Zsigmondy \to \infty nog'ns?

Opgave - IMO 1990 dag 1 vraag 3

Bepaal alle gehele getallen $n > 1$, zodanig dat $\frac{2^n+1}{n^2}$ een geheel getal is.

Oplossing

$n=1$ is een oplossing. Stel nu dat $n\ge 2$

Zij $p$ de kleinste priemdeler van $n$. Dan is $2^{2n}\equiv 1 \mod {p}$ en $2^{p-1}\equiv 1 \mod {p}$ wegens de kleine stelling van Fermat. Zij $\omega$ de orde van $2 \mod{p}$. Dan is $\omega\mid \text{ggd}(2n,p-1)$ en dit laatste is gelijk aan $2$ aangezien $p-1$ even is en $\text{ggd}(n,p-1)=1$. $\omega$ is dus gelijk aan $1$ of $2$. Als $\omega=1$, dan is $p\mid 2^1-1=1$, wat niet kan. Als $\omega=2$ dan is $p\mid 2^2-1=3$ dus $p=3$

Merk op dat $n$ oneven is, aangezien $2^n+1$ altijd oneven is. Volgens Lifting the exponent hebben we dan dat $v_3(2^n+1)=v_3(2+1)+v_3(n)=1+v_3(n)$. We hebben ook dat $v_3(n^2)=2v_3(n)$. Dit laatste echter moet kleiner of gelijk aan dit eerste zijn, dus $2v_3(n)\le 1+v_3(n) \Leftrightarrow v_3(n)\le 1$ dus $v_3(n)=1$.

Stel nu $n=3k$ met $3\nmid k$. Dan is $9k^2\mid 2^{3k}+1=8^k+1$. Zij $q$ de kleinste priemdeler van $k$. Dan is $64^k\equiv 1 \mod{q}$ en $64^{q-1}\equiv 1 \mod{q}$ (Fermat en $ggd(q,2)=1$ ). Zij $\delta$ de orde van $64$ $\mod q$. Dan is $\delta\mid \text{ggd}(k,q-1)=1$ zodanig dat $\delta=1$. Dit betekent dat $q\mid 64-1=63$ dus $q=3$ of $q=7$. Het eerste is onmogelijk wegens bovenstaande opmerkingen, dus $q=7$. Dit betekent dat $7\mid 2^n+1$.

Maar $2^n+1 \equiv 2,3,5 \pmod 7$ zodat $q=7$ niet kon, bijgevolg is $k=1$ en waren de enige mogelijke oplossingen $n=1$ en $3$.