1071 mod 465는 141입니다. 465 mod 141은 42입니다. 141 mod 42는 15, 42 mod 15는 12, 15 mod 12는 3, 12 mod 3은 0입니다. 마지막 0이 아닌 나머지 3이 최대공약수이며, 각 단계가 허용되는 이유는 똑같습니다. a와 b를 모두 나누는 수는 a − qb도 나누므로, 두 수의 쌍과 그 나머지는 약수가 정확히 같습니다. 여기서 인수분해는 필요 없으며 그것이 실용적인 의미입니다. 1071이 3·357인 이유를 누군가 알기 훨씬 전에 3이 답이 됩니다.
단계 수를 눈여겨볼 만합니다. 라메는 1844년에 두 정수에 대한 유클리드 호제법이 작은 쪽 십진 자릿수의 약 다섯 배를 결코 넘지 않으며, 최악의 경우는 이웃한 피보나치 수라고 증명했습니다. 그래서 이 페이지의 141, 42, 15, 12, 3은 빠르게 줄어듭니다. 여기서는 어느 것도 피보나치의 이웃이 아닙니다. 같은 나머지 표의 확장판은 3 = 1071s + 465t를 만족하는 계수까지 줍니다. 컴퓨터 대수 시스템의 모든 모듈러 나눗셈 절차의 재료입니다.
답
3
읽는 방법
15 mod 12, 마지막 0이 아닌 나머지입니다. 앞의 두 링크는 첫 단계인 1071 mod 465 = 141과 465 mod 141 = 42입니다.
출처
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
계산기에서 풀어 보기
이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.