최대공약수와 최소공배수Greatest Common Factor & Least Common Multiple

$12$의 약수 $1, 2, 3, 4, 6, 12$와 $18$의 약수 $1, 2, 3, 6, 9, 18$의 공통은 $1, 2, 3, 6$. 최대공약수 $6$.

$12$의 배수 $12, 24, 36, \ldots$와 $18$의 배수 $18, 36, \ldots$에서 처음 만나는 수는 $36$. 최소공배수 $36$.

검산: $12 \times 18 = 216 = 6 \times 36$ ✓.

The factors of $12$ are $1, 2, 3, 4, 6, 12$ and of $18$ are $1, 2, 3, 6, 9, 18$; the common ones are $1, 2, 3, 6$. GCF $6$.

The multiples of $12$ are $12, 24, 36, \ldots$ and of $18$ are $18, 36, \ldots$; they first meet at $36$. LCM $36$.

Check: $12 \times 18 = 216 = 6 \times 36$ ✓.

$28 = 2^2 \times 7$, $42 = 2 \times 3 \times 7$.

최대공약수: 공통 소인수 $2$(작은 지수 $1$), $7$(지수 $1$) → $2 \times 7 = 14$.

최소공배수: $2$(큰 지수 $2$), $3$, $7$ → $2^2 \times 3 \times 7 = 84$.

검산: $28 \times 42 = 1{,}176 = 14 \times 84$ ✓. $28 \div 14 = 2$, $42 \div 14 = 3$은 서로소 ✓.

$28 = 2^2 \times 7$ and $42 = 2 \times 3 \times 7$.

GCF: shared primes $2$ (smaller exponent $1$) and $7$ (exponent $1$): $2 \times 7 = 14$.

LCM: $2$ (larger exponent $2$), $3$, and $7$: $2^2 \times 3 \times 7 = 84$.

Check: $28 \times 42 = 1{,}176 = 14 \times 84$ ✓. Also $28 \div 14 = 2$ and $42 \div 14 = 3$ are relatively prime ✓.

$8 = 2^3$, $12 = 2^2 \times 3$, $20 = 2^2 \times 5$.

최대공약수: 세 수 모두에 있는 소인수는 $2$뿐이고, 지수 $3, 2, 2$ 중 가장 작은 $2$ → $2^2 = 4$.

최소공배수: $2$는 가장 큰 지수 $3$, $3$과 $5$는 한 번씩 → $2^3 \times 3 \times 5 = 120$.

검산: $120 \div 8 = 15$, $120 \div 12 = 10$, $120 \div 20 = 6$ ✓. $4$는 셋을 모두 나누고, $8$은 $12$를 나누지 못하므로 $4$가 최대 ✓. (세 수 이상에서는 곱 $=$ 최대공약수 $\times$ 최소공배수가 일반적으로 성립하지 않는다. 여기서도 $8 \times 12 \times 20 = 1{,}920 \ne 4 \times 120$.)

$8 = 2^3$, $12 = 2^2 \times 3$, $20 = 2^2 \times 5$.

GCF: the only prime in all three is $2$, with exponents $3, 2, 2$; take the smallest, $2$: $2^2 = 4$.

LCM: $2$ with its largest exponent $3$, and $3$ and $5$ once each: $2^3 \times 3 \times 5 = 120$.

Check: $120 \div 8 = 15$, $120 \div 12 = 10$, $120 \div 20 = 6$ ✓. And $4$ divides all three while $8$ does not divide $12$, so $4$ is the greatest ✓. (For three or more numbers, product $=$ GCF $\times$ LCM need not hold: here $8 \times 12 \times 20 = 1{,}920 \ne 4 \times 120$.)

(a) $15 = 3 \times 5$, $25 = 5^2$. 공통 소인수 $5$가 있으므로 서로소가 아니다. 최대공약수 $5$, 최소공배수 $3 \times 5^2 = 75$.

