1 Division Dans, Congruence: Maths Term Arithmetique Cours

MATHS Term ARITHMETIQUE COURS
Ce document n’est pas un cours à proprement parler. Son objectif est de récapituler l’essentiel et d’expliquer un
certain nombre de notions.
1 Division dans ℤ , congruence

1.1 Divisibilité
Dire qu’un entier b divise un entier a, c’est dire qu’il existe un entier k tel que a = k×b.
k et b sont ainsi deux diviseurs de a ; on dit aussi que a est un multiple de k et de b.
Ex : 35 est un multiple de 7 ; 6 divise 24 ; 36 n’est pas un multiple de 8 ; 6 ne divise pas 21
Propriété de transitivité : Si b divise a, et si c divise b, alors c divise a.

Ex : 12 est un diviseur de 60 et 3 est un diviseur de 12. Donc 3 est un diviseur de 60.
Par contraposée : 7 ne divise pas 1000, donc aucun multiple de 7 ne divise 1000.
Propriété de combinaison linéaire :

Si c divise a et b, alors c divise tout nombre pa + qb. où p et q sont deux entiers relatifs.
Ex : 3 divise 12 et 15, donc 3 est un diviseur de 12×7 + 15×4 = 144.
En effet, 12 = 3×4 et 15 = 3×5 ; donc 12×7 + 15×4 = 3×4×7 + 3×5×4 = 3×(28 + 20), multiple de 3.
Application : quels sont les entiers qui divisent deux entiers successifs ?
Si c divise a et a + 1, alors c divise, entre autres, le nombre a×(–1) + (a + 1)×1 = 1.
Finalement, c vaut 1 ou –1.
1.2 Division euclidienne

Dans cette partie, a et b sont deux entiers naturels, et b n’est pas nécessairement un diviseur de a.
Division euclidienne de a par b : a = bq + r
détermination d’un quotient q et d’un reste r, tous deux entiers, tels que 0 ≤ r < b .
Cette dernière condition assure l’unicité du couple ( q, r ) , pour un couple ( a, b ) donné.
Remarques :
* b divise a ⇔ r = 0 . * les résultats précédents sont applicables dans le cas où l’entier a est négatif.
Ex :
Division euclidienne de 35 par 4 : 35 = 4×8 + 3 (et non 4×9 – 1 ou encore 4×7 + 7)
Division euclidienne de 37 par 5 : 37 = 5×7 + 2
Division euclidienne de 21 par 7 : 21 = 7×3 + 0
Division euclidienne de –37 par 5 : –37 = 5×(–8) + 3 (il faut vérifier 0 ≤ r < b )
Déterminer la division euclidienne d’un grand nombre, par exemple celle de 11111 par 23 :
à la calculatrice, 11111/23 ≈ 483,087. Le quotient vaut donc 483.
Comme a = bq + r , 11111 = 23 × 483 + r = 11109 + r , et donc r = 2 .
1.3 Congruence
La notion de congruence est directement reliée à la division euclidienne, dont le reste est ici
l’information fondamentale, et dont le quotient est mis à l’écart.
Par exemple :
L’égalité 35 = 4×8 + 3 nous montre que 35 n’est pas divisible par 4 et qu’en outre le plus grand multiple
de 4 inférieur à 35 est 4×8 = 32. Comme 35 « dépasse » ce nombre (32) de trois unités, on dira que 35
est congru à 3 modulo 4 et on note : 35 ≡ 3[ 4 ] .
1
32 lui-même est congru à 0 modulo 4, puisqu’il est un multiple de 4. 32 ≡ 0 [ 4 ] .

(traduction dans le langage de la division euclidienne : 32 = 4×8 + 0)
On a, pour les entiers de 32 à 36 : 32 ≡ 0 [ 4 ] , 33 ≡ 1 [ 4 ] , 34 ≡ 2 [ 4 ] , 35 ≡ 3[ 4 ] , 36 ≡ 0 [ 4 ] .
Les congruences des entiers, modulo 4, ne peuvent être que 0, 1, 2 ou 3.

