Mladi nadareni matematičari

Eulerova funkcija
Kongruencije za napredne

Hrvoje Radoš (Požega)  
Godište XXV / Broj 125. / 2024.
Sir Isaac Newton

Uvod

Motivacija

Eulerov teorem

Prvo svojstvo Eulerove funkcije

Drugo svojstvo Eulerove funkcije

Treće svojstvo Eulerove funkcije

  • $\varphi(900) $ $\hskip10.7cm$ (rj. $240$)
  • $\varphi(2024) $ $\hskip10.4cm$ (rj. $880$)
  • $\varphi(20\,449)$ $\hskip10cm$ (rj. $17\,160$).

Red

Zadatci

  1. Izračunajte zadnje dvije znamenke broja $\underbrace{3^{3^{.^{.^{.^3}}}}}_{\text{2024 trojke}}$.
    ${}$
  2. Koliko ima prostih brojeva $p$ takvih da $p \mid 29^p+1$?
    ${}$
  3. Dokažite da za sve $a \in \mathbb{N},a>1,n \in \mathbb{N}$ vrijedi: $$n \mid \varphi(a^n-1).$$
  4. Nađite sve proste brojeve $p$ takve da $p^2\mid 5^{p^2}+1$.
    ${}$
  5. Odredite sve prirodne brojeve $n$ koji su relativno prosti s $1^{\varphi(n)}+2^{\varphi(n)}+3^{\varphi(n)}…+n^{\varphi(n)}$.
    ${}$
  6. Dokažite da za svaki prirodni broj $n>3$ vrijedi $1989\mid n^{n^{n^n}}-n^{n^n}$.
    ${}$
  7. 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

  1. 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.
    ${}$
  2. 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 $.
    ${}$
  3. 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).$$
    ${}$
  4. 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.$
    ${}$
  5. 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.
    ${}$
  6. 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}$.
    ${}$
  7. 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
  1. Andrej Dujella, Uvod u teoriju brojeva (skripta),
    https://web.math.pmf.unizg.hr/~duje/utb/utblink.pdf
  2. 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
  3. Justin Stevens: Olympiad Number Theory Through Challenging Problems, third edition, https://s3.amazonaws.com/aops-cdn.artofproblemsolving.com/resources/articles/olympiad-number-theory.pdf
  4. Matko Šimić: Kongruencije, Matematika i škola 114 (23), lipanj 2022.
Hrvoje Radoš, Udruga Mladi nadareni matematičari "Marin Getaldić", Požega