Approfondissements de lycée
Introduction.
"Les mathématiques sont la reine des sciences et la théorie des nombres est la reine des mathématiques." -- Carl Friedrich Gauss 1777 - 1855
Dans la section Nombres premiers et arithmétique modulaire, nous avons vu les propriétés élémentaires d'un nombre premier et sa relation avec l'arithmétique modulaire. Pour la plus grande partie, notre attention a été restreinte à l'arithmétique mod "p", où "p" est un nombre premier.
Dans ce chapitre, nous démarrons en discutant certains résultats plus élémentaires dans l'arithmétique modulo un nombre premier "p", puis en se déplaçant sur la discussion de ces résultats modulo "m" où "m" est un nombre composé. En particulier, nous examinerons de plus près le Théorème des restes chinois (TRC), et comment il nous permet de casser l'arithmétique modulo "m" en "composants". À partir de ce point de vue, le TRC est un outils extrêmement puissant qui peut nous aider à débloquer beaucoup de secrets de l'arithmétique modulaire (avec une relative facilité).
Enfin, nous introduirons l'idée d'un "groupe abélien" à travers la multiplication dans l'arithmétique modulaire et nous discuterons sur le problème du logarithme discret qui sous-tend un des plus importants systèmes cryptographiques connus actuellement.
Connaissance supposée
"Dans ce chapitre, nous supposons que le lecteur peut trouver les inverses et est capable de résoudre un système de congruences (Théorème des Restes Chinois) (voir : Nombres premiers et arithmétique modulaire)."
Théorème de Wilson.
Le théorème de Wilson est un simple résultat qui conduit à un nombre d'observations intéressantes dans la théorie élémentaire des nombres. Il établit le résultat suivant :
Si "p" est un nombre premier, alors
Nous savons que l'inverse de "p" - 1 est "p" - 1, donc tout autre nombre peut être apparié avec son inverse et être "éliminé". Par exemple, soit "p" = 7, nous considérons
Ce que nous avons fait, c'est apparier les nombres qui sont inverses les uns des autres, il nous reste alors les nombres qui sont inverse avec eux-même. Dans ce cas, ce sont les nombres 1 et 6.
Mais, il existe une difficulté technique. Pour un nombre premier général, "p", comment savons-nous que 1 et "p" - 1 sont les seuls nombre mod "p" qui élevés au carrés donnent 1 ? Pour "m" non premier, il existe plus de 2 solutions à "x"2 ≡ 1 (mod "m"), par exemple, soit "m" = 15, alors x = 1, 14, 4, 11 sont les solutions de x2 ≡ 1 (mod "m").
Néanmoins, nous pouvons montrer qu'il ne peut y avoir que (au plus) deux solutions à x2 ≡ 1 (mod "p") lorsque "p" est premier. Nous le faisons par une simple "démonstration par l'absurde". Vous pouvez passer la preuve suivante et admettre que le théorème de Wilson est vrai.
Soit "p" un nombre premier, et x2 ≡ 1 (mod "p"). Nous voulons prouver qu'il ne peut exister seulement que 2 solutions, c'est à dire x = 1, -1
il est évident, à partir de ci-dessus que "x" = 1, -1 (≡ "p" - 1) sont solutions. Supposons qu'il existe une autre solution, "x" = "d", et "d" n'est pas égal à 1 ou -1. Puisque "p" est un nombre premier, nous savons que "d" - 1 doit avoir un inverse. Nous substituons "x" avec "d" et multiplions les deux côtés par l'inverse, c.a.d.
mais notre supposition initiale était que "d" ≠ -1. C'est une contradiction. Par conséquent, il ne peut exister que 2 solutions à x2 ≡ 1 (mod "p").
Le petit théorème de Fermat.
Il existe un remarquable petit théorème nommé en l'honneur de Fermat, le prince des mathématiciens amateurs. Il établit que si "p" est premier et pour "a" ≠ 0 donné alors
Ce théorème repose sur le fait que "p" est premier. Rappelons que si "p" est premier alors "a" ≠ 0 possède un inverse. Donc, pour tout "b" et "c", nous devons avoir
Une simple conséquence de ce qui précède est que les nombres suivants doivent tous être différents mod "p"
et il existe "p" - 1 de ces nombres ! Par conséquent, la liste précédente est simplement les nombres 1, 2, ... "p" - 1 dans un ordre différent. Prenons un exemple, si "p" = 5, et "a" = 2 :
multiplions chacun des précédents par 2 mod 5, nous obtenons
Ce sont les nombres originaux dans un ordre différent.
Ainsi, pour tout "p" et en utilisant le Théorème de Wilson (rappel : 1 × 2 × ... × (p-1) ≡ -1), nous obtenons
et d'un autre côté, nous obtenons aussi 
En égalisant les deux résultats, nous obtenons
ce qui est essentiellement le petit théorème de Fermat.
L'arithmétique modulaire avec un m général.
*Le Théorème des Restes Chinois revisité*.
Cette section est plutôt théorique, et est destinée à justifier l'arithmétique que couvrira la section suivante. Par conséquent, il n'est pas nécessaire de comprendre entièrement ce qui est exposé ici, le lecteur peut choisir en toute quiétude de passer l'exposé ci-dessous.
Rappelons le Théorème des Restes Chinois (TRC) que nous avons exposé dans la section Arithmétique modulaire. Les congruences suivantes
ont une solution si et seulement si pgcd("n1","n2") divise ("b" - "c").
Ce simple théorème décevant contient la clef de l'arithmétique modulo "m" (composé) ! Nous considérerons le cas où "m" a seulement deux facteurs premiers, c'est à dire un nombre semi-premier, puis le cas général.
Supposons "m" = "p"i"q"j, où "p" et "q" sont des nombres premiers distincts, alors chaque nombre naturel sous "m" (0, 1, 2, ..., m - 1) correspond "uniquement" à un système de congruences mod "p"i et mod "q"j. Ceci est dû au fait que pgcd("p"i,"q"j) = 1, donc il divise tous les nombres.
Considérons un nombre "n", il correspond à
pour deux nombres xn et yn. Si "r" ≠ "n" alors "r" correspond à
Maintenant, puisque "r" et "n" sont différents, nous devons avoir, soit "x"r ≠ "x"n et/ou "y"r ≠ "y"n 
Par exemple, prenons formula_11, alors nous pouvons construire la table suivante montrant les formula_12, formula_13 pour chaque "n" (0, 1, 2 ... 11)
Note : comme prévu, chaque nombre correspond "uniquement" à deux systèmes de congruences mod 22 et mod 3.
 Exercices 
