kleine stelling van fermat

[boejjuh]

Okay.. ik heb een opgave, die ik echt TOTAAL niet volg
de opgave:

Gebruik de kleine stelling van Fermat om de resten van 2^2002
bij deling door 2,3,7,11 en 15 te bepalen.

en hier een stukje over de kleine stelling van Fermat:

De wiskundige basis voor het functioneren van RSA is 
de Kleine Stelling van Fermat, die zegt dat voor een priemgetal p
en een geheel getal a dat geen veelvoud is van p geldt, 
dat a^(p-1) rest 1 geeft bij deling door p. 
Hieruit konden we namelijk concluderen dat voor priemgetallen p en q, 
een coderingsmacht e met ggd(e, (p-1)(q-1)) = 1 
en een decoderingsmacht d met d*e = 1 modulo p*q geldt,
dat (X^e)^d = X modulo p*q is.

maaruh.. zover kom ik dan:
p =3
A = 2^2002

dan: (2^2002)^2 geeft rest 1 bij deling door 3,
maarja.. dan weet je toch nog niet hoeveel rest 2^2002 geeft bij deling door 3??

iemand die dit misschien wel snapt?

[mathfreak]

Een oneven macht van 2 geeft een rest 2 bij deling door 3 en een even macht van 2 geeft een rest 1 bij deling door 3. Omdat 2²⁰⁰² een even macht van 2 is zal dit dus een rest 1 bij deling door 3 opleveren.

[boejjuh]

mathfreak schreef:
Een oneven macht van 2 geeft een rest 2 bij deling door 3 en een even macht van 2 geeft een rest 1 bij deling door 3. Omdat 2²⁰⁰² een even macht van 2 is zal dit dus een rest 1 bij deling door 3 opleverenl.

ja dat weet jij toevallig,
maar hoe maak ik dan gebruik van die stelling van Fermat?

want ik moet het dus ook weten bij deling door 5,7,11 en 15..

[mathfreak]

boejjuh schreef:
ja dat weet jij toevallig,
maar hoe maak ik dan gebruik van die stelling van Fermat?

want ik moet het dus ook weten bij deling door 5,7,11 en 15..

Laten we de stelling eens bekijken: als p priem is en a geen veelvoud van p, dan geldt:
a^p-1=1 mod p. We hebben a=2²⁰⁰². Omdat a geen veelvoud is van 5 geldt: a⁴=2⁸⁰⁰⁸=1 mod 5. Laten we eens kijken of dat klopt. Er geldt: 2^4*n+1=2 mod 5, 2^4*n+2=4 mod 5, 2^4*n+3=3 mod 5, 2^4*n=1 mod 5 met n geheel. Voor n=500 vinden we: a=2²⁰⁰²=4 mod 5. Er geldt: a⁴=2⁸⁰⁰⁸=4⁴ mod 5=2⁸ mod 5=1 mod 5, wat overeenkomt met wat de stelling ons vertelde.
Omdat a geen veelvoud is van 7 geldt: a⁶=2¹²⁰¹²=1 mod 7. Laten we eens kijken of dat klopt. Er geldt: 2^3*n+1=2 mod 7, 2^3*n+2=4 mod 7, 2^3*n=1 mod 7 met n geheel. Voor n=667 vinden we: a=2²⁰⁰²=2 mod 7. Er geldt: a⁶=2¹²⁰¹²=2⁶ mod 7=1 mod 7, wat overeenkomt met wat de stelling ons vertelde.
Omdat a geen veelvoud is van 11 geldt: a¹⁰=2²⁰⁰²⁰=1 mod 11. Laten we eens kijken of dat klopt. Er geldt: 2^10*n+1=2 mod 11, 2^10*n+2=4 mod 11, 2^10*n+3=8 mod 11, 2^10*n+4=5 mod 11, 2^10*n+5=10 mod 11, 2^10*n+6=9 mod 11, 2^10*n+7=7 mod 11, 2^10*n+8=3 mod 11, 2^10*n+9=6 mod 11, 2^10*n=1 mod 11 met n geheel. Voor n=200 vinden we: a=2²⁰⁰²=4 mod 11. Er geldt: a¹⁰=2²⁰⁰²⁰=2⁴⁰ mod 11=1 mod 11, wat overeenkomt met wat de stelling ons vertelde.
Omdat 15 niet priem is kunnen we de stelling niet toepassen, maar we kunnen wel kijken hoe het zit met machten van 2 modulo 15. Er geldt: 2^4*n+1=2 mod 15, 2^4*n+2=4 mod 15, 2^4*n+3=8 mod 15, 2^4*n=1 mod 15. Voor n=500 vinden we: a=2²⁰⁰²=4 mod 15, dus de rest van 2²⁰⁰² bij deling door 15 is 4.

[boejjuh]

