“Ako sam vidio nešto dalje od drugih ljudi, to je zato što sam stajao na ramenima divova.”
Sir Isaac Newton
Uvod
Jedna od najkorisnijih ideja u teoriji brojeva, pa tako i u natjecateljskoj matematici, jesu kongruencije. Kongruencije su na prvi pogled samo “zanimljiva” notacija koja opisuje ostatke pri dijeljenju, ali kada ih se svlada, jasno je da su one izuzetno moćan alat pri uočavanju zanimljivih i važnih uzoraka koji nastaju kada promatramo ostatke pri dijeljenju nekim brojem. Cilj ovog članka obogatiti je poznavanje kongruencija dodatnim idejama (definicijama) i teoremima.
Naravno, pretpostavlja se kako je čitatelj u potpunosti upoznat s idejom kongruencija, ali oni koji nisu, mogu pogledati članak Kongruencije autora Matka Šimića [4].
Motivacija
Pokušajmo riješiti sljedeći zadatak koristeći se znanjem iz članka o kongruencijama:
Primjer 1. $\ $ Odredite zadnju znamenku broja $7^{7^7}$.
Rješenje. $\ $ Promotrimo ostatke broja $7^n$ gdje imamo $n \in \mathbb{N}_0$ pri dijeljenju s $10$.\begin{align}7^0 \equiv 1 &\pmod{10}\\
7^1 \equiv 7 &\pmod{10}\\
7^2 \equiv 9 &\pmod{10}\\
7^3 \equiv 3 &\pmod{10}\\
7^4 \equiv 1 &\pmod{10}
\end{align}Poznata je činjenica da će se ostatci sada periodički ponavljati, odnosno vrijedi:\begin{align}7^{4k} &\equiv 1 \pmod{10}\\
7^{4k+1} &\equiv 7 \pmod{10}\\
7^{4k+2} &\equiv 9 \pmod{10}\\
7^{4k+3} &\equiv 3 \pmod{10},\end{align}gdje je $k \in \mathbb{N}_0$. Stoga moramo pronaći ostatak broja $7^7$ pri dijeljenju s $4$. To se može uz nešto truda “ručno” izračunati i dobije se broj $3$, što znači da je broj $7^7$ oblika $4k+3$.
Sada zaključujemo da je zadnja znamenka broja $7^{7^7}$ znamenka $3$.
${}$
Vidjet ćemo u nastavku članka da se ovaj zadatak može riješiti na puno jednostavniji i fleksibilniji način. Proučavat ćemo i složenije inačice ovog zadatka.
Eulerov teorem
Za početak definirajmo Eulerovu funkciju.
Definicija 1. Eulerova funkcija
Eulerova funkcija $\varphi(n)$ jest funkcija koja za prirodni broj $n\in \mathbb{N}$ vraća broj brojeva iz skupa $\{1,2,\dots,n\}$ koji su relativno prosti s $n$.
Koliko je $\varphi(7)$?
Znamo da su (s obzirom na to da je $7$ prost broj) brojevi $1,2,3,4,5,6$ relativno prosti s njime, stoga je $\varphi(7) = 6.$
Koliko je $\varphi(12)$ ?
Sada bismo se trebali malo više potruditi, ali ovo i dalje znamo riješiti. Naime, $1,5,7,11$ su svi relativno prosti brojevi manji od ili jednaki $12$, stoga je $\varphi(12) = 4$.
Što ako imamo neke veće brojeve u argumentu funkcije? U nastavku navodimo svojstva Eulerove funkcije koja nas spašavaju u takvim situacijama.
Prvo svojstvo Eulerove funkcije
U nastavku ćemo za najveći zajednički djelitelj rabiti oznaku $D$, dakle $D(a,b)=c$ što znači da je najveći zajednički djelitelj brojeva $a$ i $b$ upravo $c$.
Teorem 1. (multiplikativnost Eulerove funkcije)
Neka su $m$ i $n$ relativno prosti prirodni brojevi. Tada vrijedi $$\varphi(mn)=\varphi(m)\varphi(n).$$
Ovo je najkorisnije svojstvo Eulerove funkcije jer nam omogućava lakše računanje. Npr. mogli smo pisati: $\varphi(12) = \varphi(4)\cdot\varphi(3) = 2\cdot 2=4$. Uočite da je $\varphi(12)\neq \varphi(3) \cdot \varphi(2) \cdot \varphi(2)$. Ovo svojstvo ne dokazujemo, ali zainteresirani čitatelji dokaz mogu pronaći u [1] ili [2].
Drugo svojstvo Eulerove funkcije
Teorem 2.
Neka je $p$ prost broj. Vrijedi:
$$\varphi(p)=p-1.$$
Ovo je vrlo lagano za shvatiti, naime svaki broj manji od prostog broja $p$ jest relativno prost s $p$ jer ne može nikako sadržavati $p$ u svom rastavu na proste faktore. Ovo svojstvo primijenili smo pri računanju $\varphi(7)$.
Treće svojstvo Eulerove funkcije
Teorem 3.
Neka je $p$ prost broj. Tada vrijedi:
$$\varphi(p^k)=p^k-p^{k-1}.$$
Ovo je svojstvo složenije od prethodnog. Znamo da funkcija neće brojiti samo brojeve oblika $kp$ gdje $k\in \mathbb{N}$ jer su to jedini brojevi manji od ili jednaki $p^k$ koji s njim nisu relativno prosti. To su upravo brojevi iz skupa $\{p, 2p, \dots, p^k\}$, a takvih ima $p^{k-1}$. Zatim taj broj oduzmemo od ukupnog broja brojeva manjih od ili jednakih $p^k$, a to je $p^{k}$, i dobijemo traženi rezultat. Primijetite kako je treće svojstvo samo općenitija inačica drugog svojstva.
Primjenjujući ova tri svojstva, možemo računati vrijednosti Eulerove funkcije na učinkovitiji način. Štoviše, možemo izvesti sljedeću formulu:
Teorem 4.
Neka je $n$ prirodan broj čiji je rastav na proste faktore $n=p_1^{\alpha_1}\dots p_l^{\alpha_l}$, gdje su $p_i$ međusobno različiti prosti brojevi, a $\alpha_i$ prirodni brojevi za svaki $i=1, 2, \dots, l$, pri čemu je $l\in \mathbb{N}$. Tada vrijedi:
$$\varphi(n)=n\left(1-\frac{1}{p_1}\right)\dots\left(1-\frac{1}{p_l}\right).$$
Dokaz. $\ $Iz prvog svojstva Eulerove funkcije jasno je da vrijedi:$$\varphi(n)= \varphi(p_1^{\alpha_1}\dots p_l^{\alpha_l})= \varphi(p_1^{\alpha_1})\dots\varphi(p_l^{\alpha_l})$$ jer su potencije različitih prostih brojeva relativno proste.
Zatim, primjenjujući treće svojstvo, dobivamo:$$\varphi(n)=(p_1^{\alpha_1}-p_1^{\alpha_1-1})\dots (p_l^{\alpha_l}-p_l^{\alpha_l-1}).$$ Odavde izlučivanjem $n$ slijedi:$$\varphi(n)=p_1^{\alpha_1}\left(1-\frac1{p_1}\right)\dots p_l^{\alpha_l}\left(1-\frac1{p_l}\right) = n\left(1-\frac{1}{p_1}\right)\dots\left(1-\frac{1}{p_l}\right).$$
${}$
Za vježbu izračunajte vrijednosti:
- $\varphi(900) $ $\hskip10.7cm$ (rj. $240$)
- $\varphi(2024) $ $\hskip10.4cm$ (rj. $880$)
- $\varphi(20\,449)$ $\hskip10cm$ (rj. $17\,160$).
${}$
Nakon što smo se upoznali s Eulerovom funkcijom, uvodimo Eulerov teorem:
Teorem 5. Eulerov teorem
Ako su $a$ i $n$ relativno prosti prirodni brojevi, tj. $D(a, n)=1$, vrijedi:$$ a^{\varphi(n)} \equiv 1 \pmod{n}.$$
Čitatelj smije preskočiti sljedeći dokaz zbog njegove opsežnosti, no preporuča se ipak proučiti ga.
Dokaz. $\ $Definirajmo skup $S$ koji sadrži sve brojeve relativno proste s $n$ koji su ujedno manji od $n$. Znamo da takvih brojeva ima $\varphi(n)$. $$S=\{a_1,a_2…a_{\varphi(n)}\}$$ Neka je $$R=\{aa_1,aa_2…aa_{\varphi(n)}\}.$$ Kako je svaki element skupa $S$ relativno prost s $n$ i kako je broj $a$ relativno prost s $n$, i svaki će element skupa $R$ biti relativno prost s $n$.
Dokažimo da su svi elementi skupa $R$ različiti modulo $n$. Neka je $aa_i\equiv aa_j \pmod{n}$. Tada $aa_i-aa_j \equiv 0\pmod{n}$, tj. \begin{equation} a(a_i-a_j)\equiv 0\pmod{n}.\tag{1}\label{eq:1} \end{equation} Znamo da su $a$ i $n$ relativno prosti. Zato je $a_i-a_j\equiv 0 \pmod{n}$, tj. $a_i\equiv a_j \pmod{n}$. Ovo znači da za različite elemente $a_i,\ a_j\in S$ vrijedi
$$ a\cdot a_i\not\equiv a\cdot a_j \pmod{n}.$$ Kako skupovi $R$ i $S$ imaju jednak broj elemenata, zaključujemo da elementi skupa $R$ pri dijeljenju s $n$ daju sve moguće ostatke relativno proste s $n$, tj. točno one brojeve koji su u skupu $S$.
Zaključujemo:
\begin{align}
a_1a_2\dots a_{\varphi(n)} & \equiv aa_1\cdot aa_2\dots aa_{\varphi(n)} \pmod{n}\\
a_1a_2\dots a_{\varphi(n)} & \equiv a^{\varphi(n)}\cdot a_1a_2\dots a_{\varphi(n)} \pmod {n}\\
a^{\varphi(n)} a_1a_2\dots a_{\varphi(n)}-a_1a_2\dots a_{\varphi(n)} &\equiv 0 \pmod{n}\\
a_1a_2\dots a_{\varphi(n)}(a^{\varphi(n)}-1)&\equiv 0 \pmod{n}.
\end{align}
Kako su brojevi $a_1, a_2,\dots, a_{\varphi(n)}$ relativno prosti s $n$, slijedi da je $a^{\varphi(n)} \equiv 1 \pmod{n}$.
${}$
Primjer 2. $\ $Nađite ostatak pri dijeljenju $2^{100}$ s $11,25$ i $39$.
Rješenje. $\ $Želimo primijeniti Eulerov teorem. U tu ćemo svrhu najprije odrediti vrijednosti Eulerove funkcije za 11, 25 i 39 koristeći se svojstvima koja smo obradili. $\varphi(11)=11-1=10$ po drugom svojstvu. Po trećem svojstvu vrijedi $\varphi(25)=\varphi(5^2)=5^2-5^1=25-5=20$. Za izračunati $\varphi(39)$ primjenjujemo prvo i drugo svojstvo pa je $\varphi(39)=\varphi(3)\varphi(13)=2\cdot 12=24$. Napokon smo spremni primijeniti Eulerov teorem:\begin{gather}
2^{\varphi(11)} \equiv 1\!\! \pmod{11}\quad \text{tj.}\quad 2^{10} \equiv 1\!\! \pmod{11} \implies 2^{100} \equiv 1\!\! \pmod{11} \\
2^{\varphi(25)} \equiv 1\!\! \pmod{25}\quad \text{tj.}\quad 2^{20} \equiv 1\!\! \pmod{25} \implies 2^{100} \equiv 1\!\! \pmod{25} \\
2^{\varphi(39)} \equiv 1\!\! \pmod{39}\quad \text{tj.}\quad 2^{24} \equiv 1\!\! \pmod{39} \\
\implies 2^{96} \equiv 1\!\! \pmod{39} \implies 2^{100} \equiv 16\!\! \pmod{39}.\end{gather}
${}$
Za kraj predstavljamo još jednu korisnu ideju.
Lema 1.
Neka je $r$ ostatak pri dijeljenju broja $b$ s $\varphi(n)$, odnosno najmanji broj iz $\mathbb{N}_0$ za koji je $b\equiv r \pmod{\varphi(n)}$. Ako je $a$ prirodan broj relativno prost s $n$, onda je $$a^b \equiv a^{r}\pmod{n}.$$
Dokaz. $\ $Kako je $b \equiv r \pmod{\varphi(n)}$, vrijedi $b=k\varphi(n)+r$ za neki $k\in \mathbb{N}$. Dakle, vrijedi $a^{b}=a^{k\varphi(n)+r}=a^{k\varphi(n)}\cdot a^r$. Iz Eulerova teorema slijedi da je $a^{k\varphi(n)} \equiv 1 \pmod{n}$ pa je $a^{b}\equiv 1\cdot a^r\equiv a^r \pmod{n}$.
${}$
Ova je lema na prvi pogled složena i treba vremena da se na nju naviknete, ali je jako korisna u zadatcima koji će kasnije doći.
Riješimo sada zadatak iz primjera 1 s kojim smo se “mučili” na početku, ali na znatno lakši način.
Primjer 3. $\ $ Odredite zadnju znamenku broja $7^{7^7}$.
Rješenje. $\ $ Tražimo: $$7^{7^7} \pmod{10}.$$ Po lemi 1 znamo: $$7^{7^7} \equiv 7^{r} \pmod{10},$$ gdje je $r$ ostatak pri dijeljenju $7^7$ brojem $4$. Dakle, $r \equiv 7^7 \equiv (-1)^7\equiv-1\equiv 3\pmod{4}.$ Dakle $$7^{7^7} \equiv 7^{3}\equiv343\equiv 3 \pmod{10}.$$ Zadnja znamenka broja $7^{7^7}$ je $3$.
${}$
Primjer 4. $\ $ Nađite zadnje dvije znamenke broja $3^{3^{3^3}}.$
Rješenje. $\ $ Tražimo $x$ tako da je $3^{3^{3^3}} \equiv 3^x \pmod{100}$.
Prema lemi 1, dovoljno je naći $x$ tako da vrijedi $3^{3^3} \equiv x \pmod{\varphi{(100)}}$, odnosno, zbog $\varphi(100)=40,$ $$3^{3^3}\equiv x\pmod{40}. $$ Na isti način, zbog $\varphi(40)=16$ dovoljno je naći $y$ tako da vrijedi $3^3\equiv y\pmod{16}.$
Vrijedi $3^3=27\equiv 11\pmod{16},$ pa možemo uzeti $y=11.$ Tada je $3^{3^3} \equiv 3^{11}\pmod {40}$. Kako je $3^4 = 81 \equiv 1 \pmod{40}$, vrijedi $$3^{11} = 3^4 \cdot 3^4 \cdot 3^3 \equiv 3^3\equiv 27 \pmod{40}.$$ Dakle, možemo uzeti $x=27$, tj. vrijedi $$ 3^{3^{3^3}} = 3^{27} \pmod{100}.$$ Ovo rješavamo ručno (ili s pomoću kalkulatora) te dobivamo $3^{3^{3^3}} = 87 \pmod{100}$.
${}$
Korolar 1. $\ $ Mali Fermatov teorem
Neka je $p$ prost broj i $a$ prirodan broj koji nije djeljiv s $p$, tj. $p\nmid a.$ Vrijedi: $$a^{p-1} \equiv 1 \pmod{p}.$$
Korolar je zapravo samo poseban slučaj Eulerova teorema koji se često primjenjuje u zadatcima i na njega ćemo se referirati pokratom MFT. Iz malog Fermatova teorema slijedi i ova tvrdnja:
Za prosti broj $p$ i prirodni broj $a$ vrijedi \begin{equation} a^p \equiv a \pmod{p}.\tag{2}\label{eq:2}\end{equation}
Uočimo da sada ne moramo provjeravati uvjet $p\nmid a$. Naime, $$a^p \equiv a\!\! \pmod{p} \iff a^p -a \equiv 0\!\! \pmod{p} \iff a(a^{p-1}-1) \equiv 0\!\! \pmod{p},$$
pa se lako vidi da tvrdnja vrijedi i ako je $a\equiv 0\pmod{p}$ i ako $p$ ne dijeli $a$.
Primjer 5. $\ $ Neka je $a_1, a_2, \ldots$ niz prirodnih brojeva: $a_1=2$ i $$a_{n+1}=a_n^{151}+a_n.$$ Dokaži da $151$ dijeli $a_{150}-1$.
Rješenje. $\ $ Uočimo da je $151$ prost broj.
Po MFT-u slijedi: $$a_n^{151} \equiv a_n \pmod{151}.$$ Promatrajmo sada početnu jednadžbu modulo $151$:
$$a_{n+1} \equiv a_n^{151}+a_n\equiv 2a_n \pmod{151}.$$ Indukcijom zaključujemo: $$a_{n+1} \equiv 2^na_1 \equiv 2^{n+1} \pmod{151}.$$ Sada je samo potrebno pokazati: $$a_{150}-1 \equiv 2^{150}-1 \equiv 0 \pmod{151},$$ što slijedi iz MFT-a.
${}$
Red
Definicija 2.
Neka su $a$ i $m$ relativno prosti prirodni brojevi.
Za broj $x\in \mathbb{N}$ kažemo da je red broja $a$ modulo $m$ ako je to najmanji broj za koji vrijedi:
$$a^x \equiv 1 \pmod{m}.$$
Pišemo $x=\text{ord}_m(a).$ Ova oznaka potječe od engleskog naziva order.
Teorem 7.
Neka su $a,n$ i $m$ prirodni brojevi. Vrijedi ekvivalencija: $$a^n\equiv 1\!\! \pmod{m} \iff \text{ord}_m(a)\mid n.$$
Dokaz. $\ $ Ako vrijedi $\text{ord}_m(a) \mid n$, onda trivijalno slijedi $a^n = 1 \pmod {m}$.
Druga je implikacija nešto složenija. Pretpostavimo da $\text{ord}_m(a)\nmid n$. Neka je $n = k \cdot \text{ord}_m(a) +r$, gdje je $0<r< \text{ord}_m(a)$. Tada je $$1\equiv a^n\equiv a^{k \cdot \text{ord}_m(a) +r} \equiv a^r \pmod{m}.$$ Međutim, to je kontradikcija zbog definicije reda (red mora biti najmanji broj za koji vrijedi navedena kongruencija, ali našli smo da $r$ to zadovoljava).
Teorem je lakše shvatiti ako zamislimo kako se rješava kongruencija: $$a^x\equiv 1 \pmod m$$ gdje su $a$ i $m$ zadani prirodni brojevi. Ovaj teorem govori da je dovoljno samo pronaći najmanji broj $x$ za koji jednadžba vrijedi i onda zaključiti kako su sva rješenja višekratnici tog broja.
Primjer 6. $\ $ Neka je $a,n \in \mathbb{N}, \, a\ge 1$. Odredite $\text{ord}_{a^n-1}(a)$.
Rješenje. $\ $ Tražimo najmanji $x$ za koji vrijedi: $$a^x\equiv 1 \pmod{(a^n-1)}.$$ Očito vrijedi $x\geq n$ jer inače kongruencija neće vrijediti.
Za $x=n$ kongruencija vrijedi. S obzirom na to da $x$ mora biti najmanji broj za koji navedeno vrijedi, $x=n$ odnosno $\text{ord}_{a^n-1}(a)=n$.
${}$
Zadatci
- Izračunajte zadnje dvije znamenke broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2024 trojke}}$.
${}$ - Koliko ima prostih brojeva $p$ takvih da $p \mid 29^p+1$?
${}$ - Dokažite da za sve $a \in \mathbb{N},a>1,n \in \mathbb{N}$ vrijedi: $$n \mid \varphi(a^n-1).$$
- Nađite sve proste brojeve $p$ takve da $p^2\mid 5^{p^2}+1$.
${}$ - Odredite sve prirodne brojeve $n$ koji su relativno prosti s $1^{\varphi(n)}+2^{\varphi(n)}+3^{\varphi(n)}…+n^{\varphi(n)}$.
${}$ - Dokažite da za svaki prirodni broj $n>3$ vrijedi $1989\mid n^{n^{n^n}}-n^{n^n}$.
${}$ - Pokažite da za svaki prosti broj $p$ postoji $n \in \mathbb{N}$ takav da vrijedi: $$p\mid 2^n+3^n+6^n-1.$$
${}$
Rješenja
- Kao u rješenju 4. primjera, služit ćemo se lemom 1. Tražimo ostatak pri dijeljenju broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2024 trojke}}$ sa $100$, odnosno ostatak pri dijeljenju broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2023 trojke}}$ sa $\varphi(100)=40$, zatim ostatak pri dijeljenju broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2022 trojke}}$ sa $\varphi(40)=16$, broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2021 trojka}}$ sa $\varphi(16)=8$, broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2020 trojki}}$ sa $\varphi(8)=4$. Kako je u eksponentu neparan broj, vrijedi
$$\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2020 trojki}}\equiv 3^1\pmod{4}.$$
I sad se vraćamo unazad tako da svaki put uvrštavamo prethodni rezultat.
Na kraju se dobije rješenje 87.
${}$ - Zapišimo izraz s pomoću kongruencija: $29^p+1 \equiv 0 \pmod{p}$.
Prema malom Fermatovu teoremu, za bilo koji prost broj $p$ vrijedi $29^p\equiv29 \pmod{p}$. Kombiniranjem tih dvaju izraza dobije se: $$30\equiv 0 \pmod{p}.$$ Zato traženi prost broj $p$ pripada skupu: $\{2,3,5\}$. Provjerom se utvrdi da sva tri broja zadovoljavaju uvjet $p\mid 29^p+1 $.
${}$ - Znamo da $\text{ord}_{a^n-1}(a)=n$ (primjer 6).
Prema Eulerovu teoremu (smijemo primijeniti Eulerov teorem jer očito $D(a^n-1,a)=1$) vrijedi: $$a^{\varphi(a^n-1)}\equiv 1 \pmod{(a^n-1)}.$$ Sada prema teoremu 7 vrijedi: $$\text{ord}_{a^n-1}(a) \mid \varphi(a^n-1),$$ odnosno $$n \mid \varphi(a^n-1).$$
${}$ - Odredimo najprije proste brojeve $p$ za koje vrijedi $p\mid 5^{p^2}+1$. Za $p=5$ to očito ne vrijedi. Prema MFT-u za $p\neq5$ vrijedi $5^{p-1}\equiv1 \pmod{p}$. Zato je $$5^{p^2}+1=5\cdot (5^{p-1})^{p+1}+1 \equiv 5\cdot 1+1\equiv 6 \pmod{p}.$$ Da bi vrijedilo $p\mid 5^{p^2}+1$, mora biti $6\equiv0\pmod{p}$, što je moguće samo za $p=2$ i $p=3$. Uvjet $p^2\mid 5^{p^2}+1$ zadovoljava samo $p=3.$
${}$ - Zapišimo zbroj na ljepši način: $\ \displaystyle\sum_{i=1}^{n}i^{\varphi_{(n)}}$.
Ovo izgleda savršeno za Eulerov teorem. Neka je $p$ neki prosti djelitelj od $n$. Razdvojit ćemo zbroj na dva zbroja: jedan po $i$ za koje vrijedi $p\mid i$ i drugi za $p\nmid i$: $$\sum_{i=1}^{n}i^{\varphi_{(n)}}=\sum_{p\mid i}i^{\varphi_{(n)}}+\sum_{p\nmid i}i^{\varphi_{(n)}}.$$ Ako $p\mid i$, onda $i^{\varphi(n)}\equiv0\pmod{p}$, pa je $\ \displaystyle\sum_{p\mid i}i^{\varphi_{(n)}}\equiv0\pmod{p}.$ Za $p\nmid i$ vrijedi $i^{\varphi(n)}\equiv1\pmod{p}$, pa je druga suma kongruentna broju svih $i$ relativno prostih s $p$. Odnosno $\ \displaystyle\sum_{p\nmid i}i^{\varphi_{(n)}}\equiv n-\frac{n}{p}\pmod{p}$. Stoga $$\sum_{i=1}^{n}i^{\varphi_{(n)}}=\sum_{p\mid i}i^{\varphi_{(n)}}+\sum_{p\nmid i}i^{\varphi_{(n)}} \equiv 0 + \left(n-\frac{n}{p}\right)$$ $$\equiv n-\frac{n}{p} \equiv -\frac{n}{p}\pmod{p} $$ jer $p\mid n$. Ovo će biti kongruentno s nula modulo $p$ ako i samo ako $p^2 \mid n$. Stoga je rješenje svaki $n$ za koji vrijedi $p^2 \nmid n$ za sve proste brojeve $p$, tj. svaki kvadratno slobodni prirodan broj.
${}$ - Znamo da: $1989 = 9 \cdot 13 \cdot 17$.
Sada ćemo posebno dokazati da svaki od ovih faktora dijeli $n^{n^{n^n}}-n^{n^n}.$ Dokažimo $$n^{n^{n^n}}\equiv n^{n^n} \pmod{9}.\tag{1}$$ Ako $3 \mid n$, onda (1) vrijedi. Ako $3\nmid n$, zbog $\varphi(9)=6$, prema lemi 1 dovoljno je dokazati $$n^{n^n} \equiv n^n \pmod{6}.$$ Očito i za parne i za neparne $n$ vrijedi $n^{n^n}\equiv n^n \pmod{2}$. Treba još pokazati: $$n^{n^n}\equiv n^n \pmod{3}.$$ Kako je $\varphi(3)=2$, prema lemi 1 treba samo pokazati: $${n^n}\equiv n \pmod{2},$$ što očito vrijedi. Ovime je dokazano (1).
Sada želimo pokazati: $$n^{n^{n^n}}\equiv n^{n^n} \pmod{13}.\tag{2}$$ Ako $13 \mid n$, onda tvrdnja očito vrijedi. Inače trebamo dokazati: $$n^{n^n}\equiv n^n \pmod{12},$$ odnosno $n^{n^n}\equiv n^n \pmod{4}$ i $n^{n^n}\equiv n^n \pmod{3}.$ Prva tvrdnja očito vrijedi ako $2\mid n$, a za neparne $n$, zbog $\varphi(3)=2$, treba još provjeriti: $$n^n\equiv n\pmod 2,$$ što očito vrijedi. Drugu smo tvrdnju već provjerili. Dakle, vrijedi (2).
Za kraj treba pokazati: $$n^{n^{n^n}}\equiv n^{n^n} \pmod{17}.\tag{3}$$ Ako $17 \mid n$, tvrdnja očito vrijedi. U suprotnom primjenjujemo lemu 1. Vrijedi $\varphi(17)=16,$ pa treba pokazati:
$$n^{n^n}\equiv n^n \pmod{16}.$$ Ako $2 \mid n$, tvrdnja vrijedi zbog $n>3$. Inače, zbog $\varphi(16)=8$ treba pokazati: $${n^n}\equiv n \pmod{8}.$$ Znamo da je $n$ neparan, stoga $n^2 \equiv 1 \pmod{8}$, pa i $n^{n-1} \equiv 1 \pmod{8}$. Iz toga očito slijedi $n^n \equiv n \pmod{8}$. Ovime je dokazano (3).
Nakon ovoga napornog raspisivanja očito je da vrijedi $1989 \mid n^{n^{n^n}}-n^{n^n}$.
${}$ - Ako je $p=2$ ili $p=3$, onda stavimo $n=2$. Ako je $p>3$, uzmemo $n = p-2$. Primjenom malog Fermatova teorema dobivamo:
$$6(2^{p-2}+3^{p-2}+6^{p-2} -1 )\equiv3\cdot2^{p-1}+2\cdot3^{p-1}+6^{p-1} – 6$$ $$\equiv 3\cdot 1+2\cdot1+1-6 \equiv 0 \pmod{p}.$$ Kako je $p$ relativno prost sa $6$, zaključujemo da je $2^{p-2}+3^{p-2}+6^{p-2} -1 \equiv 0 \pmod{p}$, čime smo pokazali sve što smo htjeli.
Literatura
- Andrej Dujella, Uvod u teoriju brojeva (skripta),
https://web.math.pmf.unizg.hr/~duje/utb/utblink.pdf - Shashank Chorge, Juan Vargas (2013): Proof of Euler’s φ (Phi) Function Formula, Rose-Hulman Undergraduate Mathematics Journal, Vol. 14 : Iss. 2 , Article 6. https://scholar.rose-hulman.edu/rhumj/vol14/iss2/6
- Justin Stevens: Olympiad Number Theory Through Challenging Problems, third edition, https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf
- Matko Šimić: Kongruencije, Matematika i škola 114 (23), lipanj 2022.