Approfondissements de lycée
Arithmétique modulaire.
Introduction.
L'arithmétique modulaire est reliée aux nombres premiers d'une manière agréable. Démarrons avec l'arithmétique modulo 7, c'est simplement comme l'arithmétique ordinaire excepté que l'on utilise seulement les nombres 0, 1, 2, 3, 4, 5 et 6. Si nous tombons sur un nombre en dehors de cet intervalle, nous lui ajoutons 7 (ou lui soustrayons 7), jusqu'à ce qu'il soit compris dans cet intervalle.
Exemples
Même chose pour la multiplication
Note - Négatifs : La représentation préférée de - 3 est 4, puisque - 3 + 7 = 4.
Exercices.
Trouver en modulo 11
1.
2.
3.
En utilisant les puissances de 2 trouver :
4.
i.e. trouver tous les nombres x mod 11 tels que x2 = 4. Il y a deux solutions, les trouver toutes deux.
5.
i.e. trouver tous les nombres x mod 11 tels que x2 = -2. Il y a deux solutions, les trouver toutes deux.
Division et inverses.
En restant en modulo 7, considérons le mécanisme de la division :
Qu'est-ce que
L'algèbre peut nous aider à comprendre :
Nous recherchons un nombre "x", tel que "x" x 5 = 1 modulo 7. "x" = 3 est une solution.
Exemple
Il est intéressant de noter que lorsque nous "divisions", nous recherchions réellement un nombre qui lorsqu'il est multiplié par le dénominateur donnera 1. En fait, la manière correcte de dire ce que nous faisons est de trouver les "inverses". Mais aucun tort ne nous arrivera si nous y pensons en terme de division. Considérons l'exemple suivant :
Si nous traitons cela comme une "division", nous obtenons 3. Ou nous pouvons le faire avec la manière des "inverses".
nous obtenons encore la même réponse. Intéressant !
Il est aussi intéressant de noter que la division ne marche pas toujours. Considérons :
Par la méthode des divisions, la réponse est 2. Mais 7 n'a pas d'inverse mod 28. Donc, nous ne pouvons pas dire 14/7 = 2. C'est un problème majeur avec la division en arithmétique mod "n", elle marche dans certains cas mais échoue complètement dans d'autres. Il est plus sûr de ne pas tenir compte de la division. À partir de maintenant, nous utiliserons "x-1" pour désigner l'inverse de "x" s'il existe. Le problème ci-dessus devient :
qui n'a pas de solution puisque 7-1 n'existe pas.
Notez que 0 n'a pas d'inverse ("Pourquoi pensez-vous que cela doit se produire ?") et évidemment, l'inverse de 1 est 1, mais 1 a-t'il un autre inverse ? Vous direz probablement 'non' après un moment. En fait, dans tout système de nombre raisonnable, un nombre ne peut avoir qu'un et un seul inverse. En voici la démonstration :
Supposons que "a" possède les inverses "b" et "c"
À partir de l'argument ci-dessus, tous les inverses de "a" doivent être égaux. Ainsi, si le nombre "a" possède un inverse, il doit avoir un seul inverse.
Une autre propriété intéressante de l'arithmétique modulo "n" est que le nombre "n-1" possède lui-même comme inverse. C'est à dire, (n-1) x (n-1) = 1 (mod "n"). La démonstration est laissée comme exercice à la fin de la section.
Existence d'un inverse.
Il peut sembler curieux pour vous que nous avons seulement considéré l'arithmétique modulaire d'un nombre premier; il existe une raison à cela. Et nous allons voir celle-ci maintenant.
Considérons l'arithmétique modulo 15 et notons que 15 est composé (5 × 3). Nous savons que l'inverse de 1 est 1 et celui de 14 est 14. Mais qu'en est-t'il de 3, 6, 9, 12, 5 et 10 ? Aucun d'entre eux ne possède d'inverse ! Et remarquez que chacun d'entre eux partage un facteur commun avec 15 !
Peut-être n'êtes-vous pas encore assez convaincu que cela est vrai et qu'il est bon d'être suspicieux lorsqu'un étudie les mathématiques. Mais éloignez votre doute puisque la démonstration est juste après.
Considérons 3. Supposons que 3 possède un inverse, qui est noté par x.
Le point délicat est de faire le "saut" de l'arithmétique modulaire vers l'arithmétique des nombres rationnels. Si 3x = 1 en arithmétique modulo 15, alors
pour un certain "k" en arithmétique des nombres rationnels.
Mais ceci est faux, parce que nous savons que "x" est un nombre entier. Par conséquent 3 n'a pas d'inverse en arithmétique mod 15. Montrer que 10 n'a pas d'inverse est plus difficile et est laissé en exercice.
Nous établirons le théorème montrant l'existence des inverses en arithmétique modulaire sans sa démonstration, puisque celle-ci est difficile.
Théorème
De manière similaire
Exercice.
1. Trouver x mod 7 si x existe :
2. Calculer x de deux manières : "division" et par la "recherche d'inverse".
3. Trouver x
4.
Trouver tous les inverses mod n (formula_24)
"Cet exercice peut sembler fastidieux, mais il décuplera votre compréhension de la rubrique"
Nombres premiers entre eux et Plus Grand Diviseur Commun (PGDC).
Deux nombre sont dits "premiers entre eux" si leur plus grand diviseur commun est 1. Le plus grand diviseur commun (pgdc) est simplement ce que son nom indique. Et il existe un manière rapide et élégante de le calculer pour deux nombres donnés, appelé l'Algorithme d'Euclide. Illustrons-le avec quelques exemples :
Exemple 1 :
Nous formons un tableau à deux colonnes où le plus grand des deux nombres est sur la droite comme ce qui suit
Nous calculons maintenant 49 (mod 21) qui est 7 et nous le plaçons dans la deuxième ligne de la colonne "plus petit", et nous plaçons 21 dans la colonne "plus grand".
Exécutons la même action sur la deuxième ligne pour produire la troisième ligne.
Quand nous voyons apparaître le nombre 0 dans la colonne "plus petit", nous savons alors que le nombre correspondant dans la colonne d'à côté est le PGDC des deux nombres avec lesquels nous avons démarré, i.e. 7 est le PGDC de 21 et 49. Cet "algorithme" est appelé l'algorithme d'Euclide.
Exemple 2
Exemple 3
Souvenez-vous
Vous ne savez peut-être pas pourquoi l'algorithme marche, mais il semble marcher. Vous ne pouvez pas résister à la question : "Pourquoi marche-t'il ?". Comme le dirais Arnold Ross, "C'est au demandeur de le découvrir, pas à moi de le dire."
Personnalité — Arnold Ross.
Arnold Ross est un professeur très respecté et un théoricien des nombres qui est très célèbre pour ses programmes scolaires d'été mathématiques pour les lycéens talentueux aux USA et en Australie.
Exercice.
1. Déterminer quand les ensembles de nombres suivants sont premiers entre eux
2. Trouver le PGDC des nombres 15, 510 et 375
Info — Algorithme.
Un algorithme est une description pas à pas d'une série d'actions qui faites correctement peuvent accomplir une tâche. Il existe des algorithmes pour trouver des nombres premiers, décider si 2 nombres sont premiers entre eux, trouver des inverses et beaucoup d'autres usages. Vous apprendrez comment implémenter certains de ces algorithmes que nous avons vus en utilisant un ordinateur dans le chapitre Programmation mathématique.
Équations diophantiennes.
Jetons de nouveau un coup d'œil à l'idée d'inverse, mais sous un angle différent. Considérons :
Nous savons que "x" est l'inverse de 5 et nous pouvons trouver que c'est 3 rapidement. Mais x = 10 est aussi une solution, donc x = 17, 24, 31, ... 7n + 3. Ainsi, il existe une infinité de solutions; par conséquent, nous disons que 3 est congru à 10, 17, 24, 31 et ainsi de suite. C'est une observation cruciale.
Maintenant, considérons
Une nouvelle notation est introduite ici, c'est le signe égal avec trois traits au lieu de deux. C'est le signe "congru à"; le résultat ci-dessus devrait être lu "216"x" est CONGRU à 1" à la place de "216"x" est EGAL à 1". À partir de maintenant, nous utiliserons le signe "congru à" pour l'arithmétique modulaire et le signe "égal" pour l'arithmétique ordinaire.
Pour revenir à l'exemple, nous savons que "x" existe, comme PGDC(811,216) = 1. Le problème avec la question ci-dessus est qu'il n'existe pas de manière rapide de décider la valeur de "x" ! La meilleure méthode que nous connaissons est de multiplier 216 par 1, 2, 3, 4... jusqu'à ce que nous obtenions la réponse, il existe au plus 816 calculs, manière trop fastidieuse pour les humains. Mais il existe une meilleure manière, et nous l'avons approchée quelques fois !
Nous notons que nous pouvions faire le "saut" juste avant vers les mathématiques rationnelles :
Nous sautons vers les mathématiques rationnelles de nouveau
Nous sautons une fois encore
Maintenant, le motif est clair, nous démarrerons à partir du début ainsi le processus ne sera pas interrompu :
Maintenant, tout ce que nous avons à faire est de choisir une valeur pour "f" et la substituer en retour pour trouver "a" ! Souvenez-vous que "a" est l'inverse de 216 mod 811. Nous choisissons f = 0, par conséquent e = 1, d = 13, c = 40, b = 53 et finalement a = 199 ! Si nous choisissons 1 pour "f", nous obtiendrons une valeur différente pour "a".
Un lecteur très perspicace aura noté que ceci est l'algorithme d'Euclide à l'envers.
Voici quelques exemples de plus de cette méthode ingénieuse en action :
Exemple 1
Trouver la plus petite valeur positive de "a" :
Choisissons d = 0, par conséquent a = 49.
Exemple 2
Trouver la plus petite valeur positive de "a" :
Choisissons e = 0, par conséquent a = -152 = 669
Exemple 3
Trouver la plus petite valeur positive de "a" :
Fixons i = 0, alors a = -21 = 34. "Pourquoi est-ce si lent pour deux nombres d'être si petit ? Que pouvez-vous dire sur les coefficients ?"
Exemple 4
Trouver la plus petite valeur positive de "a" :
Maintenant "d" n'est pas un nombre entier, par conséquent 21 n'a pas d'inverse mod 102.
Ce que nous avons exposé si longuement est la méthode pour trouver des solutions entières aux équations de la forme :
où "x" et "y" sont inconnus et "a" et "b" sont deux constantes données, ces équations sont appelées "équations diophantiennes" linéaires. Il est intéressant de noter que quelquefois il n'existe pas de solution, mais si une solution existe, cela implique qu'il en existe une infinité.
*Explication alternative*.
L'exemple était de trouver "a" donné :
Appliquons l'algorithme d'Euclide sur les deux nombres, mais nous aimerions plus de détails; plus précisément, nous voulons rajouter une colonne appelée QP pour faire apparaître le quotient partiel. Le quotient partiel est juste un terme technique pour "Combien de "n" vont dans "m"" c.a.d. Le quotient partiel de 19 par 3 est 6, le quotient partiel de 21 par 4 est 5 et, en dernier exemple le quotient partiel de 49 par 7 est 7.
La table indique que trois 216 vont dans 811 avec un reste de 163, ou symboliquement :
Continuons :
Maintenant, nous formons ce que l'on appelle la "table magique" qui ressemble à ceci initialement
Maintenant, nous écrivons le quotient partiel sur la première ligne :
Nous établissons la table en accord avec la règle suivante :
Cela paraît plus compliqué qu'il est. Illustrons-le en produisant une colonne :
Nous plaçons un 3 dans la deuxième ligne parce que 3 = 3 x 1 + 0. Nous plaçons un 1 dans la troisième ligne parce que 1 = 3 x 0 + 1.
Nous remplirons la table sans interruption :
Ainsi :
En fait, si vous avez remplis la table magique proprement et "multiplié en croix et soustrait" la dernière colonne correctement, alors vous obtiendrez toujours 1 ou -1, indiquant que les deux nombres avec lesquels vous avez démarré sont premiers entre eux. La table magique est juste une manière plus propre de faire des mathématiques. Une manière "désordonnée" de faire la même chose serait comme ce qui suit :
Maintenant, nous pouvons extraire l'inverse de 216 en récupérant les résultats à l'envers
Si nous regardons l'équation mod 811, nous verrons que l'inverse de 216 est 199.
Exercice.
1.
Trouver le plus petit "x" positif :
2.
Trouver le plus petit "x" positif :
3.
(b) Evaluer et exprimer sous la forme p/q
Que remarquez-vous ?
4.
(b) Evaluer et exprimer sous la forme p/q
Que remarquez-vous ?
Théorème des restes chinois.
Le théorème des restes chinois est connu en Chine sous le nom "Han Xing Dian Bing", qui dans sa traduction la plus naïve veut dire "Han Xing compte ses soldats". Le problème original est le suivant :
Nous traduisons la question en forme symbolique :
Comment allons-nous rechercher un tel "x" ? Nous utiliserons une méthode familière et cela sera illustré de meilleure manière par un exemple :
Regardons x = 2 (mod 3), nous faisons le "saut" en mathématique ordinaires
Maintenant, regardons l'équation modulo 5
Substituons dans (1) pour obtenir (2)
Nous choisissons b = 1 pour minimiser x, par conséquent x = 23. Et une vérification simple (à exécuter par le lecteur) confirmerait que x = 23 est une solution. Une bonne question à poser est "quel est le prochain plus petit "x" qui satisfait aux trois congruences ? La réponse est x = 128, et le prochain "x" est 233 et le prochain "x" est 338, et ils diffèrent de 105, le produit de 3, 5 et 7.
Nous illustrerons la méthode de résolution d'un système de congruences supplémentaire par les exemples suivants :
Exemple 1
Trouver le plus petit "x" qui satifait :
Solution
Par conséquent 52 est le plus petit "x" qui satisfait les congruences.
Exemple 2
Trouver le plus petit "x" qui satifait :
 Solution 
Par conséquent 269 est le plus petit "x" qui satisfait les congruences.
Exercices.
1.
Résoudre pour x
2.
Résoudre pour "x"
Existence d'une solution.
Les exercices précédents ont tous une solution. Donc, existe-t'il un système de congruences tel qu'aucune solution ne puisse être trouvée ? C'est certainement possible, considérons :
Un exemple plus gros est :
mais nous ne considérons pas des exemples absurdes comme cela.
Revenons au premier exemple, nous pouvons essayer de résoudre en faisant :
l'équation précédente n'a pas de solution parce que 3 n'a pas d'inverse modulo 21 !
Vous pouvez conclure rapidement que si deux systèmes modulo partagent un facteur commun alors il n'existe pas de solution. Mais ceci n'est pas vrai ! Considérons :
évidemment, une solution existe, explicitement k = 3, et les deux systèmes modulo sont le même comme pour le premier exemple (i.e. 15 et 21).
Donc, qu'est-ce qui détermine si un système de congruences possède une solution ou pas ? Considérons le cas général :
Nous avons
essentiellement, le problème nous demande de trouver k et l tels que les deux équations précédentes soient satisfaites. Nous effectuons :
Maintenant supposons que m et n ont pgdc(m,n) = d, et m = dmo, n = dno. Nous avons
maintenant lire l'équation mod ko, nous avons :
noter que ce qu'il y a ci-dessus n'a de sens seulement si (a - b)/d est entier. Aussi si (a - b)/d est un entier, alors il existe une solution, comme ko et lo sont premiers entre eux !
En résumé : pour un système de deux équations congruentes
il existe une solution si et seulement si
Et ce qui suit généralise le cas à plus de deux congruences. Pour un système de "n" congruences :
, pour qu'une solution existe, il faut pour tout i et j avec i ≠ j
Exercices.
Décider si une solution existe pour chacune des congruences. Expliquer pourquoi.
1.
2.
3.
4.
Pour aller plus loin.
Ce chapitre a été une introduction sympathique à la théorie des nombres, une branche des mathématiques profondément belle. Elle est sympathique dans le sens qu'elle est mathématiquement légère et somme toute un peu facile. Si vous avez apprécié la matière de ce chapitre, vous seriez aussi enchanté par le chapitre Arithmétique modulaire approfondie, qui est un traitement plus difficile et plus rigoureux du sujet..
Reconnaissance.
"Reconnaissance : Ce chapitre doit beaucoup de son inspiration à Terry Gagen, Professeur associé de Mathématiques à l'Université de Sydney, et à ses notes de lecture de "Number Theory and Algebra". Terry est un personnage très apprécié parmi ses étudiants et est renommé pour son style d'apprentissage entraînant."