최대공약수·최소공배수 계산기

단계별 풀이

1. 1

   시작

   유클리드 호제법으로 gcd(252, 105)를 구합니다: 나누고 나머지를 취하며, 나머지가 0이 될 때까지 반복합니다.

   $$\gcd(252,\, 105)$$
2. 2

   나눗셈 1단계

   252를 105로 나누고 나머지 42을 취합니다 — 이것이 다음 제수가 됩니다.

   $$252 = 2 \cdot 105 + 42$$
3. 3

   나눗셈 2단계

   105를 42로 나누고 나머지 21을 취합니다 — 이것이 다음 제수가 됩니다.

   $$105 = 2 \cdot 42 + 21$$
4. 4

   나눗셈 3단계

   21가 42를 나누어 떨어지므로 알고리즘이 여기서 멈춥니다.

   $$42 = 2 \cdot 21 + 0$$
5. 5

   gcd는 마지막 0이 아닌 나머지

   나머지는 0이 될 때까지 줄어들고, 마지막 제수 21가 최대공약수입니다.

   $$\gcd(252,\, 105) = 21$$
6. 6

   gcd에서 lcm으로

   임의의 두 수에 대해 gcd · lcm = abs(a · b)가 성립합니다. 252 · 105를 gcd 21로 나누면 lcm을 얻습니다.

   $$\operatorname{lcm}(252,\, 105) = \frac{252 \cdot 105}{\gcd(252,\, 105)} = \frac{26460}{21} = 1260$$
7. 7

   결과

   gcd(252, 105) = 21, lcm(252, 105) = 1260