Az A. 909. feladat (2025. május)

A. 909. Bizonyítsuk be, hogy tetszőleges $\displaystyle N$ pozitív egész számhoz lehet találni olyan $\displaystyle n>2$ pozitív egész számot, hogy az $\displaystyle n^3-1$ bármely két különböző prímtényezőjének legalább $\displaystyle N$ legyen a különbsége.

(7 pont)

A beküldési határidő 2025. június 10-én LEJÁRT.

Tudjuk, hogy $\displaystyle n^3-1=(n-1)(n^2+n+1)$. $\displaystyle n$ helyett $\displaystyle n=m+1$-et írva $\displaystyle n^3-1=m(m^2+3m+3)$. Az $\displaystyle m^2+3,+3$ tényezőt vizsgálva

$$\begin{align*} (m^2-3m+3)(m^2+3m+3)&=m^4-3m^2+9\\ (m^2+3)(m^4-3m^2+9)&=m^6+27\\ (m^6+27)(m^6-27)&=m^{12}-3^6. \end{align*}$$

Tehát $\displaystyle m^2+3m+6$ osztja az $\displaystyle m^{12}-3^6$-t. Legyen $\displaystyle m=3^\alpha$, és tegyük fel, hogy $\displaystyle p\neq 3$ osztja $\displaystyle m^2+3m+3$-at. Ekkor $\displaystyle m^{12}\equiv 3^6$ modulo $\displaystyle p$, tehát $\displaystyle 3^{12\alpha}\equiv 3^{6}$ mod $\displaystyle p$, vagyis ha $\displaystyle d$ jelöli a 3 rendjét mod $\displaystyle p$, akkor $\displaystyle d|12\alpha-6$. Ezután legyen $\displaystyle 2\alpha-1=3^\beta$. Így $\displaystyle d$ osztja $\displaystyle 2\cdot 3^{\beta+1}$, így $\displaystyle d=3^\gamma$ vagy $\displaystyle d=2\cdot 3^\gamma$. Most megmutatjuk, hogy $\displaystyle \gamma=\beta+1$. Tegyük fel indirekt módon, hogy $\displaystyle \gamma\le \beta$.
1.eset: $\displaystyle d=3^\gamma$. Ekkor $\displaystyle d$ osztja $\displaystyle 2\alpha-1$-t, tehát $\displaystyle 3^{2\alpha-1}\equiv 1$ mod $\displaystyle p$. Ekkor $\displaystyle d|2\alpha-1$, így $\displaystyle 3^{2\alpha-1}\equiv 1$ mod $\displaystyle p$. Ekkor pedig

$\displaystyle m^2+3m+3\equiv 3^{2\alpha}+3^{\alpha+1}+3\equiv 3+3^{\alpha+1}+3\,\text{mod}\,p. $

így tehát $\displaystyle 3^{\alpha}\equiv -2$ mod $\displaystyle p$, vagyis $\displaystyle 3^{2\alpha}\equiv 4$ mod $\displaystyle p$, de ez lehetetlen, hiszen azt is láttuk, hogy $\displaystyle 3^{2\alpha}\equiv 3$ mod $\displaystyle p$.
2. eset: $\displaystyle d=2\cdot 3^\gamma$. Ekkor $\displaystyle p|3^d-1=(3^{d/2}-1)(3^{d/2}+1)$, es mivel 3 rendje $\displaystyle d$, ezért $\displaystyle p$ csak a második tényezőt oszthatja, azaz $\displaystyle 3^{d/2}\equiv -1$ mod $\displaystyle p$. Ekkor pedig $\displaystyle 3^{2\alpha-1}=3^{3^\beta}=(3^{3^\gamma})^{3^{\beta-\gamma}}$ miatt $\displaystyle 3^{2\alpha-1}\equiv -1$ mod $\displaystyle p$. Ekkor pedig

$\displaystyle m^2+3m+3\equiv 3^{2\alpha}+3^{\alpha+1}+3^{\alpha+1}+3\equiv -3+3^{\alpha+1}+3\equiv 3^{\alpha+1}\,\text{mod}\,p, $

ami ellentmondás. Így beláttuk, hogy $\displaystyle 3^{\beta+1}|d$. Mivel a kis-Fermat tétel miatt $\displaystyle d|p-1$, így $\displaystyle p$ osztható $\displaystyle 3^{\beta+1}$-gyel, vagyis minden $\displaystyle 3$-tól különböző prímosztó 1 maradékot ad $\displaystyle 3^{\beta+1}$-gyel osztva, tehát bármely két prímosztó különbsége legalább $\displaystyle 3^{\beta+1}-2$, és ezzel a feladatot megoldottuk.

Statisztika:

Az A. 909. feladat értékelése még nem fejeződött be.

A KöMaL 2025. májusi matematika feladatai

Már regisztráltál?
Új vendég vagy?