(autrement dit : le reste de la division euclidienne d’un entier par 4 ne peut être que 0, 1, 2 ou 3).
Généralisation : les congruences des entiers, modulo n, ne peuvent être que 0, 1, 2, …, n − 2 ou n − 1 .
Elles sont donc cycliques.
Ex : 0 ≡ 0 [4 ] , 1 ≡ 1[ 4 ] , 2 ≡ 2 [4 ] , 3 ≡ 3[ 4 ] ,
4 ≡ 0 [ 4 ] , 5 ≡ 1[ 4 ] , 6 ≡ 2 [ 4 ] , 7 ≡ 3 [ 4 ] ,
8 ≡ 0 [ 4 ] , 9 ≡ 1[ 4 ] , 10 ≡ 2 [ 4 ] , 11 ≡ 3 [ 4 ] , etc.
Deux entiers ayant la même congruence modulo n sont dits congrus.

Cela revient à dire que leur division euclidienne par n présente le même reste.
Ex : * 5 et 9 sont congrus modulo 4. * 3 et 11 sont congrus modulo 4. * 8 et 15 sont congrus modulo 7.
Cette mise en forme simple conduit à des propriétés remarquables :

Soit a ≡ r [b ] et a ′ ≡ r ′ [b ] . Alors :
1. a + a ′ ≡ r + r ′[b ] 2. aa ′ ≡ rr ′ [b ] 3. a p ≡ r p [b ] avec p ∈ ℕ
Ex :
* avec 1. : 8 ≡ 1[7] et 23 ≡ 2 [7] , donc 31 ≡ 3[7] .
* avec 2. : 8 ≡ 1[7] et 23 ≡ 2 [7] , donc 8 × 23 = 184 ≡ 2 [7] .
12 ≡ 5[7] et 13 ≡ 6 [7] , donc 156 ≡ 30 [7] ; or 30 ≡ 2 [7] , donc 156 ≡ 2 [7 ] .
* avec 3. : 8 ≡ 1[7] , donc 82 = 64 ≡ 1[7] , 83 = 512 ≡ 1 [7] , 8 4 = 4096 ≡ 1[7] , etc.
9 ≡ 2 [7] , donc 92 = 81 ≡ 22 = 4 [7] , 93 = 729 ≡ 23 = 8 [7] ≡ 1 [7] , etc.
Exercice classique de type bac :
Déterminer le reste de la division euclidienne de 2345 par 5.
Pour simplifier cette question, on va faire intervenir la formule n°3 (puis, au besoin, la formule n°2). On
s’appuie sur une puissance de 2 qui soit congrue à 1 modulo 5, ce qui est le cas de 24 = 16.
( )
86
On décompose alors 2345 à l’aide de 24 : 2 = 2 ×2 .
345 4
( ) × 2 ≡ (1) × 2 [ 5] ≡ 2 [ 5] .
86
On a donc : 2 = 2
345 4 86
2 PGCD et nombres premiers

2.1 PGCD de deux entiers
2.1.1 Définition
Le PGCD de deux entiers est le plus grand entier qui les divise tous les deux.
(tout nombre entier possède au moins un diviseur : 1, ou lui-même)
Ex :
Les diviseurs de 12 sont 1, 2, 3, 4, 6 et 12. Ceux de 42 sont 1, 2, 3, 6, 7, 14, 21 et 42.
42 et 12 ont des diviseurs communs : 1, 2, 3 et 6, le plus grand étant 6.
On écrit alors : PGDC(12, 42) = 6.
2
Sur calculatrice : obtenir un PGCD

TI84 -> touche MATH, menu écran NUM -> gcd(42,12) donne 6
Casio 35+ -> touche OPTN, menu écran Num, sous-menu GCD -> GCD(42,12) donne 6
2.1.2 Trouver le PGCD de deux entiers : l’algorithme d’Euclide