mathfreak schreef:
Laten we de stelling eens bekijken: als p priem is en a geen veelvoud van p, dan geldt:
a^p-1=1 mod p. We hebben a=2²⁰⁰². Omdat a geen veelvoud is van 5 geldt: a⁴=2⁸⁰⁰⁸=1 mod 5. Laten we eens kijken of dat klopt. Er geldt: 2^4*n+1=2 mod 5, 2^4*n+2=4 mod 5, 2^4*n+3=3 mod 5, 2^4*n=1 mod 5 met n geheel. Voor n=500 vinden we: a=2²⁰⁰²=4 mod 5. Er geldt: a⁴=2⁸⁰⁰⁸=4⁴ mod 5=2⁸ mod 5=1 mod 5, wat overeenkomt met wat de stelling ons vertelde.
Omdat a geen veelvoud is van 7 geldt: a⁶=2¹²⁰¹²=1 mod 7. Laten we eens kijken of dat klopt. Er geldt: 2^3*n+1=2 mod 7, 2^3*n+2=4 mod 7, 2^3*n=1 mod 7 met n geheel. Voor n=667 vinden we: a=2²⁰⁰²=2 mod 7. Er geldt: a⁶=2¹²⁰¹²=2⁶ mod 7=1 mod 7, wat overeenkomt met wat de stelling ons vertelde.
Omdat a geen veelvoud is van 11 geldt: a¹⁰=2²⁰⁰²⁰=1 mod 11. Laten we eens kijken of dat klopt. Er geldt: 2^10*n+1=2 mod 11, 2^10*n+2=4 mod 11, 2^10*n+3=8 mod 11, 2^10*n+4=5 mod 11, 2^10*n+5=10 mod 11, 2^10*n+6=9 mod 11, 2^10*n+7=7 mod 11, 2^10*n+8=3 mod 11, 2^10*n+9=6 mod 11, 2^10*n=1 mod 11 met n geheel. Voor n=200 vinden we: a=2²⁰⁰²=4 mod 11. Er geldt: a¹⁰=2²⁰⁰²⁰=2⁴⁰ mod 11=1 mod 11, wat overeenkomt met wat de stelling ons vertelde.
Omdat 15 niet priem is kunnen we de stelling niet toepassen, maar we kunnen wel kijken hoe het zit met machten van 2 modulo 15. Er geldt: 2^4*n+1=2 mod 15, 2^4*n+2=4 mod 15, 2^4*n+3=8 mod 15, 2^4*n=1 mod 15. Voor n=500 vinden we: a=2²⁰⁰²=4 mod 15, dus de rest van 2²⁰⁰² bij deling door 15 is 4.

klopt allemaal wel,
maar wat je nu dus doet,
is de rest bepalen van 2^8008 bij deling door 5,
maar ik moet dus de rest van 2^2002 bepalen bij deling door 5..

daarom snap ik ook heel het nut van die stelling niet?

[mathfreak]

boejjuh schreef:
klopt allemaal wel,
maar wat je nu dus doet,
is de rest bepalen van 2^8008 bij deling door 5,
maar ik moet dus de rest van 2^2002 bepalen bij deling door 5..

daarom snap ik ook heel het nut van die stelling niet?

De rest van 2²⁰⁰² bij deling door 5 is 4, want er geldt: 2^4*n+2=4 mod 5 en 2²⁰⁰² is voor n=500 van de vorm 2^4*n+2, wat dus bij deling door 5 een rest 4 oplevert. De stelling kan worden gebruikt om te controleren of een gegeven getal a geen veelvoud is van een gegeven priemgetal p. Indien dat niet zo is moet namelijk gelden: a^p-1=1 mod p. Voor a=2²⁰⁰² en p=5 klopt dit, want a=4 mod 5 en a^5-1=a⁴=4⁴ mod 5=2⁸ mod 5=2^4*2 mod 5=1 mod 5 en 2²⁰⁰² is geen veelvoud van 5.

[boejjuh]

mathfreak schreef:
want er geldt: 2^4*n+2=4 mod 5 en 2²⁰⁰² is voor n=500 van de vorm 2^4*n+2,

die eerste zin... dat kon ik niet weten toch?
want dat staat niet in mijn stukje over die stelling..

hoe verwachten ze dan ooit van mij dat ik die som op kan lossen

[mathfreak]

boejjuh schreef:
die eerste zin... dat kon ik niet weten toch?
want dat staat niet in mijn stukje over die stelling..

hoe verwachten ze dan ooit van mij dat ik die som op kan lossen

Je kunt het wel afleiden. Wat ik deed om de rest bij deling door 5 van een macht van 2 te vinden was de machten van 2 modulo 5 bepalen. Het blijkt dat er een regelmaat in de rij zit. Kijk maar eens naar de rijen met machten van 2 modulo 5, 7 en 11 die ik gaf en probeer het zelf maar eens uit, dan zul je die regelmaat vanzelf ontdekken. Het is in dat verband misschien wel een goed idee om even de volgende hulpstelling te vermelden:
a=b mod m=>aⁿ=bⁿ mod m. In feite is dat de regel die ik in mijn tweede reply (en ook in mijn vorige) toepaste om de juistheid van de stelling te controleren.