[PDF] Cours : Arithmétique Par contre ppcm(6 9) =





Previous PDF Next PDF



Arithmétique dans Z - Thomas Richez

Arithmétique dans Z. Thomas Richez. Table des matières. 1. Divisibilité. 1. 2. PGCD et PPCM. 3. 3. Théorème de Bezout. 5. 4. Equations diophantiennes.



Cours darithmétique

Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él`eves Z ensemble des entiers relatifs. Q ensemble des nombres rationnels.



Résumé du cours darithmétique

Université Paris-Sud. Résumé du cours d'arithmétique. Les ensembles N et Z. N = {0 1



Cours : Arithmétique

Par contre ppcm(6 9) = 18 divise bien 36. Mini-exercices. 1. Calculer les coefficients de Bézout correspondant à pgcd(560



Chapitre4 : Arithmétique dans Z

Mais afin de conserver la généralité des énoncés



Arithmétique dans Z et dans Z/nZ

«Neuf personnes sur dix aiment les mathématiques sans calculs» dit-on parfois en cours ou sur les bancs des écoles



COURS - ARITHMÉTIQUE ET ALG`EBRE 2M220 Alain Kraus

Exercice 5. Déterminer tous les nombres premiers p tels que p divise 2p + 1 (utiliser le petit théor`eme de Fermat). Exercice 6 



LARITHMETIQUE

Résumé de Cours D'ARITHMETIQUE. PROF : ATMANI NAJIB. 1BAC SM. A) Divisibilité dans ?. 1)a) et deux entiers relatifs tels que ? 0.



Arithmétique dans Z

Arithmétique dans Z. 1 Divisibilité division euclidienne. Exercice 1. Sachant que l'on a 96842 = 256×375+842



Cours darithmétique

6. Arithmétique. Il existe des variantes de démonstrations par récurrence par exemple : Variante 1 Pour démontrer que P(n) est vrai pour tout n ? n0



Exo7 - Cours de mathématiques

Arithmétique Vidéo Vidéo Vidéo Vidéo partie 1 Division euclidienne et pgcd partie 2 Théorème de Bézout partie 3 Nombres premiers partie 4 Congruences Fiche d’exercices Arithmétique dans Z



Searches related to arithmétique dans z cours

Alors 2(ab + bc + ca) = 8pq + 8qr + 8pr + 8(p + q + r) + 6 donc 2(ab + bc + ca) 6 (mod 8) Montrons par l’absurde que le nombre a2 + b2 + c2 n’est pas le carré d’un nombre entier Supposons qu’il existe n 2 N tel que a2 + b2 + c2 = n2 Nous savons que a2 + b2 + c2 3 (mod 8)

Arithmétique

Vidéo"partie 1. Division euclidienne et pgcd

Vidéo"partie 2. Théorème de Bézout

Vidéo"partie 3. Nombres premiers

Vidéo"partie 4. Congruences

Fiche d"exercices‡Arithmétique dansZ

PréambuleUne motivation : l"arithmétique est au coeur du cryptage des communications. Pour crypter un message on commence

par le transformer en un -ou plusieurs- nombres. Le processus de codage et décodage fait appel à plusieurs notions

de ce chapitre :

On choisit deuxnombres premierspetqque l"on garde secrets et on posen=pq. Le principe étant que même

connaissantnil est très difficile de retrouverpetq(qui sont des nombres ayant des centaines de chiffres).

La clé secrète et la clé publique se calculent à l"aide de l"algorithme d"Euclideet descoefficients de Bézout.

Les calculs de cryptage se ferontmodulon.

Le décodage fonctionne grâce à une variante dupetit théorème de Fermat.

1. Division euclidienne et pgcd

1.1. Divisibilité et division euclidienneDéfinition 1.

Soienta,b2Z. On dit quebdiviseaet on notebjas"il existeq2Ztel quea=bq.Exemple 1.

7j21; 6j48;aest pair si et seulement si 2ja.

Pour touta2Zon aaj0 et aussi 1ja.

Siaj1 alorsa= +1 oua=1.

(ajbetbja) =)b=a (ajbetbjc) =)ajc (ajbetajc) =)ajb+cThéorème 1(Division euclidienne). Soit a2Zet b2Nnf0g. Ilexistedes entiers q,r2Ztels quea=bq+r et06rARITHMÉTIQUE1. DIVISION EUCLIDIENNE ET PGCD2

Terminologie :qest lequotientetrest lereste.

Nous avons donc l"équivalence :r=0 si et seulement sibdivisea.

Exemple 2.

Pour calculerqetron pose la division " classique ». Sia=6789 etb=34 alors

6789=34199+23

On a bien 0623<34 (sinon c"est que l"on n"a pas été assez loin dans les calculs).678934 19934

338306

329
306

23dividendediviseur

quotient reste

Démonstration.

Existence.On peut supposera>0pour simplifier. SoitN=n2Njbn6a. C"est un ensemble non vide car n=02 N. De plus pourn2 N, on an6a. Il y a donc un nombre fini d"éléments dansN, notonsq=maxNle plus grand élément.

Alorsqb6acarq2 N, et(q+1)b>acarq+1=2 N, donc

qb6a<(q+1)b=qb+b. On définit alorsr=aqb,rvérifie alors 06r=aqbUnicité.

Supposons queq0,r0soient deux entiers qui vérifient les conditions du théorème. Tout d"aborda=bq+r=

bq0+r0et doncb(qq0) =r0r. D"autre part06r00 pour avoir1Définition 2.

Soienta,b2Zdeux entiers, non tous les deux nuls. Le plus grand entier qui divise à la foisaetbs"appelle leplus

grand diviseur commundea,bet se note pgcd(a,b).Exemple 3. pgcd(21,14) =7, pgcd(12,32) =4, pgcd(21,26) =1. pgcd(a,ka) =a, pour toutk2Zeta>0. Cas particuliers. Pour touta>0 : pgcd(a,0) =aet pgcd(a,1) =1.

1.3. Algorithme d"EuclideLemme 1.

Soient a,b2N. Écrivons la division euclidienne a=bq+r. Alorspgcd(a,b) =pgcd(b,r)

En fait on a mêmepgcd(a,b) =pgcd(b,aqb)pour toutq2Z. Mais pour optimiser l"algorithme d"Euclide on

applique le lemme avecqle quotient.

Démonstration.

Nous allons montrer que les diviseurs deaet debsont exactement les mêmes que les diviseurs deb etr. Cela impliquera le résultat car les plus grands diviseurs seront bien sûr les mêmes. Soitdun diviseur deaet deb. Alorsddivisebdonc aussibq, en plusddiviseadoncddiviseabq=r.

ARITHMÉTIQUE1. DIVISION EUCLIDIENNE ET PGCD3

Soitdun diviseur debet der. Alorsddivise aussibq+r=a.Algorithme d"Euclide.On souhaite calculer le pgcd dea,b2N. On peut supposera>b. On calcule des divisions euclidiennes successives.

Le pgcd sera le dernier reste non nul.

division deaparb,a=bq1+r1. Par le lemme1 ,pgcd(a,b) =pgcd(b,r1)et sir1=0alorspgcd(a,b) =bsinon on continue : b=r1q2+r2, pgcd(a,b) =pgcd(b,r1) =pgcd(r1,r2), r1=r2q3+r3, pgcd(a,b) =pgcd(r2,r3), rk2=rk1qk+rk, pgcd(a,b) =pgcd(rk1,rk), rk1=rkqk+0. pgcd(a,b) =pgcd(rk,0) =rk.

Comme à chaque étape le reste est plus petit que le quotient on sait que06ri+1

car nous sommes sûrs d"obtenir un reste nul, les restes formant une suite décroissante d"entiers positifs ou nuls :

b>r1>r2>>0.

Exemple 4.

Calculons le pgcd dea=600 etb=124.600=1244+104

124=1041+20

104=205+4

20=45+0

Ainsi pgcd(600,124) =4.

Voici un exemple plus compliqué :

Exemple 5.

Calculons pgcd(9945,3003).

9945=30033+936

3003=9363+195

936=1954+156

195=1561+39

156=394+0

Ainsi pgcd(9945,3003) =39.

1.4. Nombres premiers entre euxDéfinition 3.

Deux entiersa,bsontpremiers entre euxsi pgcd(a,b) =1.Exemple 6.

Pour touta2Z,aeta+1sont premiers entre eux. En effet soitdun diviseur commun àaet àa+1. Alorsddivise

aussia+1a. Doncddivise1mais alorsd=1oud= +1. Le plus grand diviseur deaeta+1est donc1. Et donc pgcd(a,a+1) =1. Si deux entiers ne sont pas premiers entre eux, on peut s"y ramener en divisant par leur pgcd :

Exemple 7.

Pour deux entiers quelconquesa,b2Z, notonsd=pgcd(a,b). La décomposition suivante est souvent utile :

a=a0d b=b0daveca0,b02Zet pgcd(a0,b0) =1Mini-exercices. 1. Écrire la division euclidienne de 111 111par 20 xx, où 20xxest l"année en cours. 2. Montrer qu"un diviseur positif de 10 008et de 10 014appartient nécessairement à f1,2,3,6g.

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT43.Calculer pgcd (560,133), pgcd(12121,789), pgcd(99999,1110).

4.

T rouvertous les entiers 1 6a650 tels queaet 50 soient premiers entre eux. Même question avec 52.2. Théorème de Bézout

2.1. Théorème de BézoutThéorème 2(Théorème de Bézout).

Soient a,b des entiers. Il existe des entiers u,v2Ztels queau+bv=pgcd(a,b)La preuve découle de l"algorithme d"Euclide. Les entiersu,vne sont pas uniques. Les entiersu,vsont descoefficients

de Bézout. Ils s"obtiennent en " remontant » l"algorithme d"Euclide.

Exemple 8.

Calculons les coefficients de Bézout poura=600etb=124. Nous reprenons les calculs effectués pour trouver

pgcd(600,124) =4. La partie gauche est l"algorithme d"Euclide. La partie droite s"obtient debas en haut. On exprime

lepgcdà l"aide de la dernière ligne où le reste est non nul. Puis on remplace le reste de la ligne précédente, et ainsi

de suite jusqu"à arriver à la première ligne.600=1244+1044=

6006+124(29)

124(5)+(6001244)6124=1041+204=

124(5)+1046

104(1241041)5104=205+44=

10420520=45+0

Ainsi pouru=6 etv=29 alors 6006+124(29) =4.

Remarque.

Soignez vos calculs et leur présentation. C"est un algorithme : vous devez aboutir au bon résultat! Dans la partie

droite,ilfautà chaque ligne bien la reformater. Parexemple104(1241041)5se réécriten124(5)+1046

afin de pouvoir remplacer ensuite 104.

N"oubliez pas de vérifier vos calculs! C"est rapide et vous serez certains que vos calculs sont exacts. Ici on vérifie à

la fin que 6006+124(29) =4.

Exemple 9.

Calculons les coefficients de Bézout correspondant à pgcd(9945,3003) =39.9945=30033+93639=9945(16)+3003533003=9363+19539=

936=1954+15639=

195=1561+3939=1951561156=394+0

À vous de finir les calculs. On obtient 9945(16)+300353=39.

2.2. Corollaires du théorème de BézoutCorollaire 1.

Si dja et djb alors djpgcd(a,b).Exemple : 4j16 et 4j24 donc 4 doit diviser pgcd(16,24)qui effectivement vaut 8.

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT5

Démonstration.Commedjauetdjbvdoncdjau+bv. Par le théorème de Bézoutdjpgcd(a,b).Corollaire 2.

Soient a,b deux entiers. a et b sont premiers entre euxsi et seulement siil existe u,v2Ztels queau+bv=1Démonstration.Le sens)est une conséquence du théorème de Bézout.Pour le sens(on suppose qu"il existeu,vtels queau+bv=1. Commepgcd(a,b)jaalorspgcd(a,b)jau. De même

pgcd(a,b)jbv. Donc pgcd(a,b)jau+bv=1. Donc pgcd(a,b) =1.Remarque.

Si on trouve deux entiersu0,v0tels queau0+bv0=d, cela n"impliquepasqued=pgcd(a,b). On sait seulement alors

que pgcd(a,b)jd. Par exemplea=12,b=8; 121+83=36 et pgcd(a,b) =4.Corollaire 3(Lemme de Gauss).

Soient a,b,c2Z.Si ajbc etpgcd(a,b) =1alors ajcExemple : si 4j7c, et comme 4 et 7 sont premiers entre eux, alors 4jc.

Démonstration.

Commepgcd(a,b) =1alors il existeu,v2Ztels queau+bv=1. On multiplie cette égalité parc

pour obteniracu+bcv=c. Maisajacuet par hypothèseajbcvdoncadiviseacu+bcv=c.2.3. Équationsax+by=cProposition 1.

Considérons l"équation

ax+by=c(E) où a,b,c2Z. 1.

L "équation(

E ) possède des solutions(x,y)2Z2si et seulement sipgcd(a,b)jc. 2.

Sipgcd(a,b)jcalors il existe même une infinité de solutions entières et elles sont exactement les(x,y) = (x0+

k,y0+k)avec x0,y0,,2Zfixés et k parcourantZ.

Le premier point est une conséquence du théorème de Bézout. Nous allons voir sur un exemple comment prouver

le second point et calculer explicitement les solutions. Il est bon de refaire toutes les étapes de la démonstration à

chaque fois.

Exemple 10.

Trouver les solutions entières de

161x+368y=115 (E)

Première étape. Y a-t-il des solutions? L"algorithme d"Euclide.

On effectue l"algorithme d"Euclide pour calculer

le pgcd dea=161 etb=368.

368=1612+46

161=463+23

46=232+0

Doncpgcd(368,161) =23. Comme115=523alorspgcd(368,161)j115. Par le théorème de Bézout, l"équation

E ) admet des solutions entières.

Deuxième étape. Trouver une solution particulière : la remontée de l"algorithme d"Euclide.

On effectue la

remontée de l"algorithme d"Euclide pour calculer les coefficients de Bézout.

368=1612+46

161=463+23

46=232+023=1617+368(3)

161+(3682161)(3)

23=161346

ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT6

On trouve donc 1617+368(3) =23. Comme 115=523 en multipliant par 5 on obtient :

16135+368(15) =115

Ainsi(x0,y0) = (35,15)est unesolution particulièrede (E).

Troisième étape. Recherche de toutes les solutions.Soit(x,y)2Z2une solution de (E). Nous savons que

(x0,y0)est aussi solution. Ainsi :

161x+368y=115 et 161x0+368y0=115

(on n"a aucun intérêt à remplacerx0ety0par leurs valeurs). La différence de ces deux égalités conduit à

161(xx0)+368(yy0) =0

=)237(xx0)+2316(yy0) =0 =)7(xx0) =16(yy0) ()

Nous avons simplifié par23qui est le pgcd de161et368. (Attention, n"oubliez surtout pas cette simplification,

sinon la suite du raisonnement serait fausse.) Ainsi7j16(yy0),orpgcd(7,16) =1donc parle lemme de Gauss7jyy0. Ilexiste donck2Ztelqueyy0=7k. Repartant de l"équation():7(xx0) =16(yy0). On obtient maintenant7(xx0) =167k. D"où xx0=16k. (C"est le mêmekpourxet poury.) Nous avons donc(x,y) = (x016k,y0+7k). Il n"est pas dur de voir que tout couple de cette forme est solution de l"équation ( E ). Il reste donc juste à substituer(x0,y0)par sa

valeur et nous obtenons :Les solutions entières de 161x+368y=115 sont les(x,y) = (3516k,15+7k),kparcourantZ.Pour se rassurer, prenez une valeur dekau hasard et vérifiez que vous obtenez bien une solution de l"équation.

2.4. ppcmDéfinition 4.

Le ppcm(a,b)(plus petit multiple commun) est le plus petit entier>0 divisible paraet parb.Par exemple ppcm(12,9) =36.

Le pgcd et le ppcm sont liés par la formule suivante :Proposition 2. Si a,b sont des entiers (non tous les deux nuls) alorspgcd(a,b)ppcm(a,b) =jabjDémonstration. Posonsd=pgcd(a,b)etm=jabjpgcd(a,b). Pour simplifier on supposea>0etb>0. On écrita=da0et b=db0. Alorsab=d2a0b0et doncm=da0b0. Ainsim=ab0=a0best un multiple deaet deb.

Il reste à montrer que c"est le plus petit multiple. Sinest un autre multiple deaet debalorsn=ka=`bdonc

kda0=`db0etka0=`b0. Or pgcd(a0,b0) =1 eta0j`b0donca0j`. Donca0bj`bet ainsim=a0bj`b=n.Voici un autre résultat concernant le ppcm qui se démontre en utilisant la décomposition en facteurs premiers :

Proposition 3.

Si ajc et bjc alors ppcm(a,b)jc.

Il serait faux de penser queabjc. Par exemple6j36,9j36mais69ne divise pas36. Par contreppcm(6,9) =18 divise bien 36.Mini-exercices. 1. Calculer les coefficients de Bézout correspondant à pgcd (560,133), pgcd(12121,789). 2. Montrer à l"aide d"un corollaire du théorème de Bézout que pgcd (a,a+1) =1. 3. R ésoudreles équations : 407 x+129y=1; 720x+54y=6; 216x+92y=8. 4. T rouverles couples (a,b)vérifiant pgcd(a,b) =12 et ppcm(a,b) =360.

ARITHMÉTIQUE3. NOMBRES PREMIERS7

3. Nombres premiersLes nombres premiers sont -en quelque sorte- les briques élémentaires des entiers : tout entier s"écrit comme produit

de nombres premiers.

3.1. Une infinité de nombres premiersDéfinition 5.

Unnombre premierpest un entier>2 dont les seuls diviseurs positifs sont 1 etp.Exemples : 2,3,5,7,11 sont premiers, 4=22, 6=23, 8=24 ne sont pas premiers.Lemme 2.

Tout entier n>2admet un diviseur qui est un nombre premier.Démonstration.SoitDl"ensemble des diviseurs denqui sont>2 :

D=k>2jkjn.

L"ensembleDest non vide (carn2 D), notons alorsp=minD. Supposons, par l"absurde, quepne soit pas un nombre premier alorspadmet un diviseurqtel que1alorsqest aussi un diviseur denet doncq2 Davecq Conclusion :pest un nombre premier. Et commep2 D,pdivisen.Proposition 4. Il existe une infinité de nombres premiers.Démonstration. Par l"absurde, supposons qu"il n"y ait qu"un nombre fini de nombres premiers que l"on notep1=2, p2=3,p3,...,pn. Considérons l"entierN=p1p2pn+1. Soitpun diviseur premier deN(un telpexiste par

le lemme précédent), alors d"une partpest l"un des entierspidoncpjp1pn, d"autre partpjNdoncpdivise la

différenceNp1pn=1. Cela implique quep=1, ce qui contredit quepsoit un nombre premier.

Cette contradiction nous permet de conclure qu"il existe une infinité de nombres premiers.3.2. Eratosthène et Euclide

Comment trouver les nombres premiers? Lecrible d"Eratosthènepermet de trouver les premiers nombres premiers.

Pour cela on écrit les premiers entiers : pour notre exemple de 2 à 25.

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Rappelons-nous qu"un diviseur positif d"un entiernest inférieur ou égal àn. Donc2ne peut avoir comme diviseurs

que1et2et est donc premier. On entoure2. Ensuite on raye (ici en grisé) tous les multiples suivants de2qui ne

seront donc pas premiers (car divisible par 2) :

23 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Le premier nombre restant de la liste est3et est nécessairement premier : il n"est pas divisible par un diviseur plus

petit (sinon il serait rayé). On entoure 3 et on raye tous les multiples de 3 (6, 9, 12, ...). 2

34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Le premier nombre restant est 5 et est donc premier. On raye les multiples de 5. 2 34

56 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

7est donc premier, on raye les multiples de7(ici pas de nouveaux nombres à barrer). Ainsi de suite :11,13,17,19,23

sont premiers. 2 34
56

78 9 10

1112

1314 15 16

1718

1920 21 22

23

ARITHMÉTIQUE3. NOMBRES PREMIERS8

Remarque.Si un nombrenn"est pas premier alors un de ses facteurs est6pn. En effet sin=abaveca,b>2alorsa6pn

oub6pn(réfléchissez par l"absurde!). Par exemple pour tester si un nombre6100est premier il suffit de tester les

diviseurs610. Et comme il suffit de tester les diviseurs premiers, il suffit en fait de tester la divisibilité par2,3,5et7.

Exemple : 89 n"est pas divisible par 2,3,5,7 et est donc un nombre premier.Proposition 5(Lemme d"Euclide).

Soit p un nombre premier. Si pjab alors pja ou pjb.Démonstration. Sipne divise pasaalorspetasont premiers entre eux (en effet les diviseurs depsont1etp, mais seul 1 divise aussia, donc pgcd(a,p) =1). Ainsi par le lemme de Gausspjb.Exemple 11. Sipest un nombre premier,ppn"est pas un nombre rationnel. La preuve se fait par l"absurde : écrivonspp=abaveca2Z,b2Netpgcd(a,b) =1. Alorsp=a2b

2doncpb2=a2.

Ainsipja2donc par le lemme d"Euclidepja. On peut alors écrirea=pa0aveca0un entier. De l"équationpb2=a2on

tire alorsb2=pa02. Ainsipjb2et doncpjb. Maintenantpjaetpjbdoncaetbne sont pas premiers entre eux. Ce qui

contredit pgcd(a,b) =1. Conclusionppn"est pas rationnel.

3.3. Décomposition en facteurs premiersThéorème 3.

Soitn>2un entier. Il existe des nombres premiersp11tels que : n=p1 1p2 2prr.

De plus les p

iet lesi(i=1,...,r) sont uniques.

Exemple :24=233est la décomposition en facteurs premiers. Par contre36=229n"est pas la décomposition en

facteurs premiers, c"est 2232.

Remarque.

La principale raison pour laquelle on choisit de dire que1n"est pas un nombre premier, c"est que sinon il n"y aurait

plus unicité de la décomposition : 24=233=1233=12233=

Démonstration.

Existence.Nous allons démontrer l"existence de la décomposition par une récurrence surn.

L"entiern=2est déjà décomposé. Soitn>3, supposons que tout entier

premiers. Notonsp1le plus petit nombre premier divisantn(voir le lemme2 ). Sinest un nombre premier alors

n=p1et c"est fini. Sinon on définit l"entiern0=np

1 une décomposition en facteurs premiers. Alorsn=p1n0admet aussi une décomposition.

Unicité.

Nous allons démontrer qu"une telle décomposition est unique en effectuant cette fois une récurrence sur la

somme des exposants=Pr i=1i. Si=1 cela signifien=p1qui est bien l"unique écriture possible.

Soit>2. On suppose que les entiers dont la somme des exposants est< ont une unique décomposition. Soitnun

entier dont la somme des exposants vaut. Écrivons le avec deux décompositions : n=p1 1p2

2prr=q1

1q2 2qss. (On ap12 prr=nmais ne divise pas

q1 1q2

2qss=n. Ce qui est absurde. Doncp1>q1.

Sip1>q1un même raisonnement conduit aussi à une contradiction. On conclut quep1=q1. On pose alors

n 0=np 1=p11 1p2

2prr=q11

1q2 2qss

L"hypothèse de récurrence qui s"applique àn0implique que ces deux décompositions sont les mêmes. Ainsir=set

pi=qi,i=i,i=1,...,r.

ARITHMÉTIQUE4. CONGRUENCES9

Exemple 12.

504=23327, 300=22352.

Pour calculer le pgcd on réécrit ces décompositions :

504=23325071, 300=22315270.

Le pgcd est le nombre obtenu en prenant le plus petit exposant de chaque facteur premier : pgcd(504,300) =22315070=12. Pour le ppcm on prend le plus grand exposant de chaque facteur premier : ppcm(504,300) =23325271=12600Mini-exercices. 1. Montrer que n!+1 n"est divisible par aucun des entiers 2,3,...,n. Est-ce toujours un nombre premier? 2.

T rouvertous les nombres premiers 6103.

3. Décomposer a=2340 etb=15288 en facteurs premiers. Calculer leur pgcd et leur ppcm. 4. Décomposer 48 400en produit de facteurs premiers. Combien 48 400admet-il de diviseurs ?

5.Soienta,b>0. À l"aide de la décomposition en facteurs premiers,reprouverla formulepgcd(a,b)ppcm(a,b) =

ab.4. Congruences

4.1. DéfinitionDéfinition 6.

Soitn>2 un entier. On dit queaestcongruàbmodulon, sindiviseba. On note alors

ab(modn).On note aussi parfoisa=b(modn)ouab[n]. Une autre formulation estab(modn)() 9k2Za=b+kn.Remarquez quendiviseasi et seulement sia0(modn).Proposition 6.

1. La relation " congru modulo n » est une relation d"équivalence : (Réflexivité) aa(modn), (Symétrie) si ab(modn)alors ba(modn), (Transitivité) si ab(modn)et bc(modn)alors ac(modn). 2.

Si a b(modn)et cd(modn)alors a+cb+d(modn).

3.

Si a b(modn)et cd(modn)alors acbd(modn).

4. Si a b(modn)alors pour tout k>0, akbk(modn).Exemple 13.

151(mod 7), 722(mod 7), 3 11(mod 7),

5x+83(mod 5)pour toutx2Z,

1120xx120xx1(mod 10), où 20xxest l"année en cours.

Démonstration.

1.

Utiliser la définition.

2. Idem.

ARITHMÉTIQUE4. CONGRUENCES10

3.Prouvons la propriété multiplicative :ab(modn)donc il existek2Ztel quea=b+knetcd(modn)

donc il existe`2Ztel quecd+`n. Alorsac= (b+kn)(d+`n) =bd+(b`+dk+k`n)nqui est bien de la formebd+mnavecm2Z. Ainsiacbd(modn). 4.

C"est une conséquence du point précédent : aveca=cetb=don obtienta2b2(modn). On continue par

récurrence.Exemple 14. Critère de divisibilité par9.Nest divisible par 9 si et seulement si la somme de ses chiffres est divisible par 9.

Pour prouver cela nous utilisons les congruences. Remarquons d"abord que9jNéquivaut àN0(mod9)et notons

aussi que 101(mod 9), 1021(mod 9), 1031(mod 9),...

Nous allons donc calculerNmodulo9. ÉcrivonsNen base10:N=aka2a1a0(a0est le chiffre des unités,a1celui

des dizaines,...) alorsN=10kak++102a2+101a1+a0. Donc

N=10kak++102a2+101a1+a0

ak++a2+a1+a0(mod 9)

DoncNest congru à la somme de ses chiffres modulo9. AinsiN0(mod9)si et seulement si la somme des chiffres

quotesdbs_dbs49.pdfusesText_49
[PDF] arithmétique dans z exercices corrigés mpsi

[PDF] arithmétique exercices et problèmes

[PDF] arithmétique terminale s exercices corrigés

[PDF] arjel analyse trimestrielle

[PDF] arjel t1 2016

[PDF] arjel t2 2016

[PDF] armande le pellec muller

[PDF] armature urbaine définition

[PDF] armement du chevalier

[PDF] armes autorisées en belgique

[PDF] armor electric system

[PDF] arnold blueprint to cut

[PDF] arrêt 7 mai 2008 rétractation de l'offre

[PDF] arret de bus pont du chateau

[PDF] arret de grossesse symptomes