Bewijs modulo

[Beau96]

Hi All.

voor een opdracht moet ik bewijzen dat

a^7 = a mod 7.

buiten dat 7 een priemgetal is weet ik hier niet verder door te geraken. Iemand die me toevallig een beetje zou kunnen helpen?

Groetjes!

[Xilvo]

2^7 = 128
2 mod 7 = 2
Die zijn dus niet gelijk.

Maar misschien begrijp ik je verkeerd.

[Beau96]

2^7 = 128
2 mod 7 = 2
Die zijn dus niet gelijk.

Maar misschien begrijp ik je verkeerd.

Hii! ik snap hoe de modulo tot stand komt zegmaar (want 2 is de ''rest'') maar snap niet hoe ik dit kan bewijzen.

[Beau96]

het = tekentje moet een ≡ zijn

[mathfreak]

2^7 = 128
2 mod 7 = 2
Die zijn dus niet gelijk.

Maar misschien begrijp ik je verkeerd.

Als je weet dat 126 ≡ 0 mod 7 geldt wel dat 2⁷ ≡ 2 mod 7, dus voor a = 2 klopt het in ieder geval.

@Beau96: Maak gebruik van volledige inductie. Voor a = 1 is de bewering in ieder geval juist. Veronderstel dat de bewering juist is voor a = k. Laat dan zien dat de bewering ook juist is voor a = k+1. Daarmee is de juistheid voor alle waarden van a bewezen.

[Beau96]

oke top, dankjewel! stel je zou dit met een groter getal zoals 29 doen in plaats van 7, hoe kan je het dan bewijzen?

[RedCat]

Je wil nu algemener bewijzen:
a^p ≡ a mod p
voor alle priemgetallen p.

Als je dit voor p=7 met volledige inductie hebt bewezen (zoals mathfreak aangaf),
dan moet dit ook lukken voor p=29.

Indien je het bewijs hebt gegeven door a^7 mod 7 uit te rekenen voor a=0 t/m a=6,
dan wordt het bewijs voor p=29 inderdaad lastiger (en voor nog grotere priemgetallen
nog lastiger, en voor priemgetallen in het algemeen onmogelijk).

We volgen dus beter het advies van mathfreak, en geven een bewijs via volledige inductie:

Basisstap:
a=0:
0^p = 0 ≡ 0 mod p
(en ook a=1 zie je zo: 1^p = 1 ≡ 1 mod p)

Inductiehypothese:
stel voor a=k geldt:
k^p ≡ k mod p

Inductiestap:
Werk eerst (k+1)^p uit met het binomium van Newton:

\((k+1)^p = {p \choose 0}k^0 +{p \choose 1}k^1 + {p \choose 2}k^2 + {p \choose 3}k^3 + ... + {p \choose p-1}k^{p-1} + {p \choose p}k^p\)

Welke van al de binomiaalcoefficienten in deze gelijkheid zijn deelbaar door p (en waarom)?
Hoe komen we daarmee verder?

[Bart23]

Neem een priemgetal p.
Bekijk het rijtje getallen 1,2,3,...,p-1
Neem nu een natuurlijk getal a. Als a een p-voud is, dan is het gevraagde vanzelfsprekend. Stel dus dat a geen veelvoud van p is.
Vermenigvuldig nu elk getal van het bovenstaande rijtje met a:
a,2a,3a,....,(p-1)a
Elk van deze p-1 getallen heeft een andere rest bij deling door p. Immers, stel dat ma en na dezelfde rest hebben bij deling door p, dan is ma-na=(m-n)a een p-voud. Maar a is geen p-voud (zie boven), dan moet m-n een p-voud zijn. Maar m en n zijn kleiner dan p, dan kan alleen m-n=0, of m=n.
We concluderen dat als we de rest bij deling door p nemen, de getallen in a,2a,3a,....,(p-1)a dezelfde zijn als in 1,2,3,...,p-1, maar mogelijk in een andere volgorde.
Als we de elementen in beide rijen vermenigvuldigen, moeten ze dus ook dezelfde rest geven.
Dus: 1.2.3....(p-1)=a.2a.3a....(p-1)a (mod p) = a^(p-1).1.2.3...(p-1) (mod p)
Dus is 1.2.3....(p-1).(a^(p-1)-1) een p-voud, dus is a^(p-1)=1 (mod p), dus is a^p=a (mod p)

Het kan nog een stuk ingekort worden als je iets weet van eindige lichamen, maar daar ben ik niet van uitgegaan.