WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\require{AMSmath}

Modulo rekenen

Beste wisfaq, ik moet de congruentie x¹¹ = 9 (mod 11) gebruik makende van het feit dat 3 een 'primitive root' modulo 17 is.

Ik heb geen idee hoe deze vergelijking op te lossen met dit gegeven. Ik heb al oplossingen gevonden door gebruik te maken van Fermat's kleine stelling en door simpelweg de vergelijking te checken door simpelweg een element uit elk van de restklassen 0,1,2, ... , 10 to substituteren.

Het grootste probleem waar ik tegenaan loop is het feit dat 3 een primitive root modulo 17 is (en niet modulo 11). Ik hoop dat jullie me hiermee kunnen helpen. Bij voorbaat dank,

Herman
Herman
Student universiteit - dinsdag 5 mei 2009

Antwoord

Volgens de kleine stelling van Fermat is x¹⁰ = 1 (mod 11) als x¹ 0 (mod 11), en in alle gevallen x¹¹ = x (mod 11).
Dus de oplossing van x¹¹ = 9 (mod 11) is x = 9 (mod 11), en de 11 substituties die u voorstelt zijn overbodig.

Ik denk dat er een lees- of schrijffout heeft plaatsgevonden, en dat u de congruentie x¹¹ = 9 (mod 17) moet oplossen. Het feit dat 3 een primitieve wortel modulo 17 is (dat is correct) heeft dan zin.
Elke restklasse x (mod 17) (behalve 0 (mod 17)) is dus te schrijven als 3^k(mod 17) voor een of andere kÎ{1,2,..,16}. Verder is 3^k+16m(mod 17) = 3^k(mod 17) voor mÎ omdat 3¹⁶(mod 17) = 1 (mod 17).
Dus x¹¹ (mod 17) = 3^11k (mod 17) = 9 (mod 17) precies dan als 11k = 2 (mod 16), dus als k = 6 (mod 16), dus als x (mod 17) = 3⁶ (mod 17) = 15 (mod 17).

Vragen naar aanleiding van dit antwoord? Klik rechts..!
woensdag 6 mei 2009