Sommaire
IDivisibilitéIINombres premiersIIICongruencesIVPGCD, théorème de Bézout et théorème de GaussAPGCDBAlgorithme d'EuclideCThéorème de BézoutDThéorème de Gauss Ce contenu a été rédigé par l'équipe éditoriale de Kartable.
Dernière modification : 07/08/2019 - Conforme au programme 2019-2020
Divisibilité
Entier divisible
Soient a et b deux entiers relatifs, avec b non nul.
L'entier a est divisible par b si et seulement s'il existe un entier relatif k tel que :
a = kb
- Si b divise a, alors - b divise a.
- Si d divise les entiers a et b, il divise alors toute combinaison linéaire de a et de b : ka + k'b, avec k et k' entiers relatifs.
Multiple d'un entier
L'entier a est un multiple de b si et seulement si b est un diviseur de a.
- Si a est un multiple de b, alors - a est un multiple de b.
- La somme et / ou la différence de multiples de b est un multiple de b.
- Si a est un multiple de b, alors ka est un multiple de b ( k entier relatif).
Division euclidienne
Soient a et b deux entiers relatifs, avec b non nul.
Il existe un unique couple d'entiers relatifs \left(q ; r\right) tel que :
a = bq + r et 0 \leq r \lt |b|
- L'entier q est le quotient de la division euclidienne de a par b.
- L'entier r est le reste de la division euclidienne de a par b.
Nombres premiers
Nombre premier
Un entier naturel est dit premier lorsqu'il admet exactement deux diviseurs dans \mathbb{N} : 1 et lui-même.
Infinité des nombres premiers
Il existe une infinité de nombres premiers.
Nombre de diviseurs
Tout entier supérieur ou égal à 2 admet au moins un diviseur premier.
Diviseur premier
Si a n'est pas premier, il admet alors au moins un diviseur premier p tel que :
2 \leq p \leq \sqrt{a}
Pour n\geq 2, si n n'admet aucun diviseur premier inférieur ou égal à \sqrt n, alors n est premier.
Nombres premiers entre eux
Deux entiers sont premiers entre eux si et seulement si leur seul diviseur positif commun est 1.
Si p premier et p ne divise pas a, alors a et p sont premiers entre eux.
Divisibilité par un nombre premier
Si p est premier et divise ab , alors p divise a ou p divise b .
Si, en plus, a et b sont premiers, alors p=a ou p=b .
Décomposition en produit de facteurs premiers
Tout entier n supérieur ou égal à 2 s'écrit de façon unique sous la forme :
n=p_1^{\alpha_1}\times p_2^{\alpha_2}\times \cdot\cdot\cdot \times p_m^{\alpha_m},
où p_1,p_2,\cdot\cdot\cdot,p_m sont des nombres premiers tels que p_1\lt p_2 \lt \cdot\cdot\cdot\lt p_m et \alpha_1,\alpha_2,\cdot\cdot\cdot,\alpha_m des entiers naturels non nuls.
Cette écriture est la décomposition en produit de facteurs premiers.
Congruences
Congruence
Soient a et b deux entiers relatifs quelconques et n un entier naturel supérieur ou égal à 2.
On dit que a est congru à b modulo n, noté a \equiv b \left[n\right], si et seulement si : a - b est multiple de n.
a \equiv b \left[n\right] \Leftrightarrow a et b ont le même reste dans la division euclidienne par n.
L'entier a est divisible par b (supérieur ou égal à 2) si et seulement si a \equiv 0 \left[b\right].
Soient n un entier naturel supérieur ou égal à 2, a, a', b et b' des entiers relatifs tels que a \equiv a' \left[n\right] et b \equiv b' \left[n\right], alors :
- a + b \equiv a' + b' \left[n\right]
- a - b \equiv a' - b' \left[n\right]
- ab \equiv a'b' \left[n\right]
- a^{k} \equiv a'^{k} \left[n\right] ( k entier naturel non nul)
Soient a, b et k des entiers relatifs et n un entier supérieur ou égal à 2.
Si a\equiv b\left[n\right], alors ka\equiv kb\left[n\right].
PGCD, théorème de Bézout et théorème de Gauss
PGCD
PGCD\left(a;b\right)
Soient a et b deux entiers relatifs dont l'un au moins est non nul. L'ensemble des diviseurs communs à a et b admet un plus grand élément, que l'on appelle le plus grand diviseur commun à a et b que l'on note PGCD\left(a;b\right).
PGCD\left(a;b\right)=1 si et seulement si a et b sont premiers entre eux.
Soient deux entiers relatifs a et b, avec a\neq0.
- PGCD\left(a;0\right)=a
- PGCD\left(a;1\right)=1
- PGCD\left(a;b\right)=PGCD\left(\left| a \right|;\left| b \right|\right)
- Si b divise a, alors PGCD\left(a;b\right)=\left| b \right| .
- Si b est premier et ne divise pas a , alors PGCD\left(a;b\right)=1 .
Soient deux entiers naturels non nuls a et b dont le PGCD est D. L'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de D.
Soient des entiers naturels non nuls a, b et k.
PGCD\left(ka;kb\right)=k\times PGCD \left(a;b\right)
Soient a et b deux entiers naturels non nuls.
D est le PGCD de a et b si et seulement si \dfrac{a}{D} et \dfrac{b}{D} sont des entiers premiers entre eux.
Algorithme d'Euclide
Algorithme d'Euclide
Soient a et b deux entiers naturels non nuls tels que b ne divise pas a.
La suite des divisions euclidiennes suivantes s'arrête au bout d'un certain nombre d'étapes :
- Étape 1 : On divise a par b : a=bq_0+r_0, avec 0\leq r_0 \lt b
- Étape 2 : On divise b par r_0 : b=r_0q_1+r_1, avec 0\leq r_1 \lt r_0
- Étape 3 : On divise r_0 par r_1 : r_0=r_1q_2+r_2, avec 0\leq r_2 \lt r_1
- Étape \left(n+2\right) : On divise r_{n-1} par r_n : r_{n-1}=r_nq_{n+1}+0
On a alors : PGCD\left(a;b\right)=r_n
Déterminons PGCD (1632;538).
- Étape 1 : On divise 1632 par 538 : 1\ 632=3\times 538+18
- Étape 2 : On divise 538 par 18 : 538=29\times 18+16
- Étape 3 : On divise 18 par 16 : 18=1\times 16+2
- Étape 4 : On divise 16 par 2 : 16=8\times 2+0
Le dernier reste non nul est 2.
Ainsi, PGCD\left(1\ 632;538\right)=2.
Théorème de Bézout
Soient a et b deux entiers relatifs non nuls, et D leur PGCD. Alors, il existe des entiers relatifs u et v tels que au+bv=D.
En remontant les étapes de l'algorithme d'Euclide appliqué à deux entiers naturels a et b, on détermine un couple \left(u;v\right) tel que au+bv=D.
Théorème de Bézout
Deux entiers relatifs a et b sont premiers entre eux si et seulement s'il existe des entiers u et v (entiers relatifs) tels que :
au + bv = 1
Théorème de Gauss
Théorème de Gauss
Soient a, b et c trois entiers non nuls.
Si a divise bc et a premier avec b, alors a divise c.