CPGE Tétouan :MPSI TD 13 : Arithmétique dans Z 2024-20255

EX 1 Equations et systèmes d’inconnues dans Z 3- Après justifier son existance, déterminer l’inverse de x
Résoudre les équations et les systèmes suivants : modulo n dans J0, nJ pour chacun des cas :
1- Dans Z : (x + 5)/(x + 1) ; (1 − x)/(x2 + 2x + 3). (n, x) = (7, 3) ; (n, x) = (8, −5).
2- Dans Z2 : 3x − y − xy = 3 ; (x + 1)2 + (y − 1)2 = 25. EX 6 Les couples de quotients par pgcd et par ppcm
x∧y=3 x∧y=5 Soit (a, b) ∈ Z2 .
3- Dans N2 : ; .
x ∨ y = 36 x − y = 15 1- Supposons que (a, b) ̸= (0, 0) et soit d ∈ D(a) ∩ D(b).
Notons (α, β) ∈ Z2 tel que a = αd et b = βd.
EX 2 Caractéristique de ∧ et ∨ à l’aide de la relation "/" Montrer que a ∧ b = d ⇐⇒ α ∧ β = 1.
Pour tout x ∈ Z, notons D(x) = {k ∈ Z/k/x} et M(x) =
2- Supposons que a ̸= 0 et b ̸= 0 et posons d = a ∧ b et
{k ∈ Z/x/k} les ensembles respectivement des diviseurs
m = a ∨ b. Notons (α, β, γ, δ) ∈ Z4 tel que a = αd,
et des multiples de x dans Z. Fixons deux entiers relatifs
b = βd et γa = m = δb.
quelconques a et b.
Montrer que (γ, δ) = (ϵβ, ϵα), où ϵ = signe(ab).
Dans les questions ci-dessous on n’utilise que les définitions
élémentaires du a ∧ b et du a ∨ b à l’aide des fonctions Max 3- Supposons que a ̸= 0 et b ̸= 0 et soit m ∈ M(a) ∩
et Min et les conventions a ∧ b = 0, si (a, b) = (0, 0) et a ∨ b = 0, M(b). Notons (γ, δ) ∈ Z2 tel que γa = m = δb.
si a = 0 ou b = 0 (cours). Montrer que a ∨ b = m ⇐⇒ γ ∧ δ = 1.
1- Montrer que D(a) ∩ D(b) = D(a ∧ b). Indication : pour EX 7 Une famille de nombres composés
une inclusion, utiliser Bezout. On pose pour chaque n ∈ Z, P(n) = 4n3 − 18n2 − 8n − 15.
2- Déduire que ∀k ∈ Z : (k/a et k/b) =⇒ k/(a ∧ b). Montrer que " ∀n ∈ Z : P(n) n’est pas premier ".
Indication : Voir que P(n) = (n − 1)4 − (n − 2)4 .
3- Montrer que M(a) ∩ M(b) = M(a ∨ b). Indication :
pour une inclusion, faire une division euclidienne sur a∨b. EX 8 Nombres premiers entre eux et multiplication
4- Déduire que ∀k ∈ Z : (a/k et b/k) =⇒ (a ∨ b)/k. Dans l’exercice, a, b, c, b1 , . . . , br sont des entiers relatifs.
5- Déduire de 1- et de 3- que les lois ∧ et ∨ sont 1- Montrer que
associatives. a∧b=1
=⇒ a ∧ (bc) = 1. Réciproque ?
a∧c=1
EX 3 Un exemple de coefficients de Bezout Y
r
!

1- Trouver un couple (u0 , v0 ) ∈ Z2 tel que 24u0 + 15v0 = 2- Déduire : " (∀i ∈ J1, rK : a ∧ bi = 1) =⇒ a ∧ bi = 1".
i=1
3. Réciproque ?
2- Déduire tous les couples (u, v) ∈ Z2 tels que 3- Déduire successivement que si a ∧ b = 1, alors :
24u + 15v = 3 et représenter les graphiquement. "∀n ∈ N : a∧bn = 1" et " ∀(m, n) ∈ N2 : am ∧bn = 1".
3- Résoudre dans Z2 l’équation : 7u + 5v = 1. Indication : Dans , 1-vous pouvez utiliser le théorème de Bezout
(Interprétation graphique ?) ou le théorème de Gauss ou le théorème d’Euclide.

EX 4 Une équation diophantienne EX 9 Des distributivités, stabilités et compatibilités

