matematikk.net

[tex]p\mid 2^n -1, p\mid 2^{p-1}-1[/tex] dette impliserer at [tex]p\mid 2^d-1[/tex] d=gcd(n,p-1) hvorfor?

edit: Kan legge til at jeg prøver å forstå et bevis og selvet beviset hoppet over denne implikasjonen.

[tex]p | 2^n - 1[/tex] og [tex]p|2^{p-1}-1[/tex] er det samme som
[tex]2^n-1\equiv 0 \pmod p[/tex] og [tex]2^{p-1}-1\equiv 0 \pmod p[/tex], som igjen er det samme som
[tex]2^n \equiv 1 \pmod p[/tex] og [tex]2^{p-1} \equiv 1 \pmod p[/tex]

Det er vanlig å skrive p for primtall. Er p et primtall her?

I så fall vet vi fra Eulers teorem, [tex]a^{\phi(n)} \equiv 1 \pmod n[/tex], hvis [tex]gcd(a,n)=1[/tex], at [tex]p-1[/tex] er ordenen til den multiplikative gruppen modulo p, siden [tex]\phi(p)=p-1[/tex], gitt at [tex]p\neq 2[/tex].
Siden [tex]p-1[/tex] er ordenen, så er det også det laveste positive tallet som gir 1 (mod p). n må derfor være en multippel av [tex]p-1[/tex], hvis den også gir 1 (mod p).

I det tilfellet er resultatet trivielt siden [tex]d = gcd(k(p-1),p-1) = p-1[/tex].

Ja p er et primtall, tenkte ikke på at p-1 var den laveste potensen som opfyller [tex]2^n=1 (mod p)[/tex]

takk så mye for svaret