1. Considérons "m" = 45 = 32 × 5. Complétez la table ci-dessous et vérifiez que deux nombres quelconques doivent différer d'au moins une place dans la deuxième et la troisième colonne
2. Supposons "m" = "p"i"q"j, "n" correspond à
et "r" correspond à
Il est vrai que
et que
Arithmétique avec le TRC.
L'exercice 2 ci-dessus a donné la plus grosse indication pour savoir comment le TRC peut nous aider avec l'arithmétique modulo "m". Il n'est pas essentiel pour le lecteur de tout comprendre ci-dessus, à ce niveau. Nous décrirons comment le TRC peut nous aider avec l'arithmétique modulo "m". Dans des termes simples, le TRC aide à casser un calcul modulo-"m" en de plus petits calculs modulo des facteurs premiers de "m".
Comme toujours, considérons un exemple simple d'abord. Soit formula_22, nous voyons que "m" a deux nombres premiers distincts. Nous devons montrer la multiplication de 51 et 13 modulo 63 de deux manières. Premièrement, la manière standard
Alternativement, nous notons que
et
Nous pouvons représenter les deux expressions ci-dessus comme un couple (6,2). Nous faisons un petit abus de notation en écrivant 51 = (6,2). De manière similaire, nous écrivons 13 = (4,6). Lorsque nous multiplions avec les couples, nous multiplions les "composants", i.e. ("a","b") × ("c","d") = ("ac","bd"),
Maintenant, résolvons 
et
nous écrivons x = 6 + 9"a", qui est la première congruence, puis
par conséquent, nous avons "a" = 3 + 7"b", en substituant plus haut, nous obtenons
qui est la même réponse que nous avons obtenue à partir de la multiplication de 51 et 13 (mod 63) par la méthode standard !
Résumons ce que nous avons fait. En représentant les deux nombres (51 et 13) sous forme de deux couples et en multipliant les "composants", nous finissons avec un autre couple. Et ce couple correspond au produit des deux nombres (mod "m") via le Théorème des Restes Chinois.
Nous prendrons deux exemples supplémentaires. Soit formula_28, et multiplions 66 et 40 de deux manières. D'abord, la manière standard
et maintenant, la deuxième manière, 40 = (0,7) et 66 = (4,0) et
Pour le deuxième exemple, nous notons qu'il n'est pas nécessaire de s'arrêter à simplement deux facteurs premiers distincts. Prenons formula_29, et multiplions 900 et 647 (mod 975),
Pour l'autre manière, nous notons que 900 ≡ 0 (mod 3) ≡ 0 (mod 25) ≡ 3 (mod 13), et pour 647 ≡ 2 (mod 3) ≡ 22 (mod 25) ≡ 10 (mod 13),
maintenant, si nous résolvons les congruences suivantes
alors nous obtiendrons "x" ≡ 225 !
Pourquoi ?
Casser l'arithmétique modulaire "m" en composants plus petits semble être un peu de travail. Prenons l'exemple des multiplications, d'abord, nous avons besoin d'exprimer chaque nombre comme un "n"-uplet ("n" est le nombre de facteurs premiers distincts de "m"), multiplier les composants, puis résoudre les "n" congruences résultantes. Assurément, ce travail est plus complexe que de multiplier simplement les deux nombres, puis de réduire le résultat modulo "m". Alors, pourquoi se donner la peine d'étudier cela ?
En cassant un nombre "m" en facteurs premiers, nous avons un aperçu de la manière dont l'arithmétique fonctionne réellement. De manière plus importante, beaucoup de problèmes en arithmétique modulaire "m" peuvent être difficiles à résoudre, mais lorsque qu'ils sont cassés en composants, ils deviennent subitement plus faciles, par exemple le théorème de Wilson pour un "m" général (discuté ci-dessous).
Exercices.
1. Montrer que l'addition peut aussi être effectuée par composants.
2. Multiplier par composants 32 et 84 (mod 134).
L'indicatrice d'Euler.
Pour discuter de la forme la plus générale du théorème de Wilson et du petit théorème de Fermat mod "m" (non premier), il est intéressant de connaître un résultat simple du mathématicien célèbre Euler. Plus précisément, nous voulons discuter d'une fonction, appelée la fonction indicatrice d'Euler, notée φ.
Les fonctions φ ne sont pas des choses très simples. Pour un nombre naturel quelconque "m", φ("m") donne le nombre de "n" < "m", tel que pgcd("n","m") = 1. En d'autres termes, elle calcule combien de nombre mod "m" ont un inverse. Nous discuterons de la valeur de φ(m) pour les cas simples d'abord, puis nous déduirons la formule pour un "m" général à partir des résultats basiques.
Par exemple, soit "m" = 5, alors φ("m") = 4. Comme 5 est un nombre premier, tous les nombres naturels différents de zéro inférieurs à 5 (1,2,3 and 4) sont premiers avec lui. Donc, il existe 4 nombres mod 5 qui ont des inverses. En fait, si "m" est premier, alors φ("m") = "m" - 1.
Nous pouvons généraliser ce qui précède à "m" = "p"r où "p" est premier. Dans ce cas, nous essayons d'employer un argument de comptage pour calculer φ("m"). Notez qu'il existe "p"r nombres naturels inférieurs à "m" (0, 1, 2 ... "p"r - 1), et donc φ("m") = "p"r - (nombre de "n" < "m" tels que pgcd("n","m") ≠ 1). Nous avons effectué ceci parce qu'il est plus facile de compter le nombre de "n" sans inverse mod "m".
Un élément, "n" mod "m" n'a pas d'inverse si et seulement si il partage un facteur commun avec "m". Mais, tous les facteurs de "m" (non égaux à 1) sont un multiple de "p". Donc, combien de multiples de "p" existent mod "m" ? Nous pouvons les lister, ce sont
où le dernier élément peut être écrit comme ("p""r"-1 - 1)"p", et donc, il existe formula_31 multiples de "p". Par conséquent, nous pouvons conclure 
Nous avons maintenant toute la machinerie nécessaire pour déduire la formule de φ("m") pour un "m" quelconque.
Par le Théorème Fondamental de l'Arithmétique, tout nombre naturel "m" peut être exprimé de manière unique comme le produit de nombres premiers, c'est à dire
où pi pour i = 1, 2 ... "r" sont des nombres premiers distincts et "k"i sont des entiers positifs. Par exemple 1225275 = 3×52×17×312. À partir d'ici, le lecteur peut essayer de déduire le résultat suivant (le TRC peut aider).
 La fonction indicatrice d'Euler φ 
 Supposons "m" exprimé de manière unique comme ci-dessous
 formula_33
 alors
 formula_35
