Re: Re: Primitieve wortel

Dit is een reactie op vraag 83540

2,5,7,10,14,35 zijn delers en dus ordes van 70.
Waarom is testen voor d=10,14 en 35 een voldoende voorwaarde en d=2,5 en 7 niet?
Ik waag nog een poging: je zou toch alle ordes moeten testen om te zien of 7 een primitieve wortel is?
Dank alvast voor uw reactie.

Herman
Ouder - donderdag 22 december 2016

Antwoord

Ik weet niet wat je met `orde van $70$' bedoelt maar de delers van $70$ zijn potentiele ordes van de getallen modulo $71$.
Een getal $a$ is een primitieve wortel als zijn orde precies $70$ is, dus $a^{70}=1\bmod 71$ maar voor $i=1$ tot en met $69$ is $a^i$ niet gelijk aan $1$ modulo $71$.
We weten: als $a^i=1\bmod 71$ dan is $i$ een deler van $70$ en we hoeven dus alleen voor $i=1,2,5,7,10,14,35$ te controleren dat $a^i$ niet $1$ is modulo $71$. Maar: als $a^{10}$ niet $1$ is dan zijn $a^2$ en $a^5$ het ook niet, als $a^{14}$ niet $1$ is dan zijn $a^2$ en $a^7$ het ook niet en als $a^{35}$ niet $1$ is dan zijn $a^5$ en $a^7$ het ook niet.
Om te zien of $a$ een primitieve wortel is hoef je dus alleen te laten zien dat $a^{10}$, $a^{14}$ en $a^{35}$ niet gelijk aan $1$ zijn modulo $1$.
Het geval $a=49$ laat zien dat $2$, $5$ en $7$ controleren niet voldoende is.

kphart
donderdag 22 december 2016

©2001-2024 WisFaq