Használati utasítás: A következő lépés mindig a gombra kattintva jelenik meg. Mielőtt a gombra kattintanál, próbáld önállóan kitalálni, hogy mi következik, és a kattintás után is gondolkozz el a látottakon, vesd össze azzal, amire gondoltál. Időnként be kell írnod a választ (pl. $2\cdot2 =$ ), és addig nem tudsz továbbmenni, amíg helyes választ nem adsz. A válasz mindig egy természetes szám (negatív számot ne írj); ha több szám is megfelelne, akkor a lehető legkisebbet add meg.

Az Euler–Fermat-tétel

1. feladat. Milyen nap lesz $2019^{2020}$ nap múlva?

Megoldás: Azt kell kiszámolni, hogy mit ad maradékul $2019^{2020}$ héttel osztva. Mivel $2019 \equiv$ $\pmod{7}$, ezért $2019^{2020} \equiv$ $3^{2020} \pmod{7}$.

Még $3^{2020}$ is túl nagy szám ahhoz, hogy kiszámítsuk. Kezdd el kiszámolni a $3^0,3^1,3^2,3^3,\ldots$ számok modulo $7$ maradékát, hátha észreveszel valami szabályszerűséget, ami segíthet. Azt vesszük észre, hogy a $3$ hatványainak modulo $7$ maradékaiból álló sorozat periodikus; a periódus hossza .

Tehát a $3^{2020}$ hatványban a $2020$-as kitevőt kicserélhetjük -re, anélkül, hogy a modulo $7$ maradék megváltozna. Azt kaptuk, hogy $2019^{2020} \equiv 3^{2020} \equiv 3^4 = 81 \equiv$ $\pmod{7}$. Ez pedig azt jelenti, hogy $2019^{2020}$ nap múlva lesz.

Megjegyzés: $2019^{2020}$ nap $\approx 10^{6673}$ év; ennyi idő múlva valószínűleg semmilyen nap sem lesz, sőt talán Nap sem lesz...

Kísérletezz a következő táblázattal; figyeld meg, hogyan alakulnak a hatványok modulo $m$ maradékai.

m =

Megfigyelhetjük, hogy a maradékok sorozata mindig periodikussá válik valahonnan kezdve (néha van egy „bevezető rész” a periodikus ismétlődés beállta előtt). Ez nem meglepő, mert csak véges sok különböző maradék van modulo $m$.

A továbbiakban csak azzal az esettel foglalkozunk, amikor a hatvány alapja és a modulus relatív prím, azaz $\operatorname{lnko}(a,m)=1$. A következő táblázatban már csak ezek az esetek szerepelnek; kísérletezz ezzel is, és figyeld a periódusokat.

m =

Itt minden sor már az elejétől kezdve periodikus (soha nincs „bevezető rész”, mint az első táblázatban), és a következő periódus elején mindig $1$-es áll.

A periódus hossza $a=6,\ m=25$ esetén . Ennek alapján könnyen kiszámolható, hogy $6^{123}\equiv$ $\pmod{25}$.

A periódus hossza $a=14,\ m=25$ esetén . Ennek alapján könnyen kiszámolható, hogy $14^{777}\equiv$ $\pmod{25}$.

Macerás mindig a táblázatban keresgélni (és a táblázatot kézzel legyártani még macerásabb lenne), ezért jó lenne valami általános szabályt találni a periódusokra. A táblázatot használva keresd meg azt a legkisebb $k$ számot, amelyre minden sor $k$-periodikus.

$m=25$ esetén $k=$

$m=7$ esetén $k=$

$m=13$ esetén $k=$

$m=27$ esetén $k=$

Ismerősek ezek az értékek? Ez nem más, mint az Euler-féle $\varphi$ függvény! Nem meglepő, hogy az Euler-féle $\varphi$ függvény kapcsolatban van a fenti táblázattal, hiszen a táblázatnak éppen $\varphi(m)$ sora van. Az viszont egyáltalán nem triviális (de igaz), hogy a $\varphi(m)$-edik oszlopban végig $1$-esek állnak. Ez az állítás az Euler–Fermat-tétel.