Le théorème de Wilson.
Le théorème de Wilson pour un "m" général établit que le produit de tous les éléments inversibles mod "m"
Un élément inversible mod "m" est un nombre naturel "n" < "m" tel que pgcd("n", "m") = 1. Un élément auto-inversible est un élément dont l'inverse est lui-même.
Dans la démonstration du théorème de Wilson pour un nombre premier "p", les nombres de 1 à "p" - 1 ont tous des inverses. Ceci n'est pas vrai pour un "m" général. En fait, il est certain que ("m" - 1)! ≡ 0 (mod "m"), pour cette raison, nous considérons à la place le produit de tous les éléments inversibles mod "m". 
Pour le cas où "m" = "p" est un nombre premier, nous avons aussi fait appel au fait que 1 et "p" - 1 sont les seuls éléments qui, élevés au carré, donnent 1. En fait, pour "m" = "p"k, 1 et "m" - 1 (≡ -1) sont les seuls éléments auto-inversibles (voir les exercices). Mais, pour un "m" général, ceci n'est pas vrai. Prenons par exemple "m" = 21. En arithmétique modulo 21 chacun des nombres suivants est lui-même un inverse
donc, comment pouvons-nous dire que le produit de tous les éléments inversibles est égal à 1 ?
Nous utilisons le TRC décrit précédement. Considérons le cas où "m" = 2"p"k. Par le TRC, chaque élément mod "m" peut être représenté comme un couple ("a","b") où "a" peut prendre la valeur 0 ou 1 tandis que "b" peut prendre la valeur 0, 1, ..., ou "p"k - 1. Chaque couple correspond uniquement à une paire de congruences et la multiplication peut être exécutée par composants.
En utilisant l'information précédente, nous pouvons facilement lister tous les éléments auto-inversibles, parce que ("a","b")2 ≡ 1 signifie ("a"2,"b"2) = (1,1), donc "a" est un élément inversible mod 2 et "b" est un élément inversible mod "p"k, donc "a" ≡ 1 ou -1, "b" ≡ 1 ou -1. Mais mod 2 1 ≡ -1, donc "a" = 1. Par conséquent, il existe deux éléments qui sont auto-inversibles mod "m" = 2"p"k, ce sont (1,1) = 1, et (1, -1) = m - 1 . Donc, dans ce cas, le résultat est le même, comme "m" possède seulement un facteur premier unique.
Pour le cas où "m" possède plus d'un facteur premier et "m"≠ 2"pk". Disons "m" a "n" facteurs premiers alors "m" peut être représenté comme un "n"-uplet. Disons que "m" possède 3 facteurs premiers distincts, alors tous les éléments auto-inversibles de "m" sont
leur produit est (1,1,1) qui correspond à 1 mod "m".
Exercice.
1. Soit "p" un nombre premier. Montrer que dans l'arithmétique modulo "p"k, 1 et "p"k - 1 sont les seuls éléments auto-inversibles.
"...plus à venir"
Le petit théorème de Fermat.
Comme indiqué dans la section précédente, tous les éléments ne sont pas inversibles (c.a.d. possède un inverse) mod "m". Une version généralisée du dernier théorème de Fermat utilise la fonction indicatrice d'Euler, il énonce
pour tous les "a" ≠ 0 satisfaisant pgcd("a","m") = 1. Ceci est facile à voir à partir de la version généralisée du théorème de Wilson. Nous utilisons une technique similaire à partir de la démonstration du petit théorème de Fermat. Nous avons
où les "b"i's sont tous les éléments inversibles mod "m". Par le théorème de Wilson, le produit de tous les éléments inversibles égaux à "d" (= 1 ou -1). Donc, nous obtenons
qui est essentiellement l'énoncé du petit théorème de Fermat.
Bien que le petit théorème de Fermat est très net, il est "imprécis" dans un certain sens. Par exemple, prenons "m" = 15 = 3 × 5, nous savons que si "a" possède un inverse mod 15 alors "a"φ(15) = "a"8 ≡ 1 (mod 15). Mais 8 est trop grand, tout ce que nous avons besoin est 4, "a"4 ≡ 1 (mod 15) pour tous les "a" avec un inverse ("le lecteur peut vérifier").
La fonction de Carmichael λ("m") est le plus petit nombre tel que "a"λ(m) ≡ 1 (mod "m") pour un "a" inversible. Une question dans Ensemble de problèmes traite de cette fonction.
Exercices.
"...plus à venir"
La factorisation double-torsion.
Il est clair que factoriser un "grand" nombre peut être extrêmement difficile. Par exemple, étant donné 76 372 591 715 434 667, qui est le produit de deux nombres premiers, le lecteur peut-il le factoriser ? Sans l'aide d'un bon logiciel d'algèbre, la tâche risque d'être impossible. À ce jour, il n'existe pas d'algorithme connu "efficient" pour factoriser un nombre en facteurs premiers.
Néanmoins, sous certaines circonstances spéciales, factoriser peut être facile. Nous considérerons la méthode de factorisation double-torsion. Un élément double-torsion dans l'arithmétique modulaire "m" est un nombre "a" tel que "a"2 ≡ 1 (mod "m").
Considérons un exemple en arithmétique modulo 21. Notez qu'en utilisant le TRC, nous pouvons représenter tout nombre mod 21 comme un couple. Les éléments double-torsion sont 1 = (1,1), 13 = (1,-1), 8 = (-1,1) et 20 = (-1,-1). Les nombres 13 et 8 sont intéressants, parce que 1 et 20 (≡ - 1) sont évidemment double-torsion, nous appelons ces nombres double-torsion triviaux.
Maintenant, 13 + 1 = (1,-1) + (1,1) = (2,0). Par conséquent 13 + 1 = 14 est un élément partageant un facteur commun avec 21, comme le deuxième composant dans la représentation en couple de 14 est zéro. Par conséquent PGCD(14,21) = 7 est un facteur de 21.
L'exemple ci-dessus est très stupide parce que tout le monde peut factoriser 21. Mais qu'en est-il de 24 131 ? Factoriser n'est pas si facile. Mais, étant donné que 12 271 est un élément double-torsion non-trivial (c.a.d. ≠ 1 ou -1), alors nous pouvons conclure que pgcd(12271 + 1,24131) et pgcd(12271 - 1,24131) sont des facteurs de 24 131. En effet, pgcd(12272,24131) = 59 et pgcd(12270,24131) = 409 sont tous les deux des facteurs de 24 131.
Plus généralement, soit "m" un nombre composé, et "t" un élément double-torsion non-trivial mod "m" c.a.d. "t" ≠ 1, -1. Alors
ceci peut être expliqué en utilisant le TRC.
Nous expliquerons le cas où "m" = "pq", "p" et "q" sont des nombres premiers. Étant donné "t" est un élément double-torsion non-trivial, alors "t" a pour représentation (1,-1) ou (-1,1). Supposons "t" = (-1,1) alors "t" + 1 = (-1,1) + (1,1) = (0,2), par conséquent "t" + 1 doit avoir un multiple de "p" par conséquent pgcd("t","m") = "p". L'autre cas "t" - 1 = (-1,1) - (1,1) = (-2,0) et donc pgcd("t" - 1,m) = "q".
Donc, si nous avons un élément double-torsion non-trivial alors nous avons effectivement trouvé un (et sans doute plus) facteur premier, qui donne la factorisation du nombre. Dans les applications cryptographiques publiques les plus modernes, pour casser le système nous avons besoin seulement de factoriser un nombre avec deux facteurs premiers. De ce point de vue, la méthode de factorisation double-torsion est effroyablement efficiente.
Bien sur, trouver un élément double-torsion non-trivial n'est pas une tâche facile non plus. Donc, la banque par internet est encore sûre pour le moment. De cette manière, 76372591715434667 = 224364191 × 340395637.
Exercices.
1. Étant donné que 18815 est un élément double-torsion mod 26176. Factoriser 26176.
"...plus à venir"'