Kongruencia

kongruencia
(lat.) alatt rendesen két idom egybevágását értik. Kongruensnek v. egybevágónak oly idomokat mondunk, melyek ugy alakra, mint nagyságra nézve megegyeznek, tehát egymástól csak helyzetre nézve különböznek. - K.

A kongruencia
Definíció
Jelölése , amivel egyenértékű az jelölés, tehát és ugyanazt a maradékot adják -mel osztva. A kongruencia -mel való maradékuk szerint maradékosztályokba sorolja az egész számokat.

kongruencia (modulo n)
Minden egész n számra a kongruencia elnevezésű relációt két egész szám között a következőképpen definiáljuk: a kongruens b-vel modulo n, ha egészszámú többszöröse n-nek. írásban: .

kongruencia megoldása
Felhasználjuk a Wilson tételt, ami kimondja, hogy
De ...

Ez a kongruencia a kis Fermat-tétel szerint (mod l2) helyett (mod l) minden l3 prímre teljesül. Tudjuk viszont, hogy a 230-nál kisebb számok körében (3) csak az l=11 és az l=1 006 003 prímszámokra áll fenn.

Mivel , ezért a kongruencia mindkét oldalát leoszthatjuk az összes -vel, és akkor megkapjuk az eredeti állítást.
Megjegyzés: A tétel megfordítása is igaz.

és 8. jegy felcserélését firtató kongruencia-rendszer a
7(x8 - x7) ≡ 0 (mod 10) kongruenciához vezet, amelyből már következik, hogy x8 ≡ x7 (mod 10), azaz x8 = x7, azaz nincs igazi csere.

A bizonyításhoz az (a, b egész) alakú számok körében az egészek mintájára bevezetett oszthatóság, kongruencia és rendfogalom elemi tulajdonságait használjuk fel (ezek itt is ugyanúgy érvényesek, mint az egész számoknál).

Ha a mozgathatóságot pontosan meg akarnánk határozni vagy el akarnánk kerülni, akkor föl kellene vennünk az I. 3. és 23.-beli alakzatok egzisztenciáját és I. 4.-et kongruencia-axiómákként, amint azt Hilbert tette. I. 5.

See also: Bizonyítás, Rendszer, Maradék, Szám, Hatvány