Un théorème établit que PGCD(a, b) = PGCD(b, r) où r est le reste de la division euclidienne de a par b.
Algorithme d’Euclide : utiliser ce résultat plusieurs fois de suite afin de diminuer la valeur des nombres
dont on veut trouver le PGCD, arrêter la procédure lorsque le reste est nul, et à ce moment-là, le PGCD
cherché est l’avant-dernier reste.
Cherchons à nouveau PGCD(42, 12) : 42 = 12×3 + 6, donc cela revient à chercher PGCD(12, 6) ;
on effectue alors la division euclidienne de 12 par 6 : 12 = 6×2 + 0.
Le reste étant nul, le PGCD initialement cherché vaut donc 6.
Autre exemple : PGCD(1725, 330)
1725 = 330×5 + 75, donc on cherche PGCD(330, 75)
330 = 75×4 + 30, donc on cherche PGCD(75, 30)
75 = 30×2 + 15, donc on cherche PGCD(30, 15) (on commence à deviner le résultat : 15)
30 = 15×2 + 0, donc le PGCD initialement cherché vaut 15.
2.2 Nombres premiers entre eux

2.2.1 Définition et résultats
Deux entiers a et b sont dits premiers entre eux lorsque PGCD(a, b) = 1.
(autrement dit : ils n’ont pas de diviseur en commun – autre que 1)
Ex : 21 = 3×7 et 10 = 2×5 sont premiers entre eux
42 = 2×3×7 et 10 = 2×5 ne sont pas premiers entre eux
Soit a, b et c trois entiers naturels non nuls.

Théorème de Gauss : Si a divise bc et si a et b sont premiers entre eux, alors a divise c.
Ex : 3 divise 24 = 4×6. Comme 3 et 4 sont premiers entre eux, alors 3 divise 6.
Corollaire : Si a et b divisent c et si a et b sont premiers entre eux, alors ab divise c.

Ex : 3 et 4 divisent 24. Comme 3 et 4 sont premiers entre eux, alors 3×4 divise 24.
3 et 6 divisent 24. Mais 3 et 6 ne sont pas premiers entre eux, et il n’est plus assuré que leur produit
divise 24 ; en effet : 3×6 ne divise pas 24.
Application : Déterminer les entiers x et y tels que 5x + 7y = 1.
Il faut déjà trouver un couple (x, y) solution : (3, –2) convient.
Ainsi, 5x + 7y = 5×3 + 7×(–2), soit 5×(x – 3) = 7×(–2 – y) relation (R).
5 divise donc 7×(–2 – y), et comme 5 et 7 sont premiers entre eux, 5 divise (–2 – y), soit (–2 – y) = 5k.
On a de même : 7 divise (x – 3), c’est-à-dire (x – 3) = 7k’.
La relation (R) devient : 5×7k‘ = 7×5k , qui indique que k‘ = k.
(–2 – y) = 5k donne y = –2 – 5k et (x – 3) = 7k donne x = 7k + 3. Ces deux relations donnent tous les
couples (x, y) solutions, grâce au paramètre k qui parcourt ℤ tout entier.
2.2.2 Théorème de Bézout

Identité de Bézout :
Soit a et b deux entiers et d leur PGCD. Alors il existe deux entiers relatifs u et v tels que au + bv = d.
Théorème de Bézout :
a et b sont premiers entre eux ⇔ il existe deux entiers relatifs u et v tels que au + bv = 1.
3
Application : démontrer que pour tout n ∈ ℕ les entiers 2n + 3 et 5n + 7 sont premiers entre eux.
Il suffit de trouver deux entiers relatifs u et v tels que (2n + 3 ) u + ( 5n + 7 ) v = 1 .
En particulier, ce calcul doit faire en sorte que (2n ) u + ( 5n ) v se simplifie (s’annule).
u = 5 et v = −2 conviennent.
2.3 Nombres premiers