Soit l’équation (E) :294x + 819y = 126 d’inconnue (x, y) ∈ Z2 . 1- Montrer que le pgcd des entiers n’est pas distributif
1- Résoudre (E) et interpréter graphiquement son en- par rapport à la multiplication. Pourtant, on a toujours
semble de solutions. [a ∧ (b.c)]/[(a ∧ b).(a ∧ c)].
2- Déterminer le nombre de solutions (x, y) de (E) tels 2- Montrer que le ppcm des entiers n’est pas distributif
que : |x| ⩽ 10 et |y| ⩽ 10. par rapport à la multiplication. Pourtant, on a toujours
[a ∨ (b.c)]/[(a ∨ b).(a ∨ c)].
EX 5 Inversibilité modulaire 3- Montrer que le pgcd et le ppcm des entiers sont l’un
Définition : Un entier relatif x est dit inversible modulo un entier
distributif par rapport à l’autre. Autrement dit, pour
relatif non nul n si : "∃y ∈ Z : xy ≡ 1 [n]".
tout a, b, c ∈ Z, on a : a∧(b ∨ c) = (a ∧ b) ∨ (a ∧ c)
Le cas échéant, on dit que x−1 modulo n est bien défini et qu’on
et a∨(b ∧ c) = (a ∨ b) ∧ (a ∨ c).
écrit x−1 ≡ y [n].
4- Montrer que la relation de divisibilité est stable par
1- Fixons n ∈ Z∗ . Montrer que pour tout x ∈ Z, on a : rapport à chacune des lois ∧ et ∨. Autrement dit :
"x inversible modulo n ⇐⇒ x ∧ n = 1". ∀a, b, x ∈ Z : a/b =⇒ (x ∧ a)/(x ∧ b).
Le cas échéant, montrer que l’inverse de x modulo n ∀a, b, x ∈ Z : a/b =⇒ (x ∨ a)/(x ∨ b).
est unique modulo n. Autrement dit, si y et z deux
entiers qui vérifient xy ≡ 1 [n]" et xz ≡ 1 [n]", alors 5- Montrer que la relation de divisibilité est compatible
y ≡ z [n]". avec chacune des lois ∧ et ∨. Autrement dit :
a/b
Indication : utiliser Bezout et dire comment on détermine, le ∀a, b, c, d ∈ Z : =⇒ (a ∧ c)/(b ∧ d).
c/d
cas échéant, l’inverse de x modulo n.
a/b
2- Déduire que si x est inversible modulo n, alors x ∀a, b, c, d ∈ Z : =⇒ (a ∨ c)/(b ∨ d).
c/d
admet un unique inverse modulo n dans l’intervalle √
J0, |n|J(ou dans n’importe quel intervalle des restes fixé EX 10 Condition pour que r n ∈ Q
au départ). Soit n ∈ N.
1
CPGE Tétouan :MPSI TD 13 : Arithmétique dans Z 2024-20255

√ √
1- Montrer que n∈Q⇔ n ∈ N ⇔ ∃m ∈ N : n = m2 .
n
_ Y
n
c) ai = ai .
2- Donner des équivalences similaires si on remplace le
√ √ i=1 i=1
symbole . par r . , où r ∈ N∗ . n Y
n
√ √ √ 3
√
5 Le cas échéant, on aura aussi :
_
Ai = ai .
3- Déduire que 2, 3, 12 et 16 ne sont pas des
i=1 i=1
rationnels.
3- Déduire aussi que les deux propositions suivantes sont
Indication : Vous pouvez utiliser le théorème de Gauss. équivalentes(ici les a1 , . . . , an sont tous non nuls) :
EX 11 Divisibilité de Ap a) a1 , . . . , an premiers entre eux dans l’ensemble.
n par rapport à p!
On fixe p ∈ N∗ . _n Yn
b) Ai = ai .
1- Montrer(sans utiliser la formule Ap p
n = p!Cn ) que p i=1 i=1
divise tout entier de la forme n(n − 1) . . . (n − p + 1),
où n ∈ Z. EX 16 Equations à coéfficients dans Z
p
Indication : utiliser la division euclidienne de n sur p. Rappel : ∀r ∈ Q, ∃!(p, q) ∈ Z × N∗ : r = et p ∧ q = 1.
q
2- En déduire que ∀n ∈ N∗ : p! divise Ap Définition : L’écriture ci-dessus de r avec le tel couple (p, q)
n.
s’appelle la forme irréductible de r.
EX 12 Divers Soit (E) : "an xn + an−1 xn−1 + · · · + a1 x + a0 = 0" une
équation à coéfficients dans Z.
1- Montrer que si r est un rationnel tel qu’il existe n ∈ N∗ p
vérifiant rn ∈ Z, alors r ∈ Z. 1- Montrer que si r = ∈ Q, sous sa forme irréductible,
q
2- Montrer que si n est une somme de deux carés parfaits, est une racine de (E), alors p/a0 et q/an .
alors son reste de la division euclidienne sur 4 ne peut 2- Résoudre dans Q, puis dans R l’équation
égaler 3. 3x3 − 4x2 − 10x − 4 = 0.
π π
3- Résoudre dans Z, 13/(x2 − 3x + 11). 3- Montrer que cos ∈/ Q. Déduire que sin ∈
/ Q.
9 9
EX 13 Deux suites à termes premiers entre eux Indication :
1- Montrer que ⋄ Dans 1-, vous pouvez utiliser le théorème de Gauss.
 √ n √ ⋄ Dans 3-, se rappeler que 4 cos3 (θ) = cos(3θ) + 3 cos(θ)
