Divisibilité dans ℤ
Créé par Dhaouadi Nejib
Dans cet article, on designe par entier tout élément de ℤ et par entier naturel tout élément de ℕ
I. Diviseurs et Multiples d'entiers
☛ Définition
Soient a un entier et d un entier non nul
On dit que d est un diviseur de a ou que a est divisible par d (ou encore a est un multiple de d) s'il existe un entier q tel que $a=qd$ et on note d|a
L'ensemble des multiples de d est noté dℤ
Exemples✍
5 divise 25, -4 divise 16, 7 divise -28
Propriétés
Soient a et b deux entiers non nuls et c un entier
- a|a , a|(-a) , 1|a , (-1)|a et a|0
- Si a|b et b|a alors a=b ou a=-b
- Si a|b et b|c alors a|c
- Si a|b et a|c alors a| (αb+βc) où α et β sont deux entiers
Démonstration
- C'est évident car a=1×a , (-a)=(-1)×a , a=1×a , a=(-1)×(-a) et 0=a×0
- a|b et b|a ⇒ b=qa et a=pb où p,q ∈ ℤ donc b=pqb avec b≠0 ce qui donne pq=1 or -1 et 1 sont les seuls diviseurs de 1 alors p=q=1 ou p=q=-1 ou encore a=-b ou a=b
- a|b et b|c ⇒ b=pa et c=qb donc c=pqa d'où a|c
- a|b et a|c ⇒ b=pa et c=qa ⇒ αb+βc=αpa+βqa=a(αp+βq) donc a|(αb+βc)
Exemple✍
On pose $a=3n-2$ et $b=7n-5$ où n∈ℤ
Soit d un entier non nul tel que d|a et d|b donc d|(7a-3b) or 7a-3b=7(3n-2)-3(7n-5)=21n-14-21n+15=1 donc d|1 alors d=1 ou d=-1
Exercice 1
1) Determiner L'ensemble des entiers n tels que n-4 divise n+1.
2) Determiner L'ensemble des entiers n tels que n+1 divise n2+5n+10.
Cliquer ici pour voir les solutions
1) Pour tout entier n, n+1=(n-4)+5
Donc (n-4)|(n+1)⇔(n-4)|5⇔n-4 ∈{-5,-1,1,5}⇔n ∈{-1,3,5,9}
2) Pour tout entier n, n2+5n+10=(n+1)(n+4)+6
Donc (n+1)|(n2+5n+10)⇔ (n+1)|6⇔n+1 ∈ {-6,-3,-2,-1,1,2,3,6}⇔n ∈ {-7,-4,-3,-2,0,1,2,5}
Exercice 2
Démontrer que pour tout entier naturel n, $3^{2n+2}-2^{n+1}$ est divisible par 7.
Cliquer ici pour voir les solutions
Pour tout n∈ℕ on a: $3^{2n+2}-2^{n+1}$=$9×(3^2)^n-2×2^n$=$9×9^n-2×2^n$
Or d'après la formule du Binome on sait que $9^n=(7+2)^n=\sum_{k=0}^{n}{{C}_{n}^{k}×7^k×2^{n-k}}$=$2^n+7q$ où q est un entier
Donc $3^{2n+2}-2^{n+1}=9\times(2^n+7q)-2\times2^n$=$7\times2^n+9\times 7q=7(2^n+9q)$ d'où le résultat.
On peut aussi procéder à l'aide d'un raisonnement par récurrence.
II. Division Euclidienne dans ℤ
Rappel
On appel partie entière d'un réel x et on note E(x), le plus grand entier inferieur ou égal à x, ou encore c'est l'unique entier n tel que n≤x<n+1
Exemples: E(11)=11, E(-5)=-5, E(1.4)=1, E(-13,34)=-14; E($\sqrt{17}$)=4
☛ Définition
Soit a un entier et b un entier non nul
On appelle quotient de a par b l'entier q défini par:
$q=E\left({\frac ab}\right)\;\;\; si \;\; b>0$
$q$ est le plus petit entier superieur ou égal à $\frac ab$ si $b<0$
Conséquence
Soit q le quotient de a par b où a est un entier et b un entier non nul
- Si a est divisible par b alors $q=\frac ab$
- Si a n'est pas divisible par b alors:
- $q=E\left({\frac ab}\right)\;\;si\;b>0$
- $q=E\left({\frac ab}\right)+1\;\;si\;b<0$
Exemples✍
- a=129 et b=17>0, $\frac ab\simeq 7.6$ donc le quotient de 129 par 17 est égal à E(7.6)= 7
- a=-129 et b=17>0, $\frac ab\simeq -7.6$ donc le quotient de -129 par 17 est égal à E(-7.6)=-8
- a=129 et b=-17<0, $\frac ab\simeq -7.6$ donc le quotient de -129 par 17 est égal à E(-7.6)+1=-7
- a=-129 et b=-17<0, $\frac ab\simeq 7.6$ donc le quotient de -129 par -17 est égal à E(7.6)+1=8
N.B: Remarquons que même si les rapports $\frac ab$ sont égaux les quotients ne sont pas forcément les mêmes.
☛ Définition
Soit a un entier et b un entier non nul
On appelle reste de a par b, l'entier r tel que $r=a-bq$ où q est le quotient de a par b.
Exemples✍
Reprenons les exemples précédents :
- Pour a=129 et b=17, r=129-17×7=10
- Pour a=-129 et b=17, r=-129-17×(-8)=7
- Pour a=129 et b=-17, r=129-(-17)×(-7)=10
- Pour a=-129 et b=-17, r=-129-(-17)×8=7
☛ Théorème et définition
Pour tout entier a et pour tout entier b non nul, il existe et unique un couple d'entiers (q,r) tel que $a=bq+r$ où $0\leqslant r < \left|{b}\right| $
L'écriture $a=bq+r$ avec r∈{0,1,...,|b|-1} est appelée division euclidienne de a par b.
a s’appelle le dividende, b le diviseur, q le quotient et r le reste.
Démonstration
Pour l'existance, considerons le quotient q de a par b et le reste r de a par b.
Montrons que 0≤ r < |b|
❈Si b|a, $q= \frac ab$ et r=a-bq=0 donc 0≤ r < |b|
❈Si a n'est pas divisible par b
- Si b>0, $q=E\left({\frac{a}{b}}\right) $ et $r=a-bE\left({\frac{a}{b}}\right)$
On a $E\left({\frac ab}\right) <\frac ab <E\left({\frac ab}\right)+1 $⇔$bq <a <bq+b $⇔$0<a-bq<b$
- Si b<0, $q=E\left({\frac{a}{b}}\right)+1$ et $r=a-b\left({E\left({\frac{a}{b}}\right)+1}\right)$
On a $E\left({\frac ab}\right) <\frac ab <E\left({\frac ab}\right)+1 $⇔ $q-1< \frac ab < (q-1)+1$ $⇔bq-b > a > bq$⇔$-b >a-bq>0$ donc $0≤r<|b|$
Montrons l'unicité
Supposons qu'il existe deux couples (q,r) et (q',r') tels que a=bq+r=bq'+r' où $0\leqslant r < \left|{b}\right| $ et $0\leqslant r' < \left|{b}\right| $
Donc b(q-q')=r'-r ⇒ |b||q-q'|=|r-r'|<|b|
or |b|>0 donc |q-q'|<1 alors q-q'=0 d'où q=q' et par suite r=r'.
Exemples✍
Reprenons les exemples précédents :
- Pour a=129 et b=17, q=7 et r=10 donc 129=17×7+10
- Pour a=-129 et b=17,q=-8 et r=7 donc -129=17×(-8)+7
- Pour a=129 et b=-17,q=-7 et r=10 donc 129=(-17)×(-7)+10
- Pour a=-129 et b=-17,q=8 et r=7 donc -129=(-17)×8+7
Exercice 3
Trouver tous les entiers dont le quotient dans la division euclidienne par 5 donne un quotient égal à 3 fois le reste.
Cliquer ici pour voir les solutions
Soit a un entier qui vérifie la condition de l’énoncé.
On divise a par 5, on a alors :
a = 5q + r avec 0≤r<5.
Comme q=3r, on a a=15r+r=16r avec r∈{0,1,2,3,4} ou encore a∈{0,16,32,48,64}
Exercice 4
Lorsqu’on divise a par b, le reste est 8 et lorsqu’on divise 2a par b, le reste
est 5. Déterminer le diviseur b.
Cliquer ici pour voir les solutions
Écrivons chacune des deux divisions euclidiennes, en notant q et q′ les quotients respectifs :
$$\left\{{\begin{aligned}&{a=bq+8\;\; avec \;\; b>8\;\;\;}\\
&{2a=bq'+5 \;\;avec \;\; b>5}\end{aligned}}\right.$$
En multipliant la première division par 2 et en égalisant avec la deuxième, on obtient :
2bq + 16 = bq′ + 5 ou encore b(q'-2q)=11 avec b > 8
b|11 et b>8 donc b=11.
Le résultat s'affiche ici
III. Congruence modulo n
☛ Définition et notation
Soit n un entier naturel non nul et a et b deux entiers.
On dit que a est congru à b modulo n (ou a et b sont congrus modulo n) si a - b est un
multiple de n. On note alors $a \equiv b$ (mod n) .
☛ Théorème et définition
Soit n un entier naturel non nul .
Pour tout entier a, il existe un unique entier r appartenant à {0, ..., n-1} tel que $a\equiv r$ (mod n).
On dit que r est le reste modulo n de a.
Démonstration
Il suffit de faire la division euclidienne de a par n
On sait qu'il existe un unique couple (q,r) tel que a=qn+r avec r ∈ {0,1,...,n-1} ou encore a-r=qn
avec r ∈ {0,1,...,n-1} donc il existe et unique r∈{0,1,...,n-1} tel que $a\equiv r$ (mod n)
Conséquence
Soit n un entier naturel non nul.
Deux entiers sont congrus modulo n, si et seulement si, ils ont le même reste modulo n.
Remarques
a et b sont deux entiers et n un entier naturel non nul.
- $a \equiv 0\;\; (mod\;n)\Longleftrightarrow n|a$
- Si $a \equiv b$ (mod n) alors pour tout diviseur d>0 de n on a $a \equiv b$ (mod d)
- Si r est le reste de la division euclidienne de a par n alors $a \equiv r$ (mod n)
Exemples✍
- $143 \equiv 0$ (mod 11) car 11 divise 143 (143=13 ×11)
- $329 \equiv 53$ (mod 3) car 329 et 53 ont le même reste dans la division euclidienne par 3
- $41\equiv -4$ (mod 9) car 41=4×9+5 et -4=(-1)×9+5
- $675237 \equiv 7$ (mod 10) car 675237=10× 67523+7 (c'est le chiffre des unités)
- $67567283 \equiv 83$ (mod 100), $67567283 \equiv 283$ (mod 1000) etc ...
✒ Propriétés
Soit a, b, c et d des entiers et n un entier naturel non nul.
- $a \equiv a$ (mod n)
- $a \equiv b$ (mod n)⇔$b \equiv a$ (mod n)
- $a \equiv b$ (mod n) et $b \equiv c$ (mod n) ⇒$a \equiv c$ (mod n)
- Si $a \equiv b$ (mod n) et $c \equiv d$ (mod n) alors $a+c \equiv b+d$ (mod n) et $ac \equiv bd$ (mod n) et en conséquence:
$ka \equiv kb$ (mod n) pour tout entier k et $a^m \equiv b^m$ (mod n) pour tout entier m>0
Exemples✍
Déterminer les restes dans la division euclidienne par 7 des nombres :
1) 50100 2) 1003 3) 50100+100100
1) $50=7 \times7+1\Longrightarrow 50\equiv 1 \;\;(mod\;7)$ donc $50^{100} \equiv 1^{100} \equiv 1\;\;(mod\;7)$
2) $50\equiv 1 \;\;(mod\;7)\Longrightarrow 50 \times 2 \equiv 1\times 2 $ ou encore $100\equiv 2\;\;(mod\;7)$
donc $100^3 \equiv 2^3 \equiv 8 \equiv 1\;\;(mod\;7)$
3) $100^{100}=100^{3\times 33+1}=(100^3)^{33}\times 100$ donc $100^{100}\equiv 1^{33}\times 2 \equiv 2 \;\;(mod\;7)$
$50^{100}+100^{100} \equiv 1+2 \equiv 3 \;\;(mod\;7)$ donc 3 est le reste de la division euclidienne de $50^{100}+100^{100}$ par 7.
Exercice 5
Montrer que pour tout entier naturel n, $3^{n+3}-4^{4n+2}$ est divisible par 11.
Cliquer ici pour voir les solutions
$3^3=27 \equiv 5\;\;(mod\;11)$ donc $3^{n+3}=3^n \times 3^3\equiv 5\times3^n\;\;(mod\;11)$
$4^2=16\equiv 5\;\;(mod\;11)$ et $4^4 \equiv 25 \equiv 3\;\,(mod\;11)$ donc $4^{4n+2}=(4^4)^n \times 4^2\equiv 5\times 3^n \;\,(mod\;11)$
$3^{n+3}-4^{4n+2}\equiv 5\times 3^n-5\times 3^n \equiv 0 \;\,(mod\;11)$
Exercice 6
1) Déterminer suivant les valeurs de l’entier n, le reste de la division de n2 par 7.
2) En déduire alors les solutions de l’équation $x^2\equiv 2\;\;(mod\;7)$.
Cliquer ici pour voir les solutions
Déterminons les restes de n
2 suivant chaque reste de la division euclidienne de n par 7.
| Reste de la division de n par 7 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
| Reste de la division de n2 par 7 |
0 |
1 |
4 |
2 |
2 |
4 |
1 |
D'après le tableau de congruence précédent on déduit que les entiers n tels que $n^2 \equiv 2\;\;(mod\;7)$ sont les entiers qui ont pour restes 3 ou 4 dans la division par 7
Donc l'ensemble des solutions de l'équation $x^2\equiv2\;\;(mod\;7)$ est {7k+3,7k+4 où k∈ℤ}
Exercice 7
1) Soit a un entier naturel. Montrer que 7 divise $(a^3-1)(a^4+a)$
2) Déterminer les entiers a tels que $a^{600}\equiv 1\;\;(mod\;7)$
Rappel (Théorème de Fermat)
Pour tout entier a et pour tout entier naturel premier p on a $a^p\equiv a\;\;(mod\;p)$
Si p ne divise pas a alors $a^{p-1}\equiv 1\;\;(mod\;p)$
Cliquer ici pour voir les solutions
1) Pour tout entier naturel n,
$(a^3-1)(a^4+a)=a(a^3-1)(a^3+1)=a(a^6-1)$
- Si 7|a alors $a \equiv 0\;\;(mod\;7)$ donc $a(a^6-1) \equiv 0\;\;(mod\;7)$
- Si 7 ne divise pas a alors d'après le théorème de Fermat $a^6\equiv 1\;\;(mod\;7)$ ou encore $a^6-1 \equiv 0\;\;(mod\;7)$ donc $a(a^6-1) \equiv 0\;\;(mod\;7)$
D'où 7 divise $(a^3-1)(a^4+a)$ pour tout entier naturel a.
2) Si 7|a alors $a \equiv 0\;\; (mod\;7)$ donc $a^{600} \equiv 0\;\; (mod\;7)$ d'où tout multiple de 7 ne convient pas.
Si 7 ne divise pas a alors d'après le théorème de Fermat $a^6 \equiv 1 \;\; (mod\;7)$ donc $(a^6)^{100} \equiv 1 \;\; (mod\;7)$ ou encore $a^{600} \equiv 1 \;\; (mod\;7)$
Conclusion:
L'ensemble des entiers a tels que $a^{600} \equiv 1\;\;(mod\;7)$ est {7q+r où q∈ ℤ et r∈{1,2,3,4,5,6}}