Omvendt Fermat

[Gustav]

La $p$ være et primtall. Vis at dersom $x^k\equiv 1(\mathrm{mod}p)$ for alle $x\not\equiv 0(\mathrm{mod}p)$, så vil $p-1$ dele $k$.

[Janhaa]

La $p$ være et primtall. Vis at dersom $x^k\equiv 1(\mathrm{mod}p)$ for alle $x\not\equiv 0(\mathrm{mod}p)$, så vil $p-1$ dele $k$.

her er jeg ikke sikker, men:
har:
$gcd(k,p-1)$
der
$d=gcd(k,p-1)$
=>
$d=k\cdot u+(p-1)\cdot v$
u og v er kontanter.
deretter:
$x^d=(x^k{)}^u\cdot (x^{p-1}{)}^v$
=>
$x^k=1$
=>
$x^d=1$
=>da vil
$d|k$
og
$p-1|k$
?

[mingjun]

Gitt at $or{d}_p(x)|p-1$ for alle $x\not\equiv 0$, trenger vi kun å vise at det finnes et tall $x$ slik at $or{d}_p(x)=p-1$. Men gitt at det alltid eksisterer primitive røtter modulo et primtall, er vi ferdige.

[Gustav]

Gitt at $or{d}_p(x)|p-1$ for alle $x\not\equiv 0$, trenger vi kun å vise at det finnes et tall $x$ slik at $or{d}_p(x)=p-1$. Men gitt at det alltid eksisterer primitive røtter modulo et primtall, er vi ferdige.

Jepp, hadde en forholdsvis lik løsning: Skriv $k=n(p-1)+d$ der $0\le d<p-1$. Fra Fermats lille teorem vil $x^k=x^{n(p-1)+d}=(x^{p-1}{)}^n\cdot x^d\equiv x^d\equiv 1$. Anta $d>0$. Siden den multiplikative gruppen $Z_p^{\times }$ er syklisk fins et element $g$ som genererer gruppa, men siden $g^d=1$, så får vi motsigelsen. Dermed må $d=0$ og $k=n(p-1)$, så $p-1|k$.