" ∀n ∈ N, ∃!(an , bn ) ∈ N2 : 1 + 2 = an + bn 2 ". π
et vérifier que cos est solution d’une équation à
9
2- Montrer que " ∀n ∈ N, : a2n − 2b2n = (−1)n ". coéfficients de Z qui n’admet pas de solutions dans Q.
3- En déduire que " ∀n ∈ N, : an ∧ bn = 1 ".
√ EX 17 Une preuve du petit théorème de Fermat
Indication : Dans 1-, utiliser le fait que 2∈
/ Q pour l’unicité On fixe un nombre premier p dans tout l’exercice. On se
du couple (an , bn ). propose de montrer le petit théorème de Fermat :
Théorème : ∀a ∈ Z : (a ∧ p = 1 ⇐⇒ ap−1 ≡ 1 [p]).
EX 14 Que signifie des nombres 2 à 2 premiers entre eux ? Pour cela, on commence par montrer le lemme suivant :
1- Vérifier que pour que deux entiers a et b ne soit pas Lemme : ∀x ∈ Z : xp ≡ x [p].
premiers entre eux, il faut et il suffit qu’il existe un 1- Vérifier que ∀x ∈ Z : −x ≡ x[2].
nombre premier p tel que p/a et p/b.
2- Montrer que : ∀k ∈K0, pJ: p ∧ k! = 1 et p/Cpk .
Etendre cette propriété pour plusieurs entiers.
3- Montrer le lemme précédent en combinant entre la
2- Soit a1 , . . . , an des entiers quelconques.
Y On pose pour distinction des cas et la récurrence.
chaque k ∈ J1, nK, Ak = ai .
4- En déduire l’implication =⇒ du théorème.
i∈J1,nK\{k}
Montrer l’équivalence entre les deux propositions : 5- Montrer l’implication ⇐= du théorème.
a) a1 , . . . , an deux à deux premiers entre eux. 6- Application 1 : Calcul des puissances modulaires
b) A1 , . . . , An premiers entre eux dans l’ensemble. a) Soit p premier et a ∈ tel que p ∤ a. Por tout k ∈ N,
Notons r = Reste(k, p−1). Vérifier que ak ≡ ar [p].
EX 15 Relation entre pgcd et ppcm de plusieurs entiers Aquoi égale ak [p] si p/a et k ⩾ 1.
Soit a1 , . . . , an des entiers relatifs quelconques.
Y b) Montrer que 11 divise 45630900 − 1.
On pose pour chaque k ∈ J1, nK, Ak = ai . c) Calculer 30005000 modulo(7) et 141001 modulo(3).
i∈J1,nK\{k}
7- Application 2 :(Un Cas particulier du théorème d’Eu-
1- Etablir !
la double relation suivante : ler) Soit n un entier qui se décompose sous forme
Y
n n
! n n
! n
!
^ _ ^ _ n = pq, où p et q deux entiers premiers distincts.
ai Ai = ai = Ai ai .
On pose ϕ = (p − 1)(q − 1). Montrer(sans utiliser le
i=1 i=1 i=1 i=1 i=1
théorème d’Euler(se voit plus tard en programme MP)
2- En déduire que les trois propositions suivantes sont
que : ∀a ∈ Z : a ∧ n = 1 =⇒ aϕ ≡ 1 [n].
équivalentes(ici les a1 , . . . , an sont tous non nuls) :
Indications :
a) a1 , . . . , an deux à deux premiers entre eux. — Dans 2-, utiliser Gauss et des différentes caractéristiques
b) A1 , . . . , An premiers entre eux dans l’ensemble. des nombres premiers.
2
CPGE Tétouan :MPSI TD 13 : Arithmétique dans Z 2024-20255