Euler–Fermat-tétel: Ha $a$ és $m$ relatív prímek, akkor $a^{\varphi(m)}\equiv 1 \pmod{m}$.    
Megjegyzések:
  1. Ha $a$ és $m$ nem relatív prímek, akkor $a$-nak semmilyen hatványa sem lehet kongruens $1$-gyel modulo $m$. Ilyenkor az első táblázatban látott „bevezető részek” miatt bonyolultabb a helyzet.
  2. Ha $m$ prímszám, akkor $\varphi(m)=m-1$; ebben az esetben a tétel jóval egyszerűbb, ezt a speciális esetet nevezik kis Fermat-tételnek. A kis Fermat-tétel (és bizonyítása) az előadás anyagában a 2090. oldalon kezdődik, az Euler–Fermat-tétel pedig a 2541. oldalon.
  3. Időnként már a $\varphi(m)$-edik oszlop előtt is van csupa $1$-es oszlop. Például $\varphi(8)=4$, de $m=8$ esetén már a második oszlopban is végig $1$-esek állnak. Ez azt jelenti, hogy $\operatorname{lnko}(a,8)=1$ esetén $a^2\equiv 1\pmod{8}$ teljesül (azaz minden páratlan szám négyzete $1$-et ad maradékul $8$-cal osztva). Ez erősebb állítás, mint az Euler–Fermat-tételből adódó $a^4\equiv 1\pmod{8}$ kongruencia. Hogy mikor lehet $\varphi(m)$-nél kisebb „jó kitevőt” találni, az nem könnyű kérdés; ez meghaladja ennek a kurzusnak a kereteit.

Az 1. feladatban azt tapasztaltuk, hogy a hatvány modulo $7$ kiszámolásánál a kitevővel modulo $6=\varphi(7)$ „kellett” számolni. A következő feladatok nagyon hasonlóak, de most már próbálgatás (táblázatkészítés) helyett az Euler–Fermat-tételt fogjuk használni.

2. feladat. Mennyit ad $11$-gyel osztva maradékul $123^{6543}$?

Megoldás: Először a hatvány alapját csökkentjük: $123 \equiv$ $\pmod{11}$, ezért $123^{6543}\equiv$ $2^{6543}\pmod{11}$.

Mielőtt alkalmaznánk az Euler–Fermat-tételt, ellenőrizni kell, hogy $\operatorname{lnko}(2,11)=1.\ \checkmark$

Most számítsuk ki a modulus $\varphi$-értékét: $\varphi(11)=$ .

Osszuk el a kitevőt maradékosen $\varphi(11)=10$-zel: $6543=10\cdot654+3$.

Ennek segítségével átalakíthatjuk a hatványt (felhasználva a hatványozás azonosságait): $2^{6543}=2^{10\cdot654+3}=(2^{10})^{654}\cdot2^3$.

Ez az átalakítás arra volt jó, hogy fel tudjuk használni az Euler–Fermat-tételt: $2^{10}\equiv 1 \pmod{11}$.

Így az átalakított hatványban $2^{10}$ helyett nyugodtan írhatunk $1$-et, a modulo $11$ maradék nem fog megváltozni: $(2^{10})^{654}\cdot2^3 \equiv 1^{654}\cdot2^3 \equiv 8\pmod{11}$.

Tehát $123^{6543}$ nyolcat ad $11$-gyel osztva maradékul.

Megjegyzés: A számolást egy sorban összefoglalhatjuk: $$123^{6543} \equiv 2^{6543} \equiv 2^{10\cdot654+3} \equiv (2^{10})^{654}\cdot2^3 \equiv 1^{654}\cdot2^3\equiv 8\ \pmod{11}.$$

3. feladat. Mennyit ad $40$-nel osztva maradékul $93^{186}$?

Megoldás:

1. $93 \equiv$ $\pmod{40}$

2. $\operatorname{lnko}(13,40)=$

3. $\varphi(40)=$

4. $186=$ $\cdot 16+$

5. $93^{186} \equiv$ $13^{186} \equiv$ $13^{11\cdot16+10} \equiv$ $(13^{16})^{11}\cdot13^{10} \equiv$ $1^{11}\cdot13^{10} \equiv$ $13^{10} \equiv$ $169^{5} \equiv$ $9^{5} \equiv$ $81\cdot81\cdot9 \equiv$ $1\cdot1\cdot9 \equiv$ $9 \pmod{40}$

Tehát $93^{186}$ kilencet ad $40$-nel osztva maradékul.

Megjegyzés: Az Euler–Fermat-tétel segítségével a $93^{186}$ hatvány modulo $40$ kiszámítását visszavezettük a $13^{10}$ hatványra. Ez jóval kisebb szám, ezt már számológéppel ki lehet számolni. De, amint a fenti levezetés mutatja, kézzel (vagy fejben) is meg lehet birkózni vele. A módszer lényege az, hogy kis lépésekben haladunk, és a $40$-nél nagyobb részeredményeket rögtön redukáljuk modulo $40$. Így soha nem kell őrületesen nagy számokkal számolni (itt pl. $13^2=169$ volt a legnehezebb számolás).

