matematikk.net

1) la [tex]a \in \mathbb{N}[/tex] og [tex]p \in \mathbb{P}[/tex] være slik at [tex]p \not | a[/tex]
2) [tex]a^{p-1} \equiv 1 \bmod{p}[/tex] (Allerede bevist.)
3) la [tex]e \in \mathbb{N}[/tex] være det minste [tex]e[/tex] som er slik at [tex]a^e \equiv 1 \bmod{p}[/tex]

Bevis at [tex]e|(p-1)[/tex].


Vi utfører divisjonen [tex]\frac{p-1}e = k + \frac re[/tex], [tex]\,\,\,\,k,r \in \mathbb{N}[/tex] og [tex]0 \leq r < e[/tex]

[tex]p-1 = ke + r[/tex]. Det må altså bevises at [tex]r = 0[/tex].

Av 2) har vi at [tex]a^{ke+r} \equiv 1 \bmod{p}[/tex]

[tex](a^e)^k\cdot a^r \equiv 1 \bmod p[/tex]

[tex]1\cdot a^r \equiv 1 \bmod p[/tex] (av 3) )

[tex]a^r \equiv 1 \bmod p[/tex]. Av 1) har vi at [tex]a \not \equiv 0 \bmod p[/tex], som medfører at [tex]r = 0[/tex].


Holder dette vann?

Hva med a=2, p=3 ?

da vil 2^r=1 mod(3) ikke implisere at r =0 siden r=2 gir 2^2=4=1 mod(3)

edit: men dette stemmer ikke med kravet om at r<e, så det gjelder vel ikke

: D