— Dans 3-, utiliser la formule de binôme. 1- Montrer que pour tout k ⩾ 1, l’application
— Dans 4- vous pouvez utiliser Gauss ou Bezout ou inversi- Y
k
bilité modulaire et les opérations sur les congruences. Gk : J0, bi J −→ J0, Bk J
— Dans 5-, vous pouvez suivre la contraposée et utiliser les i=1
est bien définie et
opérations et la relation de division ou encore les opérations X
k−1

sur les congruences ou vous pouvez utiliser de manière (a0 , . . . , ak−1 ) 7−→ ai Bi
rapide Bezout. i=0
— Dans 7-, utiliser le petit théorème de Fermat et le premier injective et en déduire qu’elle est bijective.
lemme d’Euclide). 2- Fixons k ⩾ 1. Soit n ∈ J0, Bk J. Donner une méthode
récurrente pour calculer les composantes de la k-liste
EX 18 Critères de divisibilité sur les chiffres décimaux
antécédente de n par Gk .
Soit un entier naturel x = ap . . . a0 10 donné sous une
représentation décimale, avec p ∈ N et a0 , . . . , ap ∈ J0, 9K. 3- On suppose que ∀k ∈ N∗ : bk ⩾ 2.
1- Donner les restes centrés de 10 sur n dans chacun des a) Montrerque "∀n ∈ N∗ , ∃!p ∈ N, ∃! (a0 , . . . , ap ) ∈
cas : n = 2 3 4 5 6 7 8 9 10 11 
 X p
n = ai Bi
2- Déterminer toutes les valeurs possibles des restes Zp+1 : " et donner un encadre-
centrés de 10i sur n, pour toute valeur i ∈ N dans 
 i=0
et ap ̸= 0
chcun des cas de n ci-dessus. ment de n en fonction des termes de la suite
Indication : Lorsque n premier, utiliser le petit théorème de (bk )k⩾1 .
Fermat et les restes de division sur n − 1. Lorsque n n’est pas
b) Que signifie ceci lorsque la suite (bk )k⩾1 est
premier, vous pouver suivre une méthode analogue en utlisant
constante de valeur b ?
le théorème d’Euler et en considérant φ(n) au lieu de n − 1.
3- Montrer que x ≡ 2a1 +a0 [4](si p = 0, on pose a1 = 0). 4- La boucle suivante permet d’exécuter nm instructions
(Inst(i, j))(i,j)∈J0,nJ×J0,mJ , en parcourant de manière
4- Déduire que pour que x soit divisible par 4, il
ligne par ligne(Exemple : Inst(i, j) est l’affichage du
faut et il suffit que 4/ (2a1 + a0 ). Appliquer à
coefficient ai,j d’une matrice).
x = 910425478954896.
▷ Pour i allant de 0 vers n − 1 faire
5- Trouver des critères analogues de divisibilité sur cha- ▷ Pour j allant de 0 vers m − 1 faire
cun des entiers n = 2, 5, 10, 3, 9, 8, 6, 11, 7. ▷ Inst(i, j) ;
EX 19 Nombres de Fermat ▷ Fin pour j ;
Les nombres de Fermat sont les entiers donnés par Fn = ▷ Fin pour i .
n
22 +1, pour tout n ∈ N. Montrer que les nombres de Fermat Ecrire une boucle qui permet d’exécuter toutes les
sont deux à deux premiers entre eux. instructions ci-dessus de manière séquentielle en allant
n Y
n−1 de 0 vers (nm − 1).
Indication, Voir ∀n ∈ N : Fn+1 = Fn + 22 Fk .
k=0 EX 23 Méthode de Garner pour systèmes de congruence
On fixe p entiers b1 , . . . , bp naturels non nuls et
EX 20 Nombres de Fibonacci deux à deux premiers entre eux. On pose pour chaque
On considère la suite (Fn )n>0 dite de Fibonacci définie par :
 Y
k Yk
F0 = 0 , F1 = 1 k ∈ J1, pK, Bk = bi , B0 = 1 et Ck = bi .
∀n ∈ N : Fn+2 = Fn+1 + Fn i=1 i=1,i̸=k
1- Montrer que ∀n ∈ N : Fn+1 ∧ Fn = 1. On a vu(cours) que le système de congruence

 n ≡ a1 [b1 ]
2- Montrer que ∀n, m ∈ N : Fn ∧ Fm = Fn∧m . .. .. ..
(Sp ) . . . admet une unique solution
Indication : voir ∀(n, m) ∈ N∗ ×N : Fn+m = Fn Fm+1 +Fn−1 Fm . 