2.3.1 Définition
Un entier naturel est dit premier s’il possède exactement deux diviseurs : 1 et lui-même.
Ex :
nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, …
nombres non premiers : 1 (ne possède qu’un diviseur : 1), 4 (possède trois diviseurs : 1, 2, 4), 6 (possède
quatre diviseurs : 1, 2, 3, 6), …
Pour déterminer la primalité d’un nombre n, on peut se contenter d’en rechercher des diviseurs entre 2
et n.
Ex :
63 est-il premier ? On recherchera des diviseurs entre 2 et 8. Le seul diviseur trouvé est 7. 63 n’est pas
premier.
127 est-il premier ? Cherchons des diviseurs entre 2 et 11. 127 est impair, donc 2, 4, 6, 8 et 10 ne sont
pas des diviseurs de 127. 127 ne se termine pas par 0 ou 5, donc il n’est pas multiple de 5. La somme des
chiffres de 127 n’est pas un multiple de 9, donc 127 ne l’est pas non plus (ni donc un multiple de 3). Les
seuls candidats restants sont 7 et 11. 127 = 7×18 + 1, donc non divisible par 7 ; 127 = 11×11 + 6, donc
non divisible par 11. Conclusion : 127 est un nombre premier.
2.3.2 Décomposition en facteurs premiers

Tout entier naturel strictement supérieur à 1 se décompose de manière unique en un produit de
facteurs premiers.
Ex :
12 = 22×3 13 = 13 14 = 2×7 15 = 3×5 16 = 24
30 = 2×3×5 36 = 22×32 120 = 23×3×5 900 = 22×3×52 4125 = 3×53×11
L’exposant d’un facteur premier est son ordre.
2.3.3 PGCD et PPCM grâce aux facteurs premiers

Deux entiers étant décomposés, leur PGCD est le produit de leurs facteurs premiers communs, chacun
pris à l’ordre le plus petit rencontré (voir en gras dans les exemples ci-dessous).
Ex :
120 = 23×3×5 et 900 = 22×3×52, donc PGCD(120, 900) = 22×3×5 = 60.
126 = 2×32×7 et 147 = 3×72, donc PGCD(126, 147) = 3×7 = 21.
Deux entiers étant décomposés, leur PPCM est le produit de tous leurs facteurs premiers, chacun pris à
l’ordre le plus grand rencontré (voir en gras dans les exemples ci-dessous).
Ex :
15 = 3×5 et 36 = 22×32, donc PPCM(120, 900) = 22×32×5 = 180.
126 = 2×32×7 et 147 = 3×72, donc PPCM(126, 147) = 2×32×72 = 882.

1 Division Dans, Congruence: Maths Term Arithmetique Cours

Transféré par

Droits d'auteur :

Formats disponibles

1 Division Dans, Congruence: Maths Term Arithmetique Cours

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

1 Division Dans, Congruence: Maths Term Arithmetique Cours

Transféré par

Droits d'auteur :

Formats disponibles

MATHS Term ARITHMETIQUE COURS

1 Division dans ℤ , congruence

Propriété de transitivité : Si b divise a, et si c divise b, alors c divise a.

Propriété de combinaison linéaire :

1.2 Division euclidienne

32 lui-même est congru à 0 modulo 4, puisqu’il est un multiple de 4. 32 ≡ 0 [ 4 ] .

Les congruences des entiers, modulo 4, ne peuvent être que 0, 1, 2 ou 3.

Deux entiers ayant la même congruence modulo n sont dits congrus.

Cette mise en forme simple conduit à des propriétés remarquables :

2 PGCD et nombres premiers

Sur calculatrice : obtenir un PGCD

2.1.2 Trouver le PGCD de deux entiers : l’algorithme d’Euclide

2.2 Nombres premiers entre eux

Soit a, b et c trois entiers naturels non nuls.

Corollaire : Si a et b divisent c et si a et b sont premiers entre eux, alors ab divise c.

2.2.2 Théorème de Bézout

2.3 Nombres premiers

2.3.2 Décomposition en facteurs premiers

L’exposant d’un facteur premier est son ordre.

2.3.3 PGCD et PPCM grâce aux facteurs premiers

Vous aimerez peut-être aussi