1071과 465의 유클리드 호제법은 나머지 141, 42, 15, 12를 거쳐 최대공약수 3에 이릅니다

나머지가 0이 될 때까지 나머지를 구합니다. 마지막 0이 아닌 나머지가 최대공약수입니다.

방정식과 대수 · 난이도: 고전적인 결과 · 업데이트 2026-11-10

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

계산기에서 풀어 보기

이 링크는 이 문제의 숫자가 이미 입력된 알맞은 계산기를 엽니다. 위 줄은 화면에 표시되어야 하는 내용입니다. 직접 확인하세요.

본 사이트는 독립적인 제3자 도구 사이트입니다. Casio, Texas Instruments 및 그 대리점과 제휴·후원·승인 관계가 없습니다. 모델명과 제품명은 각 권리자의 상표이며, 기기를 식별하기 위한 용도로만 표시됩니다.

이 매뉴얼의 키 조작 순서는 본 사이트가 온라인 계산기를 렌더링할 때 사용하는 것과 동일한 자체 레이아웃 데이터와 공개된 제품 정보를 바탕으로 작성했습니다. 사양과 지역별 구성은 실제 기기 및 제조사의 최신 자료로 확인합니다.