orde op zaken stellen

Opgave - reeks 2 2012 dag 1 vraag 3

$(a)$ Zij $n>1$ een natuurlijk getal en $a \in \mathbb Z$ zodat $n|a^n -1.$
Bewijs dat de kleinste priemdeler van $n$ een deler van $a-1$ is.
$(b)$ Vind alle natuurlijke $n$ $n^2|3^n+1$

Oplossing

(a) Zij $p$ de kleinste priemdeler van $n$ en $q$ de orde van $a$ modulo $p$.
Dan geldt $q|p-1$ wegens de kleine stelling van Fermat en $q|n$ omdat $a^n\equiv1\pmod p$.
maar $q\leq p-1$ en $p$ was de kleinste deler van $n$ groter dan $1$. Dan moet $q=1$, dus $a\equiv1\pmod p$ wat het gevraagde bewijst.

(b) $n=1$ voldoet al.
Stel nu $n>1$.
We hebben $n|9^n-1$ dus wegens (a) hebben we $2|n$. Stel $n=2m$.
Dan moet $4|9^m+1$ maar $9^m+1\equiv1+1=2\pmod4$. $n>1$ is dus onmogelijk.