Feladat:	N.30	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Burcsi Péter ,  Csörnyei Marianna ,  Futó Gábor ,  Szeidl Ádám
Füzet:	1995/február, 101 - 102. oldal		PDF  |  MathML
Témakör(ök):	Euler-Fermat-tételek, Magasabb fokú kongruenciák, Számsorozatok, Teljes indukció módszere, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/április: N.30

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   I. megoldás. Definiáljuk a következő sorozatot: $\begin{array}{c}{\displaystyle n_0=11;n_{i+1}=2^{n_i}-1.}\end{array}$ Erről a sorozatról a következőt állítjuk: a) $n_i\mid 2^{n_i}-2$ minden $i=0$, 1, 2, $\text{...}$ esetén; b) $n_i$ összetett, ha $i\ge 1$. Mindkét állítást teljes indukcióval bizonyítjuk: a) Könnyen ellenőrizhető, hogy $n_0\mid 2^{n_0}-2$: $\begin{array}{c}{\displaystyle 2^{11}-2=2046=11\cdot 186}\end{array}$ (de a Fermat-tétel szerint is igaz). Tegyük most fel, hogy $n_i\mid 2^{n_i}-2$. Ekkor $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle 2^{n_{i+1}}-2=2\left(2^{n_{i+1}-1}-1\right)=2\left(2^{2^{n_i}-2}-1\right)=2\left(2^{\frac{2^{n_i}-2}{n_i}\cdot n_i}-1\right)=}\\ \hfill {\displaystyle =2\left(2^{n_i}-1\right)\left(1+2^{n_i}+2^{2n_i}+\text{...}+2^{2^{n_i}-2-n_i}\right)=n_{i+1}\cdot 2\left(1+2^{n_i}+\text{...}+2^{2^{n_i}-2-n_i}\right)\mathrm{.}}\end{array}}}\end{array}$ Tehát $2^{n_{i+1}}-2$ osztható $n_{i+1}$-gyel. Ezzel az a) állítást igazoltuk. b) Az $n_1$ összetett, mert $n_1=2^{11}-1=2047=23\cdot 89$. Ha $n_i$ összetett ‐ mondjuk $n_i=p\cdot q$, ahol $p$, $q>1$ ‐, akkor $\begin{array}{c}{\displaystyle n_{i+1}=2^{n_i}-1=2^{pq}-1=\left(2^p-1\right)\left(1+2^p+2^{2p}+\text{...}+2^{\left(q-1\right)p}\right)\mathrm{.}}\end{array}$ Itt mindkét tényező nagyobb, mint 1, tehát $n_{i+1}$ is összetett. Ezzel a b) állítást is bebizonyítottuk. Az $n_1$, $n_2$, $\text{...}$ számok tehát mind megfelelők. Ez a sorozat szigorúan monoton nő. ($n_i$ osztója $2^{n_i}-2$-nek, $n_i\le 2^{n_i}-2<n_{i+1}$), ezért csupa különböző elemből áll. A sorozat tehát végtelen sok megfelelő $n$-et szolgáltat.   II. megoldás. Legyen $p$  $3$-nál nagyobb prím, és legyen $n=\frac{4^p-1}{3}$. Ez egész, mert $4^p\equiv 1^p=1\left(\text{mod}3\right)$. Megmutatjuk, hogy $n$ összetett, és $n\mid 2^n-2$. Mivel végtelen sok prímszám van, ebből az állítás következik. Az $n$ összetett, mert $n=\frac{2^p+1}{3}\left(2^p-1\right)$, és $2^p\equiv {\left(-1\right)}^p\equiv -1\left(\text{mod}3\right)$ miatt az első tényező is egész, továbbá $\frac{2^p+1}{3}>\frac{2^3+1}{3}=3$,  $2^p-1>2^3-1=7$, vagyis mindkét tényező 1-nél nagyobb. Mivel $p>2$, a Fermat-tétel szerint $4^p-4$ osztható $p$-vel. Ez a szám páros, és 3-mal is osztható. Mivel $p$, 2 és 3 páronként relatív prímek, ebből következik, hogy $\begin{array}{c}{\displaystyle k=\frac{n-1}{2p}=\frac{4^p-4}{2\cdot 3\cdot p}}\end{array}$ egész szám. Az $n$ definíciója alapján $2^{2p}\equiv 1\left(\text{mod}n\right)$. Ha ezt a kongruenciát $k$-adik hatványra emeljük, és 2-vel megszorozzuk, azt kapjuk, hogy $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle 2\cdot {\left(2^{2p}\right)}^k}& {\displaystyle \equiv 2\left(\text{mod}n\right);}\hfill \\ \hfill {\displaystyle 2^n}& {\displaystyle \equiv 2\left(\text{mod}n\right)\mathrm{,}}\hfill \end{array}}}\end{array}$ azaz $2^n-2$ osztható $n$-nel. Ezzel az állítást bebizonyítottuk.  Szeidl Ádám (Miskolc, Földes F. Gimn., IV. o.t.)   Megjegyzés. A Fermat-tétel szerint, ha $p$ prím, akkor tetszőleges $p$-hez relatív prím $a$-ra $\begin{array}{c}{\displaystyle a^{p-1}\equiv 1\left(\text{mod}p\right)\mathrm{.}}\end{array}$ Ez azonban nemcsak prímekre, hanem néhány összetett $p$-re is igaz. Az ilyen számokat univerzális pszeudoprímeknek nevezzük. A legkisebb ilyen szám az 561.