Objectif Général 5 — Arithmétique, algèbre linéaire et transformations. Divisibilité dans ℤ, division euclidienne, PGCD et algorithme d'Euclide, nombres premiers, congruences.
Soient a et b deux entiers relatifs. On dit que b divise a (noté b|a) s'il existe un entier relatif k tel que a = bk. On dit aussi que a est un multiple de b, ou que b est un diviseur de a.
• Transitivité : si a|b et b|c, alors a|c.
• Combinaison linéaire : si a|b et a|c, alors pour tous entiers α, β : a|(αb + βc).
• Tout entier non nul divise 0, et 1 divise tout entier.
7 divise-t-il 91 ? On a 91 = 7 × 13, donc 7 | 91. De plus, comme 7|91 et 7|63 (63=7×9), on a 7 | (2×91 − 3×63) = 7 | (182−189) = 7 | (−7), ce qui est bien vérifié car −7 = 7×(−1).
Soit a ∈ ℤ et b ∈ ℕ*. Il existe un unique couple d'entiers (q, r) tel que :
a = bq + r avec 0 ≤ r < b
q est le quotient et r le reste de la division euclidienne de a par b. On a b | a si et seulement si r = 0.
Effectuer la division euclidienne de 157 par 12.
Le quotient est q = 13 et le reste est r = 1.
Le PGCD (plus grand commun diviseur) de deux entiers naturels non nuls a et b est le plus grand entier qui divise à la fois a et b, noté PGCD(a,b).
Si a = bq + r est la division euclidienne de a par b (b≠0), alors PGCD(a,b) = PGCD(b,r). En répétant le procédé jusqu'à obtenir un reste nul, le dernier reste non nul est le PGCD.
Deux entiers a et b sont dits premiers entre eux si PGCD(a,b) = 1. (Théorème de Bézout, admis : il existe alors des entiers u, v tels que au+bv=1.)
Calculer PGCD(252, 105) par l'algorithme d'Euclide.
Le dernier reste non nul est 21, donc PGCD(252, 105) = 21.
Un entier naturel p ≥ 2 est premier si ses seuls diviseurs positifs sont 1 et p.
Tout entier n ≥ 2 se décompose de manière unique (à l'ordre près des facteurs) en produit de nombres premiers : n = p1α1 × p2α2 × … × pkαk.
Pour n ∈ ℕ*, on dit que a est congru à b modulo n, noté a ≡ b (mod n), si n divise (a−b). Les congruences sont compatibles avec l'addition et la multiplication : si a≡b et c≡d (mod n), alors a+c≡b+d et ac≡bd (mod n).
Décomposer 360 en produit de facteurs premiers, puis déterminer le reste de 2024 modulo 7.
Effectuer la division euclidienne de 275 par 18 (donner le quotient q et le reste r).
Quotient q = 15, reste r = 5.
Démontrer que si a divise b et a divise c, alors a divise (2b − 3c).
a|b signifie qu'il existe k∈ℤ tel que b=ak. a|c signifie qu'il existe l∈ℤ tel que c=al. Alors :
Comme (2k−3l) ∈ ℤ, on en déduit que a divise (2b−3c).
Calculer PGCD(462, 273) à l'aide de l'algorithme d'Euclide.
Le dernier reste non nul est 21 : PGCD(462, 273) = 21.
Décomposer 504 en produit de facteurs premiers, puis déterminer le nombre de diviseurs positifs de 504.
Si n = p1α1p2α2p3α3, le nombre de diviseurs positifs est (α1+1)(α2+1)(α3+1). Ici :
504 possède 24 diviseurs positifs.
Déterminer le reste de la division euclidienne de 3100 par 7.
10 questions · Une seule bonne réponse · Correction immédiate
« b divise a » signifie qu'il existe k ∈ ℤ tel que :
Dans la division euclidienne de a par b (b>0), le reste r vérifie :
La division euclidienne de 50 par 7 donne :
PGCD(18, 24) = ?
Deux entiers a et b sont premiers entre eux si :
Un nombre premier est un entier ≥ 2 dont les diviseurs positifs sont :
La décomposition en facteurs premiers de 60 est :
a ≡ b (mod n) signifie que :
Le reste de la division de 100 par 9 est :
L'algorithme d'Euclide permet de calculer :
