Test de primalité de Lucas

[744]

Bonjour à tous
J'ai trouvé la démonstration du test de primalité de Lucas-Lehmer sur internet (qui dit :
si a est premier avec n, que a^(n-1) est congru à 1 modulo n, et que pour tout diviseur premier q de (n-1), a^((n-1)/q) n'est pas congru à 1 modulo n, alors n est premier)
, ainsi que sa réciproque, mais je ne les comprends pas.

J'ai vu écrit dans ces démonstrations : "L'ordre de a dans le groupe (Z/nZ)* est égal à n-1"
Je comprends pourquoi il divise n-1, mais pas pourquoi il lui est exactement égal ?!

Pouvez-vous m'aider ?

[cuati]

Bonjour à tous
J'ai trouvé la démonstration du test de primalité de Lucas-Lehmer sur internet (qui dit :
si a est premier avec n, que a^(n-1) est congru à 1 modulo n, et que pour tout diviseur premier q de (n-1), a^((n-1)/q) n'est pas congru à 1 modulo n, alors n est premier)
, ainsi que sa réciproque, mais je ne les comprends pas.

J'ai vu écrit dans ces démonstrations : "L'ordre de a dans le groupe (Z/nZ)* est égal à n-1"
Je comprends pourquoi il divise n-1, mais pas pourquoi il lui est exactement égal ?!

Pouvez-vous m'aider ?

Bonsoir,
tu l'as toi même écrit, si l'ordre de a, que je noterai o(a), n'est pas égal à (n-1) alors alors il existe un diviseur premier q de (n-1) tel que q divise et donc est un multiple de o(a) et donc a^((n-1)/q) devrait être congru à 1 modulo n, ce qui n'est pas par hypothèse...

[744]

Bonsoir,
tu l'as toi même écrit, si l'ordre de a, que je noterai o(a), n'est pas égal à (n-1) alors alors il existe un diviseur premier q de (n-1) tel que q divise et donc est un multiple de o(a) et donc a^((n-1)/q) devrait être congru à 1 modulo n, ce qui n'est pas par hypothèse...

Ah, oui, je crois que je vois. Si l'ordre n'est pas exactement (n-1), alors il existe un k divisant (n-1) (notons (n-1)=k*q) tel que soit congru à 1, c'est à dire a^ est congru à 1.
Mais le q en question n'est pas nécessairement premier ?!

[cuati]

Ah, oui, je crois que je vois. Si l'ordre n'est pas exactement (n-1), alors il existe un k divisant (n-1) (notons (n-1)=k*q) tel que soit congru à 1, c'est à dire a^ est congru à 1.
Mais le q en question n'est pas nécessairement premier ?!

Tu n'as pas tout à fait compris mon premier message... Tu peux choisir ce q premier quitte à "augmenter" un peu k...
Pour faire simple, avec tes notations : k est l'ordre de a, on suppose k<n-1 or k|n-1. Il existe donc un nombre m tel que km=n-1 et m possède lui même un diviseur premier q, m=qr par exemple. Donc n-1=kqr et (n-1)/q est un multiple de k, (n-1)/q=kr , on a donc aussi a^((n-1)/q)=a^(kr)=(a^k)^r=1.

[744]

Tu n'as pas tout à fait compris mon premier message... Tu peux choisir ce q premier quitte à "augmenter" un peu k...
Pour faire simple, avec tes notations : k est l'ordre de a, on suppose k<n-1 or k|n-1. Il existe donc un nombre m tel que km=n-1 et m possède lui même un diviseur premier q, m=qr par exemple. Donc n-1=kqr et (n-1)/q est un multiple de k, (n-1)/q=kr , on a donc aussi a^((n-1)/q)=a^(kr)=(a^k)^r=1.

Aaaaah ! Oui exact ! J'ai compris !
Merci beaucoup :we: