[subject]/[topic]

Diszkrét matematikakimaradt

Kongruenciák és az Euler–Fermat-tétel

Kongruencia modulo m, maradékosztályok, számolás kongruenciákkal, redukált maradékrendszer, Euler-féle φ-függvény, Euler–Fermat- és kis Fermat-tétel.

Forrás: DiMat_ea.pdf 32–35. dia · Feladatsor 3.26

Mit jelent a kongruencia?

Definíció

Legyen m∈ℕm \in \N. Az a,b∈ℤa, b \in \Z számok kongruensek modulo mm, ha m∣a−bm \mid a - b. Jele:

a≡b(modm).a \equiv b \pmod m.

mm a kongruencia modulusa.

Ezzel ekvivalens: aa és bb ugyanazt a maradékot adja mm-mel osztva.

Példa
  • Óra: 14 óra és 2 óra ugyanott áll a számlapon, 14≡2(mod12)14 \equiv 2 \pmod{12}.
  • 3≡11(mod4)3 \equiv 11 \pmod 4, mert 4∣3−11=−84 \mid 3 - 11 = -8. Mindkettő maradéka 3.
  • −1≡3(mod4)-1 \equiv 3 \pmod 4, mert −1=4⋅(−1)+3-1 = 4 \cdot (-1) + 3.
  • 10≡1(mod9)10 \equiv 1 \pmod 9. Ezért működik a 9-es oszthatósági szabály.

Maradékosztályok

A mod mm kongruencia ℤ\Z-t mm darab maradékosztályra bontja: egy osztályba az egymással kongruens számok kerülnek. Reprezentánsaik a 0,1,…,m−10, 1, \dots, m - 1 maradékok.

Definíció · teljes reprezentánsrendszer

mm darab szám, amelyek között minden maradékosztályból pontosan egy szerepel.

Példa · az előadásból

Mod 5 teljes reprezentánsrendszer: 5,6,12,28,−65, 6, 12, 28, -6, mert maradékaik rendre 0,1,2,3,40, 1, 2, 3, 4.

Számolás kongruenciákkal

Tétel

Ha a≡ba \equiv b és c≡d(modm)c \equiv d \pmod m, akkor

a±c≡b±d(modm),a⋅c≡b⋅d(modm).a \pm c \equiv b \pm d \pmod m, \qquad a \cdot c \equiv b \cdot d \pmod m.

Következmény: ak≡bk(modm)a^k \equiv b^k \pmod m minden k∈ℕk \in \N-re.

Vagyis bármikor helyettesíthetsz egy számot a maradékával (vagy bármely vele kongruens számmal), és az eredmény maradéka nem változik. Nagy számokkal így kis számokká válik a számolás.

Példa

Mennyi 1019+5310^{19} + 53 maradéka 9-cel osztva? 10≡110 \equiv 1, tehát 1019≡119=110^{19} \equiv 1^{19} = 1, és 53≡853 \equiv 8. Összesen 1+8=9≡01 + 8 = 9 \equiv 0: osztható 9-cel (3.1 (a)).

Példa

Mi a 71007^{100} utolsó jegye? Mod 10: 71≡77^1 \equiv 7, 72=49≡97^2 = 49 \equiv 9, 73≡63≡37^3 \equiv 63 \equiv 3, 74≡21≡17^4 \equiv 21 \equiv 1. A hatványok 4-esével ismétlődnek, 100=4⋅25100 = 4 \cdot 25, tehát 7100=(74)25≡17^{100} = (7^4)^{25} \equiv 1. Az utolsó jegy 1.

Figyelem · osztani csak óvatosan

Ha ac≡bc(modm)a c \equiv b c \pmod m, akkor a≡ba \equiv b csak akkor következik, ha (c,m)=1(c, m) = 1.

Ellenpélda: 2⋅1≡2⋅3(mod4)2 \cdot 1 \equiv 2 \cdot 3 \pmod 4 (mert 2≡62 \equiv 6), de 1≢3(mod4)1 \not\equiv 3 \pmod 4. A 2-vel nem lehet egyszerűsíteni, mert (2,4)≠1(2, 4) \ne 1.

Tétel

Ha a≡b(modm)a \equiv b \pmod m, akkor (a,m)=(b,m)(a, m) = (b, m).

Egy maradékosztály minden eleme tehát ugyanannyira „relatív prím” a modulushoz.

