[wi]modulo rekenen

In het kader van de getaltheorie de volgende vraag:

Bewijs dat voor alle x uit Z geldt:

x^7 = x mod 42

Hier zijn volgens mij Euler's phi-functie, de kleine stelling van Fermat van belang en het feit dat 42 = 2*3*7. Ik kom er echter niet helemaal uit.

[mathfreak]

phi12345 schreef op 24-04-2005 @ 15:35 :
In het kader van de getaltheorie de volgende vraag:

Bewijs dat voor alle x uit Z geldt:

x^7 = x mod 42

Hier zijn volgens mij Euler's phi-functie, de kleine stelling van Fermat van belang en het feit dat 42 = 2*3*7. Ik kom er echter niet helemaal uit.

De vergelijking is gelijkwaardig met x⁷-x=0 mod 42, dus x⁶(x-1)=0 mod 42. Het is duidelijk dat x=0 mod 42 of x=1 mod 42 beide voldoen. Bepaal phi(42)=42*1/2*2/3*6/7=42*1/3*6/7=42*2/7=12, en bepaal nu alle a
met ggd(a,42)=1, zodat [a]₄₂ een priemrestklasse modulo 42 is, dan moet voor x=a aan de vergelijking worden voldaan.

Ik begrijp niet helemaal wat je nu op het laatst aan het doen bent. Ik moet bewijzen dat de functie voor alle gehele getallen geldt. Kun je, vanaf de phi-functie, nog eens aangeven wat je waarom aan het doen bent? Bedankt

[mathfreak]

phi12345 schreef op 24-04-2005 @ 20:04 :
Ik begrijp niet helemaal wat je nu op het laatst aan het doen bent. Ik moet bewijzen dat de functie voor alle gehele getallen geldt. Kun je, vanaf de phi-functie, nog eens aangeven wat je waarom aan het doen bent? Bedankt

Wat ik doe is gebruik maken van het volgende: als m een gegeven getal is kun je een restklassengroep modulo m bepalen. Door je nu te beperken tot die restklassen die een a bevatten met de eigenschap ggd(a,m)=1 hou je de priemrestklassen [a]_m over. Het blijkt dat deze priemrestklassen onder de operatie vermenigvuldiging modulo m een abelse groep vormen die de orde phi(m) heeft. Omdat phi(42) gelijk is aan 12 vind je dus 12 getallen a met de eigenschap ggd(a,m)=1. Voor al deze getallen moet gelden dat ze aan de gegeven vergelijking voldoen. Voor alle overige getallen kun je gebruik maken van het feit dat de Eulerfunctie phi voor ggd(a,b)=1 de eigenschap phi(a*b)=phi(a)*phi(b) heeft. Waar het om gaat is dat Z door een bewerking modulo m automatisch in een restklassenverzameling modulo m opgedeeld wordt. Je hoeft je dus per restklasse maar tot 1 element uit die restklasse te beperken, aangezien alle andere elementen in die restklasse dezelfde eigenschappen bezitten.

Bedankt voor de uitleg, Mathfreak. Voor de geinteresseerde: dit probleem is nauw verbonden aan de zogenaamde Chinese Reststelling.

[mathfreak]

phi12345 schreef op 29-04-2005 @ 00:28 :
Bedankt voor de uitleg, Mathfreak.

Graag gedaan. Overigens dien ik hier volledigheidshalve aan toe te voegen dat ik dit wel op heb moeten zoeken, aangezien mijn eigen wiskundige interesse zich hoofdzakelijk beperkt tot de analyse en de aanverwante deelgebieden.

phi12345 schreef op 29-04-2005 @ 00:28 :
Voor de geinteresseerde: dit probleem is nauw verbonden aan de zogenaamde Chinese Reststelling.

Voor digenen die die stelling niet kennen noem ik deze hier even: laat m₁, m₂,...m_n gegeven zijn met ggd(m_i,m_j)=1 voor i ongelijk j en beschouw het stelsel x=b₁ mod m₁, x=b₂ mod m₂,..., x=b_n mod m_n. Stel m=m₁*m₂*...*m_n, a_i=m/m_i en a_i*x_i=b_i mod m_i voor i=1 t/m n, dan is x'=a₁*x₁+a₂*x₂+...+a_n*x_n
een oplossing van het gegeven stelsel.
Via x' kan een andere oplossing x''=x' mod m worden gevonden.