Approfondissements de lycée/Arithmétique modulaire

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

${\begin{matrix}3+2=5\mod {7}\\\\5+6=11=4\mod {7}\\\\5-6=-1=6\mod {7}\\\end{matrix}}$

Même chose pour la multiplication

${\begin{matrix}3\times 5=15=1\mod {7}\\\\5\times -6=-30=5\mod {7}\\\end{matrix}}$

Note - Négatifs : La représentation préférée de - 3 est 4, puisque - 3 + 7 = 4.

Exercices

Trouver en modulo 11

1.

-1 x -5

5

2.

3 x 7

21

3.

Exercices

1. 2¹
2. 2²
3. 2³
4. 2⁴
5. 2⁵
6. 2⁶
7. 2⁷
8. 2⁸
9. 2⁹
10. 2¹⁰

---

Solution

1. 2
2. 4
3. 8
4. 5
5. 10
6. 9
7. 7
8. 3
9. 6
10. 1

Que remarquez-vous ?

En utilisant les puissances de 2 trouver :

6¹

6²

6³

6⁴

6⁵

6⁶

6⁷

6⁸

6⁹

6¹⁰

Que remarquez-vous de nouveau ?

4.

${\sqrt {4}}$

i.e. trouver tous les nombres x mod 11 tels que x² = 4. Il y a deux solutions, les trouver toutes deux.

5.

${\sqrt {-2}}$

i.e. trouver tous les nombres x mod 11 tels que x² = -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

${\frac {1}{5}}$?

L'algèbre peut nous aider à comprendre :

${\begin{matrix}x&=&{\frac {1}{5}}\\5\times x&=&1\end{matrix}}$

Nous recherchons un nombre x, tel que x x 5 = 1 modulo 7. x = 3 est une solution.

Exemple

${\begin{matrix}x&=&{\frac {3}{5}}\\&=&3\times {\frac {1}{5}}\\&=&3\times 3\\&=&2\end{matrix}}$

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 :

${\frac {6}{2}}\ \ {\mbox{(mod 7)}}$

Si nous traitons cela comme une division, nous obtenons 3. Ou nous pouvons le faire avec la manière des inverses.

${\frac {6}{2}}=6\cdot 4=24=3{\pmod {7}}$

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 :

${\frac {14}{7}}\ \ {\mbox{(mod 28)}}$

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 :

$14\cdot 7^{-1}\ \ {\mbox{(mod 28)}}$

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

$b=b\times 1=b(ac)=(ba)c=1\times c=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.

$3x=1\ {\mbox{(mod 15)}}$

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

$3x=15k+1\,$

pour un certain k en arithmétique des nombres rationnels.

${\begin{matrix}3x&=&15k+1\\x&=&5k+{\frac {1}{3}}\\\end{matrix}}$

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

Si n est un nombre premier alors chaque nombre (excepté 0) possède un inverse en arithmétique modulo n.

De manière similaire

Si n est composé alors chaque nombre qui ne partage pas de facteur commun avec n possède un inverse.

Exercice

1. Trouver x mod 7 si x existe :

$x=2^{-1}$

$x=3^{-1}$

$x=4^{-1}$

$x=5^{-1}$

$x=6^{-1}$

$x=7^{-1}$

2. Calculer x de deux manières : "division" et par la "recherche d'inverse".

$x=28\cdot 7^{-1}\ \ {\mbox{(mod 29)}}$

3. Trouver x

$x=5^{99}\times (40+3^{-1})\ {\pmod {11}}$

4. Trouver tous les inverses mod n ($n\leq 19\,$)
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 :

Trouver le PGDC de 21 et 49.

Nous formons un tableau à deux colonnes où le plus grand des deux nombres est sur la droite comme ce qui suit

plus petit	plus grand
21	49

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.

plus petit	plus grand
21	49
7	21

Exécutons la même action sur la deuxième ligne pour produire la troisième ligne.

plus petit	plus grand
21	49
7	21
0	7

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

Trouver le PGDC de 31 et 101

plus petit	plus grand
31	101
8	31
7	8
1	7
0	1

Exemple 3

Trouver le PGDC de 132 et 200

plus petit	plus grand
132	200
68	132
64	68
4	64
0	4

Souvenez-vous

1. Le PGDC n'a pas besoin d'être un nombre premier.
2. Le PGDC de deux nombres premiers est 1.

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.

• http://www.ams.org/notices/200107/fea-ross.pdf

Exercice

1. Déterminer quand les ensembles de nombres suivants sont premiers entre eux

1. 5050 5051
2. 59 78
3. 111 369
4. 2021 4032

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 :

$5x=1\,$ mod 7

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

$216x\equiv 1\ \ \mod {811}$

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 "216x est CONGRU à 1" à la place de "216x 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 :

${\begin{matrix}216a&=&1+811b\\0&\equiv &1+163b&{\pmod {216}}\\\end{matrix}}$

Nous sautons vers les mathématiques rationnelles de nouveau