Megjegyzés: A 3. feladat megoldásában a 4. lépésben a $186=11\cdot\varphi(40)+10$ maradékos oszásból a $11$-es hányadosra nem is volt szükségünk (mert ő csak az $1^{11}$ hatványban szerepelt, annak meg mindenképpen $1$ az értéke), csak a $10$-es maradékot használtuk. Ez általában is így van, kimondhatjuk tehát az Euler–Fermat-tétel alábbi következményét:

Ha $a$ és $m$ relatív prímek és $k_1 \equiv k_2 \pmod{\varphi(m)}$, akkor $a^{k_1} \equiv a^{k_2} \pmod{m}$.    

Ezt konyhanyelven úgy fogalmazhatjuk meg, hogy a hatvány modulo $m$ maradékának kiszámolásakor a kitevő „modulo $\varphi(m)$ számít”. Ez pontosan az a megfigyelés, amit a második táblázat kapcsán tettünk. (A kongruencia bevezetésénél mondtam olyat, hogy egy modulo $m$ kongruenciában „szabad” egy számot egy másik, vele modulo $m$ kongruens számra kicserélni. Most látjuk, hogy ez kitevőkre nem igaz: a kitevőkkel modulo $\varphi(m)$ kell számolni, és ezt is csak akkor tudjuk, ha az alap és a modulus relatív prím.)

Foglaljuk össze az $a^k\equiv ? \pmod{m}$ típusú feladatok megoldásának lépéseit:

   1. az $a$ alapot redukáljuk modulo $m$;

   2. ellenőrizzük, hogy $a$ és $m$ relatív prímek;

   3. kiszámoljuk $\varphi(m)$ értékét;

   4. a $k$ kitevőt redukáljuk modulo $\varphi(m)$;

   5. kiszámítjuk a hatványt (az 1. és a 4. lépésben kapott csökkentett alappal és kitevővel) modulo $m$, szükség esetén kisebb lépésekre bontva a számolást.

Az 1. és a 2. lépés sorrendje nem fontos, de könnyebb lehet a csökkentett alapnak a modulussal vett legnagyobb közös osztóját meghatározni. (Pl. a 3. feladatban könnyebb volt $\operatorname{lnko}(13,40)$-et kiszámolni $\operatorname{lnko}(93,40)$ helyett.)

4. feladat. Mennyit ad $27$-tel osztva maradékul $2791^{1808}$?

Megoldás:

1. $2791 \equiv 10 \pmod{27}$

2. $\operatorname{lnko}(10,27)=1\ \checkmark$

3. $\varphi(27)=\varphi(3^3)=3^3-3^2=27-9=18$

4. $1808 = 100 \cdot 18 + 8$

5. $2791^{1808} \equiv 10^{1808} \equiv 10^{100 \cdot 18 + 8} \equiv (10^{18})^{100}\cdot10^{8} \equiv 1^{100}\cdot10^{8} \equiv 10^{8} \equiv 100^4 \equiv 19^4 \equiv 361^2 \equiv 10^2 \equiv 100 \equiv 19 \pmod{27}$

Tehát $2791^{1808}$ tizenkilencet ad $27$-tel osztva maradékul.

5. feladat. Mennyit az utolsó két számjegye az $1997^{5807}$ számnak?

Megoldás: Az utolsó két számjegy meghatározásához modulo $100$ kell számolnunk.

1. $1997 \equiv 97 \equiv -3 \pmod{100}$ (most jobban járunk a negatív maradékkal!)

2. $\operatorname{lnko}(-3,100)=1\ \checkmark$

3. $\varphi(100)=\varphi(2^2\cdot5^2)=\varphi(2^2)\cdot\varphi(5^2)=(2^2-2^1)\cdot(5^2-5^1)=2\cdot20=40$

4. $5807 = 145 \cdot 40 + 7$

5. $1997^{5807} \equiv (-3)^{5807} \equiv (-3)^{145 \cdot 40 + 7} \equiv ((-3)^{40})^{145}\cdot(-3)^{7} \equiv 1^{145}\cdot(-3)^{7} \equiv (-3)^{7} \equiv -3^5\cdot3^2 \equiv -243\cdot9 \equiv -43\cdot9 \equiv -387 \equiv -87 \equiv 13 \pmod{100}$

Tehát $1997^{5807}$ utolsó két számjegye egy és három.

Szorgalmi feladat. Mennyit ad $37$-tel osztva maradékul $76^{(85^{87})}$? Ha április 5-éig elküldöd emailben (lehet gépelve vagy kézírást beszkennelve is, csak olvasható legyen), akkor kapsz egy pluszpontot. Ne csak a végeredményt írd le, hanem a levezetést is. Természetesen önálló munkát kérek, egymásról lemásolni (vagy egymásnak megmutatni) a megoldást nem ér.