(b) $8 = 2^3$, $15 = 3 \times 5$. 공통 소인수가 없으므로 서로소이고, 최소공배수는 곱 $8 \times 15 = 120$.

검산:

(a) $15 = 3 \times 5$ and $25 = 5^2$ share the prime $5$, so they are not relatively prime. GCF $5$, LCM $3 \times 5^2 = 75$.

(b) $8 = 2^3$ and $15 = 3 \times 5$ share no prime, so they are relatively prime, and the LCM is the product $8 \times 15 = 120$.

Check:

두 수의 곱은 최대공약수 $\times$ 최소공배수 $= 6 \times 180 = 1{,}080$이다. 한 수가 $30$이므로 다른 수는 $1{,}080 \div 30 = 36$.

검산: $30 = 2 \times 3 \times 5$, $36 = 2^2 \times 3^2$. 최대공약수 $2 \times 3 = 6$ ✓, 최소공배수 $2^2 \times 3^2 \times 5 = 180$ ✓.

The product of the two numbers is GCF $\times$ LCM $= 6 \times 180 = 1{,}080$. One number is $30$, so the other is $1{,}080 \div 30 = 36$.

Check: $30 = 2 \times 3 \times 5$ and $36 = 2^2 \times 3^2$ have GCF $2 \times 3 = 6$ ✓ and LCM $2^2 \times 3^2 \times 5 = 180$ ✓.

정사각형의 한 변은 $48$과 $72$의 공약수여야 하고, 가장 큰 것은 최대공약수다. $48 = 2^4 \times 3$, $72 = 2^3 \times 3^2$이므로 최대공약수는 $2^3 \times 3 = 24$. 가로 $48 \div 24 = 2$장, 세로 $72 \div 24 = 3$장이므로 $2 \times 3 = 6$장.

검산: $24 \times 24 \times 6 = 3{,}456 = 48 \times 72$ ✓.

The side of the square must be a common factor of $48$ and $72$, and the largest is the GCF. Since $48 = 2^4 \times 3$ and $72 = 2^3 \times 3^2$, the GCF is $2^3 \times 3 = 24$. That gives $48 \div 24 = 2$ squares across and $72 \div 24 = 3$ down: $2 \times 3 = 6$ squares.

Check: $24 \times 24 \times 6 = 3{,}456 = 48 \times 72$ ✓.

동시 출발은 최소공배수 $36$분마다 되풀이된다. $9$시부터 $12$시까지는 $180$분이고 $180 \div 36 = 5$이므로, $9$시의 첫 동시 출발 뒤로 $36$분 간격의 동시 출발이 $5$번 더 있다. 모두 $1 + 5 = 6$번.

검산: $9\!:\!00$에서 $36$분씩 더하면 $9\!:\!36,\ 10\!:\!12,\ 10\!:\!48,\ 11\!:\!24,\ 12\!:\!00$ — 마지막이 정확히 $12$시 ✓ ($36 \times 5 = 180$).

Joint departures repeat every LCM $= 36$ minutes. From 9:00 to 12:00 is $180$ minutes, and $180 \div 36 = 5$, so after the joint departure at 9:00 there are $5$ more, $36$ minutes apart. In all, $1 + 5 = 6$.

Check: adding $36$ minutes repeatedly to 9:00 gives 9:36, 10:12, 10:48, 11:24, 12:00, and the last lands exactly on noon ✓ ($36 \times 5 = 180$).

$(252, 105) \to (105, 42)$ ($252 - 2 \times 105 = 42$) $\to (42, 21)$ ($105 - 2 \times 42 = 21$). $42 = 2 \times 21$이므로 최대공약수는 $21$.

최소공배수 $= 252 \times 105 \div 21 = 12 \times 105 = 1{,}260$.