${\begin{matrix}216c&=&1+163b\\53c&\equiv &1&{\pmod {163}}\\\end{matrix}}$

Nous sautons une fois encore

${\begin{matrix}53c&=&1+163d\\0&\equiv &1+4d&{\pmod {53}}\\\end{matrix}}$

Maintenant, le motif est clair, nous démarrerons à partir du début ainsi le processus ne sera pas interrompu :

${\begin{matrix}216a&=&1+811b\\216c&=&1+163b\\53c&=&1+163d\\53e&=&1+4d\\e&=&1+4f\\\end{matrix}}$

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 :

${\begin{matrix}33a&\equiv &1\ \ {\mbox{(mod 101)}}\\33a&=&1+101b\\33c&=&1+2b\\c&=&1+2d\\\end{matrix}}$

Choisissons d = 0, par conséquent a = 49.

Exemple 2 Trouver la plus petite valeur positive de a :

${\begin{matrix}27a&\equiv &1\ \ {\mbox{(mod 821)}}\\27a&=&1+821b\\27c&=&1+11b\\5c&=&1+11d\\5e&=&1+d\\\end{matrix}}$

Choisissons e = 0, par conséquent a = -152 = 669

Exemple 3 Trouver la plus petite valeur positive de a :

${\begin{matrix}34a&\equiv &1\ \ {\mbox{(mod 55)}}\\34a&=&1+55b\\34c&=&1+21b\\13c&=&1+21d\\13e&=&1+8d\\5e&=&1+8f\\5g&=&1+3f\\2g&=&1+3h\\2i&=&1+h\\\end{matrix}}$

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 :

${\begin{matrix}21a&\equiv &1\ \ {\mbox{(mod 102)}}\\21a&=&1+102b\\21c&=&1+18b\\3c&=&1+18d\\3d&=&1\\\end{matrix}}$

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 :

ax + by = 1

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é :

216a = 1 (mod 811)

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.

Plus petit	Plus grand	QP
216	811	3
163

La table indique que trois 216 vont dans 811 avec un reste de 163, ou symboliquement :

811 = 3 x 216 + 163.

Continuons :

Plus petit	Plus grand	QP
216	811	3
163	216	1
53	163	3
4	53	13
1	4	4
0	1

Maintenant, nous formons ce que l'on appelle la "table magique" qui ressemble à ceci initialement

0	1
1	0

Maintenant, nous écrivons le quotient partiel sur la première ligne :

		3	1	3	13	4
0	1
1	0

Nous établissons la table en accord avec la règle suivante :

Multiplier un quotient partiel un espace vers la gauche de lui dans une ligne différente, ajouter le produit au nombre deux espaces vers la gauche sur la même ligne et placer la somme dans la ligne correspondante.

Cela paraît plus compliqué qu'il est. Illustrons-le en produisant une colonne :

		3	1	3	13	4
0	1	3
1	0	1

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 :

		3	1	3	13	4
0	1	3	4	15	199	811
1	0	1	1	4	53	216

Ainsi :

|199 x 216 - 811 x 53| = 1

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 :

811 = 3 x 216 + 163

216 = 1 x 163 + 53

163 = 3 x 53 + 4

53 = 13 x 4 + 1

Maintenant, nous pouvons extraire l'inverse de 216 en récupérant les résultats à l'envers

1 = 53 - 13 x 4

1 = 53 - 13 x(163 - 3 x 53)

1 = 40 x 53 - 13 x 163

1 = 40 x(216 - 163) - 13 x 163

1 = 40 x 216 - 53 x 163

1 = 40 x 216 - 53 x(811 - 3 x 216)

1 = 199 x 216 - 53 x 811

Si nous regardons l'équation mod 811, nous verrons que l'inverse de 216 est 199.

Exercice

1. Trouver le plus petit x positif :

216x = 1 (mod 816)

2. Trouver le plus petit x positif :

42x = 7 (mod 217)

3.

(a) Produire la table magique pour 33a = 1 (mod 101)

(b) Evaluer et exprimer sous la forme p/q

$3+{1 \over 16+{1 \over 2}}$

Que remarquez-vous ?

4.

(a) Produire la table magique pour 17a = 1 (mod 317)

(b) Evaluer et exprimer sous la forme p/q

$18+{1 \over 1+{1 \over {1+{1 \over 1+{1 \over 5}}}}}$

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 :

Il existe un nombre x, lorsque divisé par 3 donne le reste 2, lorsque divisé par 5 donne le reste 3 et lorsque divisé par 7 donne le reste 2. Trouver le plus petit x.

Nous traduisons la question en forme symbolique :

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&\equiv &3{\pmod {5}}\\x&\equiv &2{\pmod {7}}\\\end{matrix}}$

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

${\begin{matrix}x&\equiv &2{\pmod {3}}\\x&=&2+3a\qquad (1)\end{matrix}}$

Maintenant, regardons l'équation modulo 5

