TS Spé Chap 1 : Cours Divisibilité

7/22/2019 TS Sp Chap 1 : Cours Divisibilit

1/5

1. Divisibilit

1.1 Divisibilit dans Z

1.1.1 Multiples et diviseurs

Dfinition. Un nombre entierest par dfaut un entier relatif (de Z). Si ce nombre est positif

alors cest un entier naturel (de N).

Dfinition. Soient aet bdans Z. Le nombre aest un multiplede b (ou best un diviseur de a)

sil existe k dans Zvrifiant a= kb.

Remarque. On note alorsb|a. Lensemble des multiples de a est not aZ. Par exemple les nombres pairs sont nots

2Z ={ , 4, 2, 0, 2, 4, 6, }.

Tout entier apossde au moins comme diviseurs 1, 1, a, a.

Sia = 0 alors tout diviseur de a est compris entre |a|et |a|. Il en rsulte quun entier

non nul possde un nombre fini de diviseurs.

1.1.2 Proprits lmentaires

On se place dans Z.

1. Si b|a alors b|a aussi.

2. Si a|b et b|a alors a= b.

3. Si a|b et b|c alorsa|c (transitivit).

4. Si a|b et a|c alors a divise b+c, b c et plus gnralement toute combinaison linaire

b+c.

5. Si a|b alors ac|bcpour tout c non nul.

Preuve. Exercice !

1.2 Division euclidienne

1.2.1 Prliminaires

On rappelle le rsultat fondamental (dcoulant de la construction de N) suivant :

Thorme. Toute partie non vide de Npossde un plus petit lment.

Remarque. Cette proprit est remarquable. Elle est par exemple fausse pour R+ (R

+ ne

possde pas de plus petit lment) et Q+ (Q

+ ne possde pas de plus petit lment).

120


2/5

Thorme. Toute suite dcroissante dentiers naturels est stationnaire.

Preuve. Soit (an) une suite dcroissante dentiers naturels et soitA= {an, n N} lensemble des

valeurs prises par cette suite. Lensemble A dentiers naturels possde un plus petit lmenta.

Il existe donc un rang n0tel que an0 =a. Puisque (an) dcroit, n n0impliquean =an0.

1.2.2 Division euclidienne

Thorme. Soient a et b deux entiers naturels, avec b = 0. Il existe un unique couple (q, r)

dentiers naturels vrifiant a= bq+r et 0 r < b.

Dfinition. Dans cette situation, a est le dividende, b le diviseur, q le quotient et r le reste.

Preuve. Existence. Soit B = {k N, k b > a} lensemble de tous les multiples de b

suprieurs a. Cest un sous-ensemble de N, il possde ainsi un plus petit lment q.

Notons alors q = q

1. Par dfinition de q

, qb a. Ainsi r = a bq 0 et de plusr < b(sinon r b implique a bq bi.e. a b+bq= qb: absurde).

Unicit. Si a = bq1 +r1 = bq2+r2 avec 0 r1, r2 < b alors b < r2r1 < b et

r2 r1 =b(q1 q2). Ainsi r2 r1 est un multiple de b strictement compris entre b et

b ; la seule possibilit est r2 r1= 0. Par consquent r1=r2 et ensuite q1=q2.

Corollaire.Soient a et b deux entiers relatifs, avec b= 0. Il existe un unique couple (q, r) avec

q Zet r Nvrifiant a= bq+r et 0 r


3/5

Remarque. Soient a et b deux entiers non nuls et d leur pgcd. On a donc a = da et b = db

avec a et b entiers. Soit d leur pgcd ; il divise a et b et donc dd diviseaet b. Loption d >1

conduit donc une absurdit puisqued est le plus grand diviseur commun de a et b. Finalement

d = 1 i.e. a et b sont premiers entre eux.

1.3.2 Calcul effectif du pgcd

Thorme (Euclide). Soient a et b deux entiers naturels non nuls et a = bq+ r leur division

euclidienne. Alors pgcd(a, b) = pgcd(b, r)

Preuve. Sic diviseaet balorscdivisea bq=r. Rciproquement, sicdivisebet r alorsc divise

bq+ r= a. Ainsi lensemble des diviseurs communs a et bet celui des diviseurs communs b

et r sont les mmes. Ils possdent donc le mme plus grand lment.

Thorme (algorithme dEuclide). Litration de lgalit du thorme prcdent permet de

trouver le pgcd de aet b comme le dernier reste r non nul.

Preuve. On a sucessivement pgcd(a, b) = pgcd(b, r0), pgcd(b, r0) = pgcd(r0, r1), pgcd(r0, r1) =

pgcd(r1, r2), pgcd(r1, r2) = pgcd(r2, r3), etc. La suite (rk) des restes est strictement dcroissante

(car un reste est strictement infrieur au diviseur) ; elle sarrte donc et on note rn1le dernier

reste non nul.

Par galits successives, pgcd(a, b) = = pgcd(rn2, rn1). De plusrn2=qrn1 + rn= qrn1implique pgcd(rn2, rn1) =rn1. Finalement, pgcd(a, b) =rn1.

Remarque. On peut attaquer lalgorithme dEuclide sans tenir compte du plus grand des deux