검산: $1{,}260 \div 252 = 5$, $1{,}260 \div 105 = 12$ ✓. 소인수분해 $252 = 2^2 \times 3^2 \times 7$, $105 = 3 \times 5 \times 7$로도 최대공약수 $21$, 최소공배수 $2^2 \times 3^2 \times 5 \times 7 = 1{,}260$ ✓.

$(252, 105) \to (105, 42)$ (since $252 - 2 \times 105 = 42$) $\to (42, 21)$ (since $105 - 2 \times 42 = 21$). As $42 = 2 \times 21$, the GCF is $21$.

LCM $= 252 \times 105 \div 21 = 12 \times 105 = 1{,}260$.

Check: $1{,}260 \div 252 = 5$ and $1{,}260 \div 105 = 12$ ✓. By factoring, $252 = 2^2 \times 3^2 \times 7$ and $105 = 3 \times 5 \times 7$ give GCF $21$ and LCM $2^2 \times 3^2 \times 5 \times 7 = 1{,}260$ ✓.

두 톱니바퀴는 같은 수의 톱니만큼 함께 움직인다. 처음 맞물린 톱니가 다시 만나려면 지나간 톱니 수가 $24$의 배수이면서 $36$의 배수여야 하고, 가장 이른 때는 최소공배수 $72$개를 지났을 때다. A는 $72 \div 24 = 3$바퀴, B는 $72 \div 36 = 2$바퀴.

검산: $24 \times 3 = 72 = 36 \times 2$ ✓.

Meshing gears advance by the same number of teeth. For the starting pair of teeth to meet again, the number of teeth passed must be a multiple of $24$ and of $36$, and the earliest is the LCM, $72$ teeth. A turns $72 \div 24 = 3$ times and B turns $72 \div 36 = 2$ times.

Check: $24 \times 3 = 72 = 36 \times 2$ ✓.

나머지 $2$를 빼면 나누어떨어진다. 그러면 그 자연수는 $60$과 $85$에 대해 무엇인가? 나머지는 나누는 수보다 작아야 한다는 조건도 잊지 말 것.

Subtract the remainder $2$ and the divisions come out even. What does that make the number with respect to $60$ and $85$? Remember that a remainder must be smaller than the divisor.

$62$를 나누어 나머지가 $2$이면 $62 - 2 = 60$은 나누어떨어진다. 마찬가지로 $87 - 2 = 85$도 나누어떨어진다. 그러므로 구하는 수는 $60$과 $85$의 공약수다. $60 = 2^2 \times 3 \times 5$, $85 = 5 \times 17$이므로 최대공약수는 $5$이고, 공약수는 $1$과 $5$뿐이다.

나머지 $2$가 나오려면 나누는 수가 $2$보다 커야 하므로 $1$은 제외된다. 답은 $5$.

검산: $62 \div 5 = 12$ 나머지 $2$ ✓, $87 \div 5 = 17$ 나머지 $2$ ✓.

If dividing $62$ leaves remainder $2$, then $62 - 2 = 60$ is divided evenly. Likewise $87 - 2 = 85$ is divided evenly. So the number is a common factor of $60$ and $85$. Since $60 = 2^2 \times 3 \times 5$ and $85 = 5 \times 17$, the GCF is $5$, and the common factors are just $1$ and $5$.

For a remainder of $2$ to occur, the divisor must exceed $2$, which rules out $1$. The answer is $5$.

Check: $62 \div 5 = 12$ remainder $2$ ✓ and $87 \div 5 = 17$ remainder $2$ ✓.

그런 수에서 $1$을 빼면 $4, 6, 9$ 모두의 배수가 된다.

Subtract $1$ from such a number and it becomes a multiple of $4$, $6$, and $9$ all at once.

구하는 수에서 $1$을 빼면 $4, 6, 9$ 모두로 나누어떨어지므로 세 수의 공배수다. $4 = 2^2$, $6 = 2 \times 3$, $9 = 3^2$의 최소공배수는 $2^2 \times 3^2 = 36$이고, 공배수는 $36, 72, 108, \ldots$이다. 따라서 구하는 수는 $37, 73, 109, \ldots$이고 가장 작은 두 개는 $37$과 $73$.

