Feladat:	N.39	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Braun Gábor ,  Burcsi Péter ,  Dombi Gergely ,  Duzmath Zsolt ,  Farkas Péter ,  Gyarmati Katalin ,  Kiss Márton ,  Makai Márton ,  Pap Gyula ,  Póczos Barnabás ,  Szádeczky-Kardoss Szabolcs ,  Tóth Gábor Zsolt ,  Valkó Benedek
Füzet:	1995/március, 164 - 165. oldal		PDF  |  MathML
Témakör(ök):	Euler-Fermat-tételek, Maradékos osztás, Euler-féle számelméleti függvény, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1994/szeptember: N.39

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. Legyenek $n$ páratlan prímosztói: $q_1<\text{...}<q_s$; ha az $n$ $2$-hatvány, akkor $s=0$. Jelölje $t$ a legnagyobb olyan egész számot, amelyre $\begin{array}{c}{\displaystyle 2^t\mid \left(q_1-1\right)\cdot \text{...}\cdot \left(q_s-1\right)\mathrm{.}}\end{array}$ A $\phi$ függvény értékét szolgáltató képlet szerint ekkor $\begin{array}{c}{\displaystyle 2^t\mid \left(q_1-1\right)\cdot \text{...}\cdot \left(q_s-1\right)\mid \phi \left(n\right)\mathrm{,}}\end{array}$ a $q_i$ prímek páratlan volta miatt pedig $t\ge s$. Így $\begin{array}{c}{\displaystyle 2^{2^t}-1\mid 2^{\phi \left(n\right)}-\mathrm{1,}}\end{array}$ és itt a bal oldalon álló osztó az egymáshoz páronként relatív prím $2^{2^0}+1$, $2^{2^1}+1$, $\text{...}$, $2^{2^{t-1}}+1$ (páratlan) számok szorzata. Ha $t>s$, akkor az előbbi $t$ darab szám között van olyan, amelyik relatív prím $n$-hez. A továbbiakban tegyük fel, hogy $t=s$; ekkor mindegyik $q_i$ 4-gyel osztva 3-at ad maradékul. Tételezzük fel továbbá, hogy, a feladat állításával ellentétben, $2^{\phi \left(n\right)}-1$ minden prímosztója a $q_i$ prímek közül kerül ki. Ekkor szükségképpen $q_i=2^{2^{i-1}}+1$  ($1\le i\le s$), így viszont $s\le 1$, hiszen $i\ge 2$ esetén $2^{2^{i-1}}+1\equiv 1\left(\text{mod}4\right)$. Ez azt jelenti, hogy az $n$ szám $2^{\alpha }{3}^{\beta }$ alakú. Ha $\beta =0$, akkor $\alpha \ge 3$ miatt $3=2^2-1$ valódi (és $n$-hez relatív prím) osztója $2^{2^{\alpha -1}}-1=2^{\phi \left(n\right)}-1$-nek, ellentmondás. Ha $\beta =1$, akkor $\alpha \ge 2$ miatt $5\mid 2^{2^2}-1\mid 2^{\phi \left(n\right)}-1$, ellentmondás. Ha pedig $\beta \ge 2$, akkor $7=2^3-1\mid 2^{\phi \left(n\right)}-1$, ugyancsak ellentmondás.   Megjegyzés. Több megoldó is úgy fejezte be a bizonyítást, hogy felhasználta $2^{2^5}+1$ összetettségét (ld. pl. Szalay Mihály: Számelemélet, 65. old.).   II. megoldás. Könnyen látható, hogy elegendő a feladatot páratlan $n$-re megoldani; azért a továbbiakban feltesszük, hogy $n$ páratlan. Ha $n=p^k$ prímhatvány, akkor $\phi \left(n\right)=p^k-p^{k-1}$ szerint $\begin{array}{c}{\displaystyle 2^{\phi \left(n\right)}-1=\left(2^{\left(p^k-p^{k-1}\right)/2}-1\right)\left(2^{\left(p^k-p^{k-1}\right)/2}+1\right)\mathrm{.}}\end{array}$ E két tényező nem lehet egyszerre $p$-vel osztható, hiszen a különbségük 2. Feltehető tehát, hogy $n=ab$, ahol $a$ és $b$ 1-nél nagyobb, egymáshoz relatív prím egészek. Ekkor $\phi \left(n\right)=\phi \left(a\right)\cdot \phi \left(b\right)$, és $\phi \left(a\right)$, valamint $\phi \left(b\right)$ páros. Így $\frac{\phi \left(n\right)}{2}$ osztható $\phi \left(a\right)$-val és $\phi \left(b\right)$-vel, következésképpen $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle 2^{\phi \left(a\right)}-1\mid 2^{\frac{\phi \left(n\right)}{2}}-\mathrm{1,}}\\ \hfill {\displaystyle 2^{\phi \left(b\right)}-1\mid 2^{\frac{\phi \left(n\right)}{2}}-1.}\end{array}}}\end{array}$ Az Euler‐Fermat tétel szerint $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle a\mid 2^{\phi \left(a\right)}-1\mid 2^{\frac{\phi \left(n\right)}{2}}-\mathrm{1,}}\\ \hfill {\displaystyle b\mid 2^{\phi \left(b\right)}-1\mid 2^{\frac{\phi \left(n\right)}{2}}-\mathrm{1,}}\end{array}}}\end{array}$ így, mivel $\left(a\mathrm{,}b\right)=1$, $n\mid 2^{\frac{\phi \left(n\right)}{2}}-1$. Tehát, ha $p$ tetszőleges prímosztója $2^{\frac{\phi \left(n\right)}{2}}+1$-nek, akkor $p$ nem oszthatja a 2-vel kisebb $2^{\frac{\phi \left(n\right)}{2}}-1$ számot, így $n$-et sem.  Dombi Gergely (Fazekas M. Főv. Gyak. Gimn., IV. o.t.) dolgozata alapján