entiers a et b. Un mauvais choix ventuel (i.e. par un programme) se traduit par une simpledivision euclidienne inutile.

1.4 Congruences

1.4.1 Gnralits

Dfinition. Deux entiers aet b sont congrusmodulo lentier naturel nsi a best un multiple

de n. On note alors a b mod n ou a b [n].

Remarque. De manire quivalente, ceci signifie que a et b ont le mme reste lors de leur

division euclidienne par n.

Remarque. Il existe un seul entier r vrifiant 0 r < n et a r mod n. Cest le rsidu

minimal. La phrase calculer a mod n signifie calculer r (rduction modulaire).

Thorme. (rflexivit)a a mod n ;

(commutativit) a b mod n ssi b a mod n ;

(transitivit) a b mod n et b c mod n impliquent a c mod n.

Preuve. Triviale.

122


4/5

1.4.2 Oprations

Thorme. Si a b mod net a b mod n alors a+a b+b mod n ;

si a b mod net a b mod nalors aa bb mod n ;

si a b mod net k N alors ak bk mod n.

Preuve. Exercice !

Il suffit de remarquer que aa bb = (a b)a + (a b)b est divisible par n puisque

a b et a b le sont.

Simple rcurrence en utilisant le deuxime point : exercice !

Remarque. Attention ! il ny a pas dopration triviale de division modulaire.

1.5 Grands thormes1.5.1 Bzout

Thorme (de Bzout). Deux entiers non nuls aet b sont premiers entre eux ssi il existe deux

entiersu et v vrifiant au+bv = 1.

Preuve. Supposons quil existe u et v tels que au+bv = 1. Si d divise a et b alors d

diviseau+bv i.e. d= 1. Par consquent aet bsont premiers entre eux.

Supposons que a et b soient premiers entre eux. Posons G = {am+ bn, m Z, n

Z} N. On constate que G est non vide puisque aa+ bb = a2 + b2 > 0 et donc

aa+bb G. Lensemble G est donc un sous-ensemble non vide de N et possde ainsi

un plus petit lment non nul d = au + bv. Montrons ensuite que d divise a et b.

Effectuons la division euclidienne de a par d : a = dq+r avec 0 r < d. Il vient

r= a dq=a (au + bv)q= a(1 qu) + b(vq). Si r >0 alors on a trouv un lment

de G plus petit que d car r < d, ce qui contredit la dfinition de d. Ainsi r = 0, ce qui

montre que d divise a. En montrant de mme que d divise b, on prouve que d divise a

etb. Puisque aet bsont premiers entre eux, on obtient d = 1 et finalement au + bv= 1.

Corollaire. Lquation diophantienneax+by =c (a, b Z

, c, x, y Z) possde des solutionsssi cest un multiple de d= pgcd(a, b).

Preuve. Supposons quil existe x et y tels que ax+ by = c. Il suffit de noter que d

diviseaet b donc ax+by i.e. d divise c.

Posons, comme nous lavons dj vu,a = da etb = db aveca etb premiers entre eux.

Le thorme de Bzout montre quil existe deux entiers u et v vrifiant au+ bv = 1.

Ainsi dau + dbv = d, soit au +bv = d. Si c est un multiple de d (c = kd) alors

a(ku) +b(kv) =kd= c.

Corollaire. Un diviseur commun deux entiers divise leur pgcd.

123


5/5

Preuve. Soient a et b deux entiers non nuls et d leur pgcd. On sait dsormais quil existe deux

entiersu et v tels que au + bv=d. Si d diviseaet balors d diviseau + bv i.e. d divised.

Corollaire (inverse modulaire). Un entier non nul a possde un inversemodulo lentier naturel

non nul n (i.e. un entier btel que ab 1 modn) ssi a et n sont premiers entre eux.

Preuve. Par le thorme de Bzout : a et nsont premiers entre eux ssi il existe des entiers u et

v vrifiant au+nv = 1 ssi au 1 modn.

Remarque. Les solutions dune quation diophantienneax+by = c (avec c multiple

de pgcd(a, b)) se reprsentent comme des points rgulirement rpartis sur la droite

dquation ax+by = c soit y =1

b(c ax).

Ceci conduit un algorithme simple (mais peu performant) pour trouver une solution

particulire de cette quation : on vrifie si x = 1, 2, 3, conduit uny entier. Ds que

cest le cas, on a trouv un couple (x, y) solution.

1.5.2 Gauss

Thorme (de Gauss). Soienta, b, ctrois entiers non nuls. Sia divise bcet si a est premier avec

b alors adivise c.

Preuve. On a bc= ka. Puisque a et b dont premiers entre eux, le thorme de Bzout montre

quil existe deux entiersu et v vrifiantau +bv= 1. Il vient c = c.1 =c(au+bv) =cau +(cb)v=

cau+kav = a(cu+kv) i.e. c est un multiple de a.

Corollaire. Si aet bdivisent c et si aet b sont premiers entre eux alors abdivise c.

Preuve. On remarque que bdivise c= ka. Puisque b est premier avec a, le thorme de Gauss

montre que bdivise k (k= lb). Il vient c= ka= lba= l(ab) et ainsi abdivise c.

124

Documents

TS Spé Chap 1 : Cours Divisibilité