검산: $37 = 4 \times 9 + 1 = 6 \times 6 + 1 = 9 \times 4 + 1$ ✓. $73 = 4 \times 18 + 1 = 6 \times 12 + 1 = 9 \times 8 + 1$ ✓.

Subtracting $1$ from the number leaves something divisible by $4$, $6$, and $9$, so a common multiple of the three. From $4 = 2^2$, $6 = 2 \times 3$, $9 = 3^2$, the LCM is $2^2 \times 3^2 = 36$, and the common multiples are $36, 72, 108, \ldots$. So the numbers are $37, 73, 109, \ldots$, and the two smallest are $37$ and $73$.

Check: $37 = 4 \times 9 + 1 = 6 \times 6 + 1 = 9 \times 4 + 1$ ✓. $73 = 4 \times 18 + 1 = 6 \times 12 + 1 = 9 \times 8 + 1$ ✓.

예. $24 = 2^3 \times 3^1$, $36 = 2^2 \times 3^2$. 최대공약수는 소인수마다 작은 지수: $2^2 \times 3^1 = 12$. 최소공배수는 큰 지수: $2^3 \times 3^2 = 72$. 곱해 보면 $12 \times 72 = 2^{2+3} \times 3^{1+2} = 2^5 \times 3^3$이고, $24 \times 36 = 2^{3+2} \times 3^{1+2} = 2^5 \times 3^3$이다. 같다.

증명. 두 수 $a, b$를 소인수분해하고, 한쪽에만 있는 소수는 다른 쪽에 지수 $0$으로 있다고 본다. 어떤 소수 $p$에 대해 $a$의 지수를 $m$, $b$의 지수를 $n$이라 하자. 최대공약수에서 $p$의 지수는 $m$과 $n$ 중 작은 것, 최소공배수에서 $p$의 지수는 $m$과 $n$ 중 큰 것이다. 두 수 중 작은 것과 큰 것을 더하면 두 수의 합이므로

곱셈에서 같은 소수의 지수는 더해지므로, 최대공약수 $\times$ 최소공배수와 $a \times b$는 모든 소수에 대해 지수가 같다. 소인수분해가 한 가지뿐이므로 두 곱은 같은 수다.

채점 기준 (논리가 맞는 다른 풀이도 만점). ① $24, 36$의 예에서 지수의 합이 일치함을 보이면 기본 점수. ② 일반 증명에서 소인수마다 "작은 지수 $+$ 큰 지수 $=$ 두 지수의 합"을 밝히면 추가 점수. ③ 그 결과 두 곱의 소인수분해가 같아 값이 같다고 마무리하면 만점. 벤 다이어그램(겹치는 부분이 양쪽에 두 번 곱해진다)으로 일반적으로 설명해도 만점.

Example. $24 = 2^3 \times 3^1$ and $36 = 2^2 \times 3^2$. The GCF takes the smaller exponent of each prime: $2^2 \times 3^1 = 12$. The LCM takes the larger: $2^3 \times 3^2 = 72$. Their product is $12 \times 72 = 2^{2+3} \times 3^{1+2} = 2^5 \times 3^3$, while $24 \times 36 = 2^{3+2} \times 3^{1+2} = 2^5 \times 3^3$. The same.

Proof. Factor both numbers $a$ and $b$ into primes, treating a prime that appears in only one of them as having exponent $0$ in the other. For any prime $p$, let its exponent be $m$ in $a$ and $n$ in $b$. In the GCF, the exponent of $p$ is the smaller of $m$ and $n$; in the LCM, it is the larger. The smaller plus the larger of two numbers is their sum, so

Since multiplying adds the exponents of each prime, GCF $\times$ LCM and $a \times b$ have the same exponent for every prime. As prime factorizations are unique, the two products are the same number.