n ≡ ap [bp ]
dans x dans l’intervalle J0, Bp J et que cette solution! peut
EX 21 Valuation p-adique et représentation dans la base p Xp
On fixe un nombre premier p et un entier naturel non nul n. s’écrire sous forme x = Reste ak uk Ck , Bp , où
Notons ap . . . a0 p la représentation de n dans la base p. k=1
1- Montrer que pour tout k ∈ N, on a : u1 , . . . , up sont des coefficients de Bezout relativement aux
vp (n) = k ⇐⇒ (∀i ∈ J0, kJ: ai = 0) et ak ̸= 0. entiers C1 , . . . , Cp .
Nous allons dans ci-dessous proposer une autre méthode
2- Comparer ceci avec la définition par dérivées de l’ordre
-dite de Garner- qui permet de calculer la telle solution x
de multiplicité d’une racine dans un polynôme et avec
de manière plus efficace au niveau des tailles des entiers à
la formule de Taylor.
manipuler.
L’idée de la méthode repose sur le fait que l’exercice 22
EX 22 Représentation de Garner pour les entiers
précédent, affirme que tout élément de J0, Bp J peut s’écrire
Fixons une suite (bk )k⩾1 d’entiers naturels non nuls et
de manière unique sous forme : x = Gp (α0 , . . . , αp−1 ) =
Yk
X
p−1
posons pour chaque k ⩾ 1, Bk = bi et B0 = 1. αk Bk = α0 + α1 b1 + α2 b1 b2 + · · · + αp−1 b1 . . . bp−1 .
i=1
k=0
Notre objectif se ramène donc à calculer les coefficients
3
CPGE Tétouan :MPSI TD 13 : Arithmétique dans Z 2024-20255

α0 , . . . , αp−1 (avant de calculer x) et bien sûr en fonction

des b1 , . . . , bp et des a1 , . . . , ap .
Cas de p = 1 :
1- Montrer que α0 ≡ a1 [b1 ].
2- En déduire que α0 = Reste (a1 , b1 ).
Cas de p = 2 :
1- Justifier pourquoi b1 est inversible modulo b2 .
Notons u1 l’inverse de b1 modulo b2 .
2- Montrer que α1 ≡ u1 (a2 − α0 ) [b2 ].
3- En déduire que α1 = Reste (u1 (a2 − α0 ) , b2 ).
x ≡ −6 [5]
4- Résoudre dans J0, 34K puis dans Z : (S2 )
x ≡ 4 [7]
Une héridité : On suppose  que p ⩾ 2 et qu’on a arrivé

 n ≡ a1 [b1 ]
à résoudre le système (Sp−1 ) .. .. .. et on
 . . .

n ≡ ap−1 [bp−1 ]
note Ap−1 sa solution trouvée dans J0, Bp−1 J(ou dans Z).
1- Montrer que pour tout x ∈ Z, on a :
x ≡ Ap−1 [Bp−1 ]
x solution de (Sp ) ⇐⇒ x solution de
x ≡ ap [bp ]
2- Justifier pourquoi qu’on est donc ramené à un système
à deux équations qui satisfait aux mêmes conditions
que du cas de p = 2 ci-dessus.

 x ≡ 8 [5]
3- Résoudre dans J0, 139K, puis dans Z : (S3 ) x ≡ 9 [7]

x ≡ 1 [4]
p−1
Une formule récurrente pour les coefficients (αk )k=0 :
On suppose pour la suite que p ⩾ 2 et fixons k ∈ J1, pJ.
1- Justifier pourquoi Bk est inversible modulo bk+1 .
Notons par Uk un tel inverse de Bk modulo bk+1 .
X
k−1
!
2- Montrer que αk ≡ Uk ak+1 − αi Bi [bk+1 ].
i=0

X
k−1
! !
3- Déduire que αk = Reste Uk ak+1 − αi Bi , bk+1 .
i=0
4- Déduire un algorithme récursif qui permet de calculer
p−1
les coefficients (αk )k=0 , puis l’unique solution x du
système (Sp ).
5- Résoudre avec cette formule le système (S3 ) ci-dessus.

EX 24 Equations et systèmes de congruence dans Z

Résoudre les équations et les systèmes suivants :
1- Dans Z, puis dans J0, 11K : 5x + 6 ≡ 0[12] ; 8x + 3 ≡
0[12] ; 8x + 4 ≡ 0[12].
5x − y ≡ 3[7]
2- Dans Z2 , puis dans J0, 7K : .
2x + 3 ≡ 1[7]
x ≡ 3[5]
3- Dans Z, puis dans J0, 34K : .
x ≡ 4[7]
x ≡ 5[10]
4- Dans Z, puis dans J0, 29K : .
x ≡ 1[6]
x ≡ 3[4]
5- Dans Z, puis dans J0, 11K : .
x ≡ 5[6]