Précision sur le théorème de Fermat-Euler

Par Mathous

Rappel Théorème Fermat-Euler

Rappelons ce théorème :

Théorème Fermat-Euler :

Soit nn un entier supérieur à 11, et ϕ(n)ϕ(n) (indicatrice d'Euler) le nombre d'entiers inférieurs à nn et premiers avec nn.

Pour tout entiera premier avec nn, on a aφ(n)1[n]a^{\varphi (n)} \equiv 1 [n].

Il en résulte que pour tout entier aa premier avec nn, on a aλφ(n)+1a[n]a^{\lambda \varphi(n)+1} \equiv a [n].

Ce théorème est utilisé en cryptographie, notamment pour le codage RSA.
Mais il impose que aa soit premier avec nn.

Qu'en est-il dans le cas contraire ?

Soit nn un entier (supérieur à 11), "quadratfrei"(c'est-à-dire sans facteur carré), et soit mm un entier tel que pour tout diviseur pp premier de nn on ait p1m1p - 1|m - 1.

Soit pp un diviseur premier de nn, et aa un entier quelconque.

  • ou bien aa est premier avec nn, auquel cas ap11[p]a^{p-1}\equiv 1 [p] (petit théorème de Fermat).

Donc am11[p]a^{m-1} \equiv 1 [p] puisque p1m1p - 1|m - 1.

Ceci étant vrai pour tout diviseur pp premier de nn, et nn n'ayant pas de diviseur carré, am11[n]a^{m-1} \equiv 1 [n].

Il en résulte de am11[p]a^{m-1} \equiv 1 [p] que ama[p]a^m \equiv a [p].

  • ou bien aa n'est pas premier avec pp, c'est donc un multiple de pp et a0[p]a \equiv 0 [p] .

Donc ap10[p]a^{p-1} \equiv 0 [p].

D'où am10[p]a^{m-1} \equiv 0 [p] puisque p1m1p - 1|m - 1.

Il en résulte que am0[p]a^m \equiv 0 [p], et donc ama[p]a^m \equiv a [p].

Dans tous les cas (aa premier ou non avec pp), ama[p]a^m \equiv a [p] .

Or, ceci est vrai pour tout diviseur premier pp de nn.

Autrement dit, amaa^{m- a} est un multiple de pp pour tout diviseur premier pp de nn.

Mais nn étant sans facteur carré, il en résulte donc que amaa^{m -a} est un multiple de nn : autrement dit, ama[n]a^m \equiv a [n].

En résumé :

Théorème :

Soit nn un entier (supérieur à 11), quadratfrei, et mm un entier tel que pour tout diviseur pp premier de nn on ait p1m1p- 1|m - 1.

Alors, pour tout entier aa, on a ama[n]a^m \equiv a [n].
On peut préciser que si de plus aa est premier avec nn, on a am11[n]a^{m-1} \equiv 1 [n].

Exemple:

n=33=3×11n = 33 = 3 \times 11
nn est donc sans carré.
On a φ(n)=(31)×(111)=20\varphi (n) = (3 - 1) \times (11 - 1) = 20.

Si on choisit m1=φ(n)=20m - 1 = \varphi(n) = 20 et donc m=21m = 21, on est donc dans la situation du théorème.

Soit a=5a = 5 : il est premier avec nn, et on vérifie bien que am1=5201[n]a^{m-1} = 5^{20} \equiv 1 [n], ainsi que am=5215[n]a^m = 5^{21} \equiv 5 [n].

Si par contre on choisit a=3a = 3 , il n'est plus premier avec nn, et on constate que am1=32012[n]a^{m-1} = 3^{20} \equiv 12 [n] et non pas à 11.

Par contre, on a bien am=3213[n]a^m = 3^{21} \equiv 3 [n].

Contre-exemple:

Si on choisit cette fois n=12=22×3n = 12 = 22 \times 3, on a φ(n)=6\varphi(n) = 6.

On choisit comme précédemment m1=φ(n)=6m - 1 = \varphi(n) = 6 et donc m=7m = 7.

On a encore, pour tout diviseur premier de nn :
21m12 - 1|m - 1 et 31m13 - 1|m - 1.

Par contre, nn n'est plus quadratfrei.

Soit alors a=2a = 2 : am1=264[n]a^{m-1} = 2^6 \equiv 4 [n], ce à quoi on pouvait s'attendre.

Mais am=278[n]a^m = 2^7 \equiv 8 [n], et non pas à 22.

Toutes nos vidéos sur précision sur le théorème de fermat-euler


Posez vos questions

D'autres interrogations sur ce cours ? Démarrez une discussion et obtenez des réponses à des exercices pratiques.

Accéder au forum


Cours de mathématiques Hors Programme

  1. Définitions de réciproque, contraposée, démonstration par l'absurde et algorithme
  2. Équation de Fermat pour p égal à 3
  3. Précision sur le théorème de Fermat-Euler
  4. Méthode de Horner (ou schéma de Horner)
  5. LaTeX: Dessin géométrique en LaTeX avec PSTricks
  6. Inégalités et Encadrements
  7. Équation diophantienne à la façon d'Euler
  8. Sommes de carrés : un théorème d'Aubry
  9. Développements limités
  10. Groupes finis et groupes cycliques
  11. Entiers d'Eisenstein
  12. Comment prendre des cours de maths en ligne ?
  13. 4 bonnes raisons de prendre des cours particuliers de mathématiques
  14. Préparer sa rentrée scolaire au mieux
  15. Comment prendre des cours particuliers de maths pendant le confinement COVID ?
  16. Choisir un prof particulier : focus sur la démarche à suivre
  17. L’évolution de l’école obligatoire
  18. Cours particuliers en ligne : une solution qui plaît
  19. Aides aux devoirs : comment s'organiser et pour quel tarif ?
  20. Comment choisir une calculatrice scientifique ?
  21. Faire appel à des étudiants pour des cours particuliers
  22. Quels sont les avantages du tutorat en ligne ?
  23. Améliorer ses compétences en mathématiques grâce aux cours particuliers en ligne
  24. Comment choisir le meilleur statut pour donner des cours particuliers ?
  25. Assurance scolaire pour étudiants : pourquoi et comment choisir les garanties adaptées ?
  26. Formation CAP Petite Enfance : détails, durée et perspectives professionnelles
  27. Pendant les vacances, stages, révisions ou soutien scolaire ?
  28. Protégez votre enfant : détecter le harcèlement scolaire
  29. Découvrez comment les diagrammes peuvent révolutionner votre compréhension des mathématiques
  30. Découvrir les Sciences : une exploration infatigable des mystères du monde
  31. Dessins numériques et avatars uniques : guide complet avec CapCut Online
  32. Le matériel pour une salle de classe confortable et propice à l'apprentissage
  33. Pourquoi choisir une prépa scientifique ?
  34. Le marché du soutien scolaire en France : tendances et solutions
  35. Carrières en comptabilité : explorez les métiers accessibles après une formation
  36. Archi Prep' : la meilleure prépa architecture pour 2025
  37. Comment progresser en mathématiques : astuces et idées pour tous les élèves