Exercices de Mathématiques
Arithmétique dans ZZ (III)
Énoncés
Énoncés des exercices
Exercice 1 [ Indication ] [ Correction ]
Montrer que a ∧ b = 1 ⇔ (ab) ∧ (a + b) = 1.
Exercice 2 [ Indication ] [ Correction ]
Résoudre les équations 2x − 5y ≡ 3
(mod 24) et 2x − 5y ≡ 5
(mod 24) dans IN.
Exercice 3 [ Indication ] [ Correction ]
Résoudre dans IN et dans ZZ l’équation 10x + 15y + 6z = 73.
Exercice 4 [ Indication ] [ Correction ]
Résoudre dans ZZ le système
(cid:26) x − 2y + z = 0
x + 2y − 2z = 1
Exercice 5 [ Indication ] [ Correction ]
Calculer le reste dans la division de 19991999 par 7.
Exercice 6 [ Indication ] [ Correction ]
Calculer le reste dans la division de N = 199919991999 par 11.
c(cid:13)EduKlub S.A.
Page 1
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Mathématiques
Arithmétique dans ZZ (III)
Indications, résultats
Indications ou résultats
Indication pour l’exercice 1 [ Retour à l’énoncé ]
– si ab ∧ (a + b) = 1, et si d divise a et b, alors. . ..
– Réciproquement, si a ∧ b = 1, alors (a + b) ∧ a = · · ·
Indication pour l’exercice 2 [ Retour à l’énoncé ]
Évaluer 2n et 5n modulo 24, par récurrence.
Indication pour l’exercice 3 [ Retour à l’énoncé ]
Si (x, y, z) est solution, montrer que y ≡ 1
(mod 2), x ≡ 1
(mod 3) et z ≡ 3
(mod 5).
Réciproquement, si x = 3X + 1, y = 2Y + 1 et z = 5Z + 3, considérer l’équation en X, Y, Z.
Indication pour l’exercice 4 [ Retour à l’énoncé ]
Si (x, y, z) est solution du système, constater que x et z sont impairs.
Poser alors x = 2X + 1, z = 2Z + 1, et résoudre le nouveau système.
Indication pour l’exercice 5 [ Retour à l’énoncé ]
On est amené à vérifier que la suite des 4n (mod 7) est 3-périodique.
Publicité
On trouve 19991999 ≡ 4
(mod 7).
Indication pour l’exercice 6 [ Retour à l’énoncé ]
Constater que N ≡ 819991999
(mod 11) et que 810 ≡ 1
(mod 11).
Justifier qu’il suffit alors de calculer n = 19991999 modulo 10.
Finalement, le reste dans la division de N = 199919991999 par 11 est 7.
c(cid:13)EduKlub S.A.
Page 2
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Mathématiques
Arithmétique dans ZZ (III)
Corrigés
Corrigés des exercices
Corrigé de l’exercice 1 [ Retour à l’énoncé ]
– On suppose que ab et a + b sont premiers entre eux.
Soit d un diviseur commun de a et b. Alors d divise ab et a + b.
Il s’ensuit que d = ±1. Ainsi les entiers a, b sont premiers entre eux.
– Réciproquement, on suppose que a et b sont premiers entre eux.
Alors a + b est premier avec a et avec b. Il est donc premier avec leur produit.
Corrigé de l’exercice 2 [ Retour à l’énoncé ]
On trouve successivement
n 0 1 2
3
2n 1 2 4
8
5n 1 5 1 · · ·
4
6
5
16 8 · · ·
Une récurrence évidente donne alors : ∀ n ≥ 3,
De le même manière, ∀ n ≥ 0,
(cid:26) 5n = 1
5n = 5
On en déduit : 2x − 5y ≡ 3
(mod 24) ⇔
On voit également que l’équation 2x − 5y ≡ 5
(mod 24) si n est pair
(mod 24) si n est impair
(cid:26) 2n = 16
2n = 8
Publicité
(mod 24) si n est pair
(mod 24) si n est impair
(cid:26) x = 2
y est pair
ou
(cid:26) x est impair ≥ 3
y est impair
(mod 24) ne possède aucune solution.
Corrigé de l’exercice 3 [ Retour à l’énoncé ]
Soit (x, y, z) ∈ ZZ3 une solution de 10x + 15y + 6z = 73, s’il en existe.
On effectue une réduction modulo 2 et on trouve y ≡ 1
(mod 3) et z ≡ 3
On trouve de même x ≡ 1
Autrement dit x = 3X + 1, y = 2Y + 1, z = 5Z + 3, avec (X, Y, Z) ∈ ZZ3.
Réciproquement, si on écrit x, y, z sous cette forme :
10x + 15y + 6z = 73 ⇔ 10(3X + 1) + 15(2Y + 1) + 6(5Z + 3) = 73 ⇔ X + Y + Z = 1
• Dans IN :
(mod 2).
(mod 5).
On remarque que si x, y, z sont dans IN, il en est de même de X, Y, Z.
Les seules solutions en (X, Y, Z) sont (1, 0, 0), (0, 1, 0) et (0, 0, 1).
Les seules solutions en (x, y, z) sont donc (4, 1, 3), (1, 3, 3) et (1, 1, 8).
• Dans ZZ :
L’équation X + Y + Z = 1 a pour solutions les triplets (X, Y, 1 − X − Y ), avec (X, Y ) ∈ ZZ2.
Les solutions de 10x + 15y + 6z = 73 sont donc les (x, y, z) tels que :
x = 3X + 1, y = 2Y + 1, z = 5(1 − X − Y ) + 3 = 8 − 5(X + Y ), avec (X, Y ) ∈ ZZ2.
c(cid:13)EduKlub S.A.
Page 3
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Mathématiques
Arithmétique dans ZZ (III)
Corrigés
Corrigé de l’exercice 4 [ Retour à l’énoncé ]
Soit (x, y, z) ∈ ZZ3 une solution du système, s’il en existe.
La deuxième équation montre que x est impair.
La première équation montre alors que z est impair.
On peut donc poser x = 2X + 1 et z = 2Z + 1, avec (X, Z) ∈ ZZ2.
Le systeme équivaut alors a
(cid:26) X − y + Z = −1
X + y − 2Z = 1
qui équivaut à
(cid:26) Z = 2X
y = 3X + 1
Publicité
L’ensemble des solutions est donc formé des triplets
x = 2X + 1
y = 3X + 1
z = 4X + 1
, avec X ∈ ZZ.
Corrigé de l’exercice 5 [ Retour à l’énoncé ]
On a 1999 = 285 · 7 + 4 et donc 19991999 ≡ 41999 (mod 7).
On calcule ensuite les premières valeurs de 4n (mod 7) :
n 0 1 2 3 · · ·
4n 1 4 2 1 · · ·
Il est clair que la suite des 4n (mod 7) est 3-périodique.
Plus précisément : 4n = 4r (mod 7) avec n = r (mod 3).
Or 1999 ≡ 1 (mod 3). On en déduit 19991999 ≡ 41999 ≡ 41 = 4
(mod 7).
Corrigé de l’exercice 6 [ Retour à l’énoncé ]
On a 1999 = 191 · 11 + 8. Ainsi 1999 ≡ 8
(mod 11) ⇒ N ≡ 819991999
(mod 11).
Le petit théorème de Fermat (cf exercice 4.4.11) montre que 810 ≡ 1
(mod 11).
Il reste donc à trouver le reste r dans la division de n = 19991999 par 10.
En effet, si n = 10q + r, alors 8n = 810q+r = (810)q 8r ≡ 8r
(mod 10). Donc n ≡ (−1)1999 ≡ −1 ≡ 9
Or 1999 ≡ −1
(mod 11).
(mod 10).
Ainsi r = 9, et N ≡ 8n ≡ 89
(mod 11). D’autre part :
82 ≡ −2
(mod 11) ⇒ 84 ≡ 4
(mod 11)
⇒ 88 ≡ 16 ≡ 5
(mod 11) ⇒ 89 ≡ 40 ≡ 7
(mod 11)
Conclusion : le reste dans la division de N = 199919991999 par 11 est 7.
c(cid:13)EduKlub S.A.
Page 4
Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et privée sont interdites.
www.klubprepa.net
Jean-Michel Ferrard