QuickCalculators는 음이 아닌 두 정수에 대해 유클리드 알고리즘을 실행하여 GCF가 0이 아닌 마지막 나머지로 나타날 때까지 모든 몫과 나머지를 인쇄합니다. 어느 순서로든 쌍을 입력하십시오. 단계 테이블에는 분할 형식이 표시되므로 각 라인을 직접 확인할 수 있습니다.
반복 나눗셈으로 GCF 찾기
유클리드의 알고리즘은 큰 숫자를 작은 숫자로 나누고 큰 숫자를 나머지 숫자로 바꾸는 과정을 반복하여 최대공약수를 찾습니다. 나머지 0이 나타나면 해당 단계의 제수는 GCF입니다. Euclid의 알고리즘 계산기는 각 부문을 기록하므로 체인을 감사할 수 있습니다.
816 및 2260의 경우 2260 ¼ 816로 시작하세요. 몫은 2이고 나머지는 628입니다. 다음으로, 816 ¼ 628는 나머지 188를 남깁니다. 나머지가 0이 되면 체인이 멈출 때까지 계속합니다. 0이 아닌 최종 나머지는 원래 쌍의 GCF입니다.
단계 테이블 읽기
단계 테이블에는 모든 라운드의 피제수, 제수, 몫 및 나머지가 나열됩니다. 나머지 열을 읽어보면 0으로 끝나는 축소 시퀀스가 표시됩니다. QuickCalculators는 노트북 사본이 a × b + r이 각 행의 이전 배당금과 동일한지 확인할 수 있도록 해당 열을 정렬합니다.
48 및 18에 대한 간략한 스케치:
| 배당 | 제수 | 몫 | 나머지 |
|---|---|---|---|
| 48 | 18 | 2 | 12 |
| 18 | 12 | 1 | 6 |
| 12 | 6 | 2 | 0 |
0이 아닌 마지막 나머지는 6이므로 GCF(48, 18) = 6입니다.
이런 흔한 실수를 피하세요
뺄셈 형식과 나눗셈 형식은 동일한 알고리즘입니다. 나눗셈은 하나의 몫으로 압축된 반복 뺄셈입니다. 학생들은 때때로 이를 다른 답을 가진 경쟁 방법으로 취급합니다. 올바르게 적용하면 둘 다 동일한 GCF에서 종료됩니다. 48에서 18를 두 번 빼면 12에 도달합니다. 이는 정확히 몫 2가 한 줄에 인코딩되는 것입니다.
나눗셈을 선호하면 유클리드가 설명한 수학적 경로를 변경하지 않고 쓰기를 절약할 수 있습니다.
알고리즘이 항상 종료되는 이유 이해
각 나머지는 이전 제수보다 엄격하게 작은 음수가 아닌 정수이므로 나머지 시퀀스는 영원히 내려갈 수 없습니다. 유한 하강법은 유한한 여러 단계 후에 나머지가 0이 되도록 합니다. 이 보장은 페이지에서 허용하는 모든 음수가 아닌 정수 입력에 대해 적용됩니다.
피보나치 수와 관련된 최악의 경우 쌍은 일반적인 교실 예제보다 더 많은 단계가 필요하지만 여전히 완료됩니다. 단계 수는 일반적인 무작위 쌍에 대한 입력의 로그에 따라 대략 증가하므로 Euclid의 방법은 과거 목록 요소를 확장합니다.
자주 묻는 질문
유클리드의 알고리즘은 무엇입니까?
유클리드 알고리즘은 나머지로 나누기를 반복하여 음이 아닌 두 정수의 최대공약수를 구하는 방법입니다. 0이 아닌 마지막 나머지는 GCF입니다. 계산기는 각 나눗셈 단계를 인쇄합니다.
Euclid의 알고리즘은 GCF를 어떻게 찾나요?
유클리드의 알고리즘은 더 작은 숫자로 나눈 후 더 큰 숫자를 나머지로 바꾸고 나머지가 0이 될 때까지 반복하여 GCF을 찾습니다. 나머지가 0이 아닌 마지막 단계에 사용되는 제수는 GCF입니다.
816와 2260의 GCF는 무엇인가요?
816 및 2260의 GCF은 해당 쌍에 대해 유클리드 알고리즘을 실행하고 단계 테이블에서 0이 아닌 마지막 나머지를 읽어서 찾습니다. 모든 몫과 나머지를 순서대로 보려면 이 페이지에 두 정수를 모두 입력하세요.
유클리드의 알고리즘이 작동하는 이유는 무엇입니까?
유클리드 알고리즘은 a와 b의 공약수가 b와 a mod b의 공약수도 되기 때문에 작동합니다. 쌍을 더 작은 숫자와 나머지로 바꾸면 나머지가 0이 될 때까지 GCF가 유지됩니다.
유클리드의 알고리즘은 몇 단계를 거치나요?
Euclid의 알고리즘이 수행하는 단계 수는 입력에 따라 다릅니다. 각 나머지는 이전 제수보다 작으므로 프로세스는 유한합니다. 피보나치와 같은 쌍은 평균보다 더 많은 단계가 필요하지만 일반적인 교실 숫자는 빨리 끝납니다.
뺄셈과 나눗셈 형태의 차이점은 무엇입니까?
빼기 형식은 큰 것에서 작은 것을 반복적으로 뺍니다. 나누기 형식은 몫을 사용하여 대량으로 뺍니다. 두 형식 모두 동일한 GCF를 계산합니다. 나눗셈은 뺄셈을 반복해서 간결하게 쓴 것일 뿐입니다.
요약
유클리드의 알고리즘 계산기는 반복된 나눗셈을 통해 GCF를 찾고 모든 몫과 나머지를 단계 테이블에 표시합니다. 48 및 18와 같은 쌍은 나머지 6에서 끝나며 GCF(48, 18)과 일치합니다. 뺄셈과 나눗셈 형식은 서로 다른 압축 수준에서 동일한 알고리즘입니다. 나머지는 엄격하게 감소하므로 음수가 아닌 정수에 대해서는 프로세스가 항상 종료됩니다.