Hét vraag- en antwoordplatform van Nederland

Kan iemand dit stukje uit de kleine stelling van Fermat uitleggen?

(https://www.win.tue.nl/~jessers/aansluiting/bewijsFermat.htm) Op deze website vind je een bewijs van de kleine stelling van Fermat, maar ik snap niet wat men bedoelt met 'Je kunt dus alleen maar 3*i ≡ 3*j (mod 7) krijgen als i ≡ j (mod 7)'.

Verwijderde gebruiker
6 jaar geleden
in: Wiskunde
2.4K
Verwijderde gebruiker
6 jaar geleden
Betekent het niet gewoon wat er staat? In het tabelletje erboven: 1*3 = 3 (mod 7)
2*3 = 6 (mod 7)
3*3 = 2 (mod 7)
4*3 = 5 (mod 7)
5*3 = 1 (mod 7)
6*3 = 4 (mod 7) Die zijn dus allemaal verschillend. En als je dus bijvoorbeeld i=4 neemt, dan is i*3 = 4*3 = 12 = 5 (mod 7), en als je alle mogelijke waarden van j bekijkt, zul je er maar één vinden die ook 5 oplevert, en dat is 4. Alles mod 7, dus 11 doet het ook. En 18 ook...
Nou ja, en dat is gewoon wat er staat.

Heb je meer informatie nodig om de vraag te beantwoorden? Reageer dan hier.

Antwoorden (1)

Wat ze bedoelen is het volgende:
De drie horizontale strepen betekend niet is gelijk aan, maar is congruent aan. Het is belangrijk om het subtiele verschil hiertussen goed te begrijpen en niet door elkaar te halen.

Het houdt ongeveer het volgende in: 4 mod 3 = 1 zou je zeggen? Dat klopt strikt genomen niet, en waarschijnlijk wordt dit ook fout gerekend door je professor. Echter, 4 mod 3 ≡ 1 klopt wel. 4 mod 3 ≡ 1 betekend namelijk eigenlijk: 4 mod 3 = 1 mod 3 wat wel klopt (als je dus bij het =-teken mod 3 achter de 1 had gezet had het wel geklopt). 4 is dus gelijk aan 1, mits je beide in mod 3 rekent. Dat is ook precies de basis van het statement wat er gemaakt wordt.

Wat er dus geprobeerd te zeggen wordt op de pagina is dat als je 3 * i ≡ 3 * j mod 7 hebt, dat het dan per se zo moet zijn dat i ≡ j mod 7.

Een voorbeeld maakt als snel duidelijk waarom dit zo is. Stel i = 5 en j = 12
(dus i ≡ j mod 7) want 5 mod 7 ≡ 5 en 12 mod 7 ≡ 5.

Omdat je dus in, bijvoorbeeld, mod 7 werkt maakt het vervolgens niet uit met hoeveel je de getallen vermenigvuldigd als i en j al eigenlijk hetzelfde zijn (d.w.z. congruent mod 7).

Kort gezegd, als i en j in de modulus waarin je werkt hetzelfde zijn (congruent) maakt het natuurlijk niet uit keer hoeveel je een getal doet, als de getallen 'hetzelfde' zijn blijven ze daarna ook altijd hetzelfde als je ze vermenigvuldigd met hetzelfde getal. In jouw voorbeeld geven ze het andersom. Als iets *3 hetzelfde is als iets anders *3 in een bepaalde modulus moeten de getallen dus hetzelfde zijn in die modulus. Net zoals bij 3i = 3j i en j hetzelfde getal moeten zijn om correct te zijn.

Source: masterstudent Cyber Security aan de TUE & RU
(Lees meer...)
Verwijderde gebruiker
6 jaar geleden

Weet jij het beter..?

Het is niet mogelijk om je eigen vraag te beantwoorden Je mag slechts 1 keer antwoord geven op een vraag Je hebt vandaag al antwoorden gegeven. Morgen mag je opnieuw maximaal antwoorden geven.

0 / 5000
Gekozen afbeelding