1. 정의A = Bq + R일 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다. 위의 정의를 활용하면 연쇄적인 나눗셈으로 A,B의 최대공약수를 소인수 분해 없이 구할 수 있다.2. 구현개발 언어로 이를 구현하기 위해서는 %(mod) 연산자를 알고 있어야 한다. A%B의 결과값은 A를 B로 나누었을 때, 나머지를 반환한다.큰 수를 A, 작은 수를 B라고 해보자.1️⃣ 큰 수를 작은 수로 나누고 나머지를 얻는다. 이때 나머지를 R이라 하자.A % B = R2️⃣ 작은 수를 나머지로 나눈다. 이때 나온 나머지 값을 R'라고 하자.B % R = R'3️⃣ 2번을 작은수가 나머지로 나누어 떨어질 때까지 반복한다.R % R' = 04️⃣ 작은 수를 나누어 떨어지게 만든 R'는 유클리드 호제법을 따라 거슬러..