Redukált maradékosztályok és a φ-függvény

Definíció

Egy maradékosztály redukált, ha elemei relatív prímek a modulushoz. A redukált maradékosztályok száma az Euler-féle φ-függvény:

φ(m)=#{a∈{1,…,m}∣(a,m)=1}.\varphi(m) = \#\{a \in \{1, \dots, m\} \mid (a, m) = 1\}.
mmredukált maradékokφ(m)\varphi(m)
211
31, 22
41, 32
51, 2, 3, 44
61, 52
71, 2, 3, 4, 5, 66

Prímre egyszerű: ha pp prím, φ(p)=p−1\varphi(p) = p - 1, mert 1,…,p−11, \dots, p - 1 mind relatív prím hozzá.

Tétel · φ képlete

Ha m=p1α1⋯prαrm = p_1^{\alpha_1} \cdots p_r^{\alpha_r}, akkor

φ(m)=m⋅∏i=1r(1−1pi).\varphi(m) = m \cdot \prod_{i=1}^{r} \left(1 - \frac{1}{p_i}\right).
Példa

φ(24)\varphi(24): 24=23⋅324 = 2^3 \cdot 3, tehát φ(24)=24⋅12⋅23=8\varphi(24) = 24 \cdot \frac{1}{2} \cdot \frac{2}{3} = 8. Valóban: 1,5,7,11,13,17,19,231, 5, 7, 11, 13, 17, 19, 23.

Az Euler–Fermat-tétel

Tétel · Euler–Fermat

Ha (a,m)=1(a, m) = 1, akkor

aφ(m)≡1(modm).a^{\varphi(m)} \equiv 1 \pmod m.
Tétel · kis Fermat-tétel

Ha pp prím és p∤ap \nmid a, akkor ap−1≡1(modp)a^{p-1} \equiv 1 \pmod p.

Hogyan használjuk? Nagy kitevőnél a kitevőt φ(m)\varphi(m) szerinti maradékára cseréljük: ha k=q⋅φ(m)+rk = q \cdot \varphi(m) + r, akkor

ak=(aφ(m))q⋅ar≡1q⋅ar=ar(modm).a^k = \left(a^{\varphi(m)}\right)^q \cdot a^r \equiv 1^q \cdot a^r = a^r \pmod m.
Példa · az előadásból: 2²⁰²⁶ mod 15

(2,15)=1(2, 15) = 1, és φ(15)=15⋅23⋅45=8\varphi(15) = 15 \cdot \frac{2}{3} \cdot \frac{4}{5} = 8. Mivel 2026=8⋅253+22026 = 8 \cdot 253 + 2:

22026=(28)253⋅22≡1⋅4=4(mod15).2^{2026} = (2^8)^{253} \cdot 2^2 \equiv 1 \cdot 4 = 4 \pmod{15}.

A maradék 4.

Interaktív

Nagy hatványok maradéka

aᵏ mod m kiszámítása az Euler–Fermat-tétellel.

φ(15) = 15·(1 − 1/3)·(1 − 1/5) = 8, és (2, 15) = 1.

Relatív prímek, ezért az Euler–Fermat-tétel szerint 28 ≡ 1 (mod 15). Írjuk fel: 2026 = 8·253 + 2, tehát

22026 = (28)253 · 22 ≡ 1 · 22 ≡ 4 (mod 15)

Gyakorló feladatok

Gyakorló feladat · 3.26 (a)

Mennyi maradékot ad 39283^{928}, ha 29-cel osztjuk?

Megoldás

29 prím és 29∤329 \nmid 3, így a kis Fermat-tétel szerint 328≡13^{28} \equiv 1. 928=28⋅33+4928 = 28 \cdot 33 + 4, tehát 3928≡34=81≡81−58=23(mod29)3^{928} \equiv 3^4 = 81 \equiv 81 - 58 = 23 \pmod{29}.

Gyakorló feladat · 3.26 (b)

Mennyi maradékot ad 174017^{40}, ha 25-tel osztjuk?

Megoldás

(17,25)=1(17, 25) = 1 és φ(25)=25⋅45=20\varphi(25) = 25 \cdot \frac{4}{5} = 20. 40=2⋅2040 = 2 \cdot 20, tehát 1740=(1720)2≡1(mod25)17^{40} = (17^{20})^2 \equiv 1 \pmod{25}.