Exercices de Math´ematiques
Arithm´etique dans ZZ (III)
´Enonc´es
´Enonc´es des exercices
Exercice 1 [ Indication ] [ Correction ]
Montrer que a ∧ b = 1 ⇔ (ab) ∧ (a + b) = 1.
Exercice 2 [ Indication ] [ Correction ]
R´esoudre les ´equations 2x − 5y ≡ 3
(mod 24) et 2x − 5y ≡ 5
(mod 24) dans IN.
Exercice 3 [ Indication ] [ Correction ]
R´esoudre dans IN et dans ZZ l’´equation 10x + 15y + 6z = 73.
Exercice 4 [ Indication ] [ Correction ]
R´esoudre dans ZZ le syst`eme
(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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Math´ematiques
Arithm´etique dans ZZ (III)
Indications, r´esultats
Indications ou r´esultats
Indication pour l’exercice 1 [ Retour `a l’´enonc´e ]
– si ab ∧ (a + b) = 1, et si d divise a et b, alors. . ..
– R´eciproquement, si a ∧ b = 1, alors (a + b) ∧ a = · · ·
Indication pour l’exercice 2 [ Retour `a l’´enonc´e ]
´Evaluer 2n et 5n modulo 24, par r´ecurrence.
Indication pour l’exercice 3 [ Retour `a l’´enonc´e ]
Si (x, y, z) est solution, montrer que y ≡ 1
Publicité
(mod 2), x ≡ 1
(mod 3) et z ≡ 3
(mod 5).
R´eciproquement, si x = 3X + 1, y = 2Y + 1 et z = 5Z + 3, consid´erer l’´equation en X, Y, Z.
Indication pour l’exercice 4 [ Retour `a l’´enonc´e ]
Si (x, y, z) est solution du syst`eme, constater que x et z sont impairs.
Poser alors x = 2X + 1, z = 2Z + 1, et r´esoudre le nouveau syst`eme.
Indication pour l’exercice 5 [ Retour `a l’´enonc´e ]
On est amen´e `a v´erifier que la suite des 4n (mod 7) est 3-p´eriodique.
On trouve 19991999 ≡ 4
(mod 7).
Indication pour l’exercice 6 [ Retour `a l’´enonc´e ]
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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Math´ematiques
Arithm´etique dans ZZ (III)
Corrig´es
Corrig´es des exercices
Corrig´e de l’exercice 1 [ Retour `a l’´enonc´e ]
– 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´eciproquement, 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´e de l’exercice 2 [ Retour `a l’´enonc´e ]
On trouve successivement
n 0 1 2
3
Publicité
2n 1 2 4
8
5n 1 5 1 · · ·
4
6
5
16 8 · · ·
Une r´ecurrence ´evidente donne alors : ∀ n ≥ 3,
De le mˆeme mani`ere, ∀ n ≥ 0,
(cid:26) 5n = 1
5n = 5
On en d´eduit : 2x − 5y ≡ 3
(mod 24) ⇔
On voit ´egalement que l’´equation 2x − 5y ≡ 5
(mod 24) si n est pair
(mod 24) si n est impair
(cid:26) 2n = 16
2n = 8
(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`ede aucune solution.
Corrig´e de l’exercice 3 [ Retour `a l’´enonc´e ]
Soit (x, y, z) ∈ ZZ3 une solution de 10x + 15y + 6z = 73, s’il en existe.
On effectue une r´eduction modulo 2 et on trouve y ≡ 1
(mod 3) et z ≡ 3
On trouve de mˆeme x ≡ 1
Autrement dit x = 3X + 1, y = 2Y + 1, z = 5Z + 3, avec (X, Y, Z) ∈ ZZ3.
R´eciproquement, si on ´ecrit 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).
Publicité
On remarque que si x, y, z sont dans IN, il en est de mˆeme 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’´equation 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard
Exercices de Math´ematiques
Arithm´etique dans ZZ (III)
Corrig´es
Corrig´e de l’exercice 4 [ Retour `a l’´enonc´e ]
Soit (x, y, z) ∈ ZZ3 une solution du syst`eme, s’il en existe.
La deuxi`eme ´equation montre que x est impair.
La premi`ere ´equation montre alors que z est impair.
On peut donc poser x = 2X + 1 et z = 2Z + 1, avec (X, Z) ∈ ZZ2.
Le systeme ´equivaut alors a
(cid:26) X − y + Z = −1
X + y − 2Z = 1
qui ´equivaut `a
(cid:26) Z = 2X
y = 3X + 1
L’ensemble des solutions est donc form´e des triplets
x = 2X + 1
y = 3X + 1
z = 4X + 1
, avec X ∈ ZZ.
Corrig´e de l’exercice 5 [ Retour `a l’´enonc´e ]
On a 1999 = 285 · 7 + 4 et donc 19991999 ≡ 41999 (mod 7).
Publicité
On calcule ensuite les premi`eres 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´eriodique.
Plus pr´ecis´ement : 4n = 4r (mod 7) avec n = r (mod 3).
Or 1999 ≡ 1 (mod 3). On en d´eduit 19991999 ≡ 41999 ≡ 41 = 4
(mod 7).
Corrig´e de l’exercice 6 [ Retour `a l’´enonc´e ]
On a 1999 = 191 · 11 + 8. Ainsi 1999 ≡ 8
(mod 11) ⇒ N ≡ 819991999
(mod 11).
Le petit th´eor`eme de Fermat (cf exercice 4.4.11) montre que 810 ≡ 1
(mod 11).
Il reste donc `a 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´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation
individuelle et priv´ee sont interdites.
www.klubprepa.net
Jean-Michel Ferrard