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-féle $\varphi$ függvény

Vegyünk egy $m$ természetes számot, és számoljuk meg, hogy $1$-től $m$-ig hány olyan szám van, ami relatív prím $m$-hez. Ezt a számot $\varphi(m)$ jelöli; az így definiált függvény az Euler-féle $\varphi$ függvény. Formálisan: $$\varphi\colon\; \mathbb{N}\to\mathbb{N},\; m\mapsto \bigl\vert \{ a : 1 \leq a \leq m, \, \operatorname{lnko}(a,m)=1 \} \bigr\vert.$$

Nézzünk néhány példát:

$\varphi(1)=$ $\bigl\vert \{ 1 \} \bigr\vert = 1$

$\varphi(2)=$ $\bigl\vert \{ 1 \} \bigr\vert = 1$

$\varphi(3)=$ $\bigl\vert \{ 1,2 \} \bigr\vert = 2$

$\varphi(4)=$ $\bigl\vert \{ 1,3 \} \bigr\vert = 2$

$\varphi(5)=$ $\bigl\vert \{ 1,2,3,4 \} \bigr\vert = 4$

$\varphi(6)=$ $\bigl\vert \{ 1,5 \} \bigr\vert = 2$

$\varphi(7)=$ $\bigl\vert \{ 1,2,3,4,5,6 \} \bigr\vert = 6$

$\varphi(8)=$ $\bigl\vert \{ 1,3,5,7 \} \bigr\vert = 4$

$\varphi(9)=$ $\bigl\vert \{ 1,2,4,5,7,8 \} \bigr\vert = 6$

$\varphi(10)=$ $\bigl\vert \{ 1,3,7,9 \} \bigr\vert = 4$

Idáig elég összevisszának tűnnek az értékek, nemigen látszik semmi szabályszerűség (még csak nem is monoton a függvény: hol csökken, hol nő az érték). Azért mégis lehet valami általános megfigyelést tenni. Például, ha $p$ prímszám, akkor $1$-től $p$-ig minden szám relatív prím $p$-hez, kivéve magát $p$-t. Tehát ekkor $\varphi(p)=$ $p-1$. (Lásd a fenti példák között a $p=2,3,5,7$ értékeket.)

Nézzünk most prímhatványokat. Az alábbi példákban sorold fel $1$-től $m$-ig azokat a számokat, amelyek relatív prímek $m$-hez, majd add meg $\varphi(m)$ értékét.

$\varphi(32)=$ $=\bigl\vert \{ 1,3,5,7,9,\ldots,31 \} \bigr\vert = 32-16 = 16$ (minden második szám kimarad). Általánosan: $\varphi(2^k)=$ $2^k-2^{k-1}=2^{k-1}$.

$\varphi(27)=$ $=\bigl\vert \{ 1,2,4,5,7,8,10,\ldots,26 \} \bigr\vert = 27-9 = 18$ (minden harmadik szám kimarad). Általánosan: $\varphi(3^k)=$ $3^k-3^{k-1}$.

$\varphi(125)=$ $=\bigl\vert \{ 1,2,3,4,6,7,8,9,11,\ldots,124 \} \bigr\vert = 125-25 = 100$ (minden ötödik szám kimarad). Általánosan: $\varphi(5^k)=$ $5^k-5^{k-1}$.

Prímhatványokra tehát úgy számíthatjuk ki $\varphi$ értékét, hogy az adott prímhatványból kivonjuk ugyanazon prímnek eggyel kisebb kitevőjű hatványát:

Ha a szám nem prímhatvány (vagyis több különböző prímosztója is van), akkor $\varphi$ értékét megkaphatjuk úgy, hogy az egyes prímhatványtényezők $\varphi$ értékeit összeszorozzuk:

Ez egyáltalán nem triviális állítás; a bizonyítás megtalálható az előadás anyagában a 2488. oldaltól kezdődően (a $\varphi$ függvényről szóló rész már a 2467. oldalon kezdődik). Ez a bizonyítás lineáris kongruenciarendszereket használ. Íme egy másik gondolatmenet, ami $\varphi(360)$ példáján magyarázza el a fenti képletet, a szitaformulát használva.

Az Euler-féle $\varphi$ függvény használható nagy hatványok modulo $m$ maradékainak kiszámítására. Hogy az majd flottul menjen, szükséges, hogy jól és gyorsan ki tudd számolni fejben $\varphi(m)$ értékét (nem túl nagy $m$-ekre), úgyhogy gyakoroljuk egy kicsit!

$\varphi(81)=$ $=\varphi(3^4)=3^4-3^3=81-27=54$

$\varphi(100)=$ $=\varphi(2^2)\cdot\varphi(5^2)=(2^2-2)\cdot(5^2-5)=2\cdot20=40$

$\varphi(41)=$ $=41-1=40$

$\varphi(24)=$ $=\varphi(2^3)\cdot\varphi(3)=(2^3-2^2)\cdot(3-1)=4\cdot2=8$

$\varphi(360)=$ $=\varphi(2^3)\cdot\varphi(3^2)\cdot\varphi(5)=(2^3-2^2)\cdot(3^2-3)\cdot(5-1)=4\cdot6\cdot4=96$

Na most már készen állsz arra, hogy választ adj olyan kérdésekre, mint például, hogy milyen nap lesz $2019^{2020}$ nap múlva!