Algorytm Euklidesa na 1071 i 465 dochodzi do nwd 3 przez reszty 141, 42, 15, 12

Bierz reszty, aż jedna będzie zerem; ostatnia niezerowa reszta to największy wspólny dzielnik.

Równania i algebra · Poziom: Klasyczny wynik · Zaktualizowano 2026-11-10

1071 mod 465 to 141. 465 mod 141 to 42. 141 mod 42 to 15, 42 mod 15 to 12, 15 mod 12 to 3, a 12 mod 3 to 0. Ostatnia niezerowa reszta, 3, to największy wspólny dzielnik, a każdy krok jest uprawniony z tego samego powodu: każda liczba dzieląca zarówno a, jak i b dzieli też a − qb, więc para i jej reszta mają dokładnie te same dzielniki. Nic tutaj nie potrzebuje rozkładu na czynniki — i to praktyczny sens: 3 jest odpowiedzią na długo przed tym, jak ktokolwiek wie, dlaczego 1071 to 3·357.

Liczba kroków to rzecz, na którą warto patrzeć. Lamé udowodnił w 1844 roku, że algorytm Euklidesa na parze liczb całkowitych nigdy nie trwa dłużej niż około pięciokrotność liczby cyfr dziesiętnych mniejszej, a najgorsze przypadki to kolejne liczby Fibonacciego — dlatego 141, 42, 15, 12, 3 na tej stronie kurczą się szybko: nic tutaj nie jest sąsiadem Fibonacciego. Rozszerzona wersja tej samej tabeli reszt zwraca też współczynniki z 3 = 1071s + 465t, składnik każdej procedury dzielenia modularnego w systemie algebry komputerowej.

Odpowiedź

3

Jak to czytać

15 mod 12, ostatnia niezerowa reszta. Pierwsze dwa linki to kroki otwierające, 1071 mod 465 = 141 i 465 mod 141 = 42.

Źródło

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

Rozwiąż w kalkulatorze

Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.

To niezależny serwis informacyjny prowadzony przez stronę trzecią. Nie jest powiązany z firmami Casio, Texas Instruments ani ich dystrybutorami, nie jest przez nie sponsorowany ani autoryzowany. Nazwy modeli i produktów są znakami towarowymi ich właścicieli i pojawiają się tutaj wyłącznie w celu identyfikacji urządzeń.

Sekwencje naciskania klawiszy w tych instrukcjach powstały na podstawie własnych danych o układzie klawiatury z tego serwisu — tych samych, które renderuje kalkulator online — oraz publicznie dostępnych informacji o produktach. Specyfikacje i konfiguracje regionalne są potwierdzane na fizycznym urządzeniu i w najnowszych materiałach producenta.