${\begin{matrix}2+3a&\equiv &3{\pmod {5}}\\3a&\equiv &1{\pmod {5}}\\a&\equiv &2{\pmod {5}}\\a&=&2+5b\end{matrix}}$

Substituons dans (1) pour obtenir (2)

$x=2+3(2+5b)\qquad (2)$

$x=8+15b\equiv 2{\pmod {7}}$

$b\equiv 1{\pmod {7}}$

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 :

$x\equiv 1{\pmod {3}}$

$x\equiv 2{\pmod {5}}$

$x\equiv 3{\pmod {7}}$

Solution

${\begin{matrix}x&=&1+3a&\equiv &2{\pmod {5}}\\&&a&=&2+5b\\x&=&1+3(2+5b)&\equiv &3{\pmod {7}}\\&=&7+15b&\equiv &3{\pmod {7}}\\&&b&\equiv &3{\pmod {7}}\\&&b&=&3+7c\\x&=&7+15(3+7c)\\x&=&52+15\times 7c\end{matrix}}$

Par conséquent 52 est le plus petit x qui satisfait les congruences.

Exemple 2 Trouver le plus petit x qui satifait :

$x\equiv 5{\pmod {11}}$

$x\equiv 3{\pmod {7}}$

$x\equiv 8{\pmod {9}}$

Solution

${\begin{matrix}x&=&5+11a&\equiv &3{\pmod {7}}\\&&a&\equiv &3{\pmod {7}}\\&&a&=&3+7b\\x&=&5+11(3+7b)\\x&=&38+11\times 7b&\equiv &8{\pmod {9}}\\&&2+2\times 7b&\equiv &8{\pmod {9}}\\&&b&\equiv &3{\pmod {9}}\\&&b&=&3+9c\\x&=&38+11\times 7(3+9c)\\&=&269+11\times 7\times 9c\end{matrix}}$

Par conséquent 269 est le plus petit x qui satisfait les congruences.

Exercices

1. Résoudre pour x

${\begin{matrix}3x&\equiv &5{\pmod {14}}\\2x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {15}}\\\end{matrix}}$

2. Résoudre pour x

${\begin{matrix}3x&\equiv &5{\pmod {19}}\\7x&\equiv &-3{\pmod {17}}\\x&\equiv &6{\pmod {11}}\\\end{matrix}}$

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 :

x ≡ 5 (mod 15)

x ≡ 10 (mod 21)

Un exemple plus gros est :

x ≡ 1 (mod 2)

x ≡ 0 (mod 2)

mais nous ne considérons pas des exemples absurdes comme cela.

Revenons au premier exemple, nous pouvons essayer de résoudre en faisant :

${\begin{matrix}x&=&5+15k&\equiv &10&{\pmod {21}}\\&&15k&\equiv &5&\\&&3k&\equiv &1&\\\end{matrix}}$

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 :

x ≡ 4 (mod 15)

x ≡ 7 (mod 21)

${\begin{matrix}x&=&4+15k&\equiv &7&{\pmod {21}}\\&&15k&\equiv &3&\\&&17\times 15k&\equiv &17\times 3&\\&&3k&\equiv &9&\\\end{matrix}}$

é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 :

x ≡ a (mod m)

x ≡ b (mod n)

Nous avons

x = a + km

x = b + ln

essentiellement, le problème nous demande de trouver k et l tels que les deux équations précédentes soient satisfaites. Nous effectuons :

0 = (a - b) + (km - ln)

(ln - km) = (a - b)

Maintenant supposons que m et n ont pgdc(m,n) = d, et m = dm_o, n = dn_o. Nous avons

dln_o - dkm_o = (a - b)

ln_o - km_o = (a - b)/d

maintenant lire l'équation mod k_o, nous avons :

l_on ≡ (a - b)/d (mod k_o)

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 k_o et l_o sont premiers entre eux !

En résumé : pour un système de deux équations congruentes

x ≡ a (mod m)

x ≡ b (mod n)

il existe une solution si et seulement si

pgdc(m,n) divise (a - b)

Et ce qui suit généralise le cas à plus de deux congruences. Pour un système de n congruences :

x ≡ a₁ (mod m₁)

x ≡ a₂ (mod m₂)

...

x ≡ a_n (mod m_n)

, pour qu'une solution existe, il faut pour tout i et j avec i ≠ j

pgdc(m_i,m_j) divise (a_i - a_j)

Exercices

Décider si une solution existe pour chacune des congruences. Expliquer pourquoi.

1.

x ≡ 7 (mod 25)

x ≡ 22 (mod 45)

2.

x ≡ 7 (mod 23)

x ≡ 3 (mod 11)

x ≡ 3 (mod 13)

3.

x ≡ 7 (mod 25)

x ≡ 22 (mod 45)

x ≡ 7 (mod 11)

4.

x ≡ 4 (mod 28)

x ≡ 28 (mod 52)

x ≡ 24 (mod 32)

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.