[PDF] Arithmétique (Exo7) ARITHMÉTIQUE. 1. DIVISION EUCLIDIENNE





Previous PDF Next PDF



Cours darithmétique

Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él`eves pré- parant les olympiades internationales de mathématiques.



2- La moyenne arithmétique - a) Définition

La moyenne arithmétique d'une série ou moyenne arithmétique simple se calcule par une formule qui est donnée par l'expression :.



Explication de larithmétique binaire qui se sert des seuls caractères

9 oct. 2006 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents whether they are pub-.



CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE

CHAPITRE 3 : CONGRUENCES ET ARITHMÉTIQUE MODULAIRE. 1. Congruences. Définition 1.1. Soit m a



ARITHMETIQUE

Lise Jean-Claude - Cours d'arithmétique -Terminale S. 1/16. ARITHMETIQUE. Partie des mathématiques étudiant les propriétés élémentaires des nombres entiers.



XSane scanned image

En effet si V était réduit à {0}



Concepts de base en arithmétique

s'initier aux exercices d'arithmétique de type olympique. Il rassemble les connaissances nécessaires et suffisantes pour pouvoir résoudre des exercices de 



Les déterminants de la performance arithmétique de 7 à 10 ans

2 nov. 2015 VIII.1 Prédiction de la performance arithmétique en CE2 ... et sur les compétences arithmétiques (calcul mental ; opération écrites ...



Arithmétique (Exo7)

ARITHMÉTIQUE. 1. DIVISION EUCLIDIENNE ET PGCD. 2. Terminologie : q est le quotient et r est le reste. Nous avons donc l'équivalence : r = 0 si et seulement 



Formules concernant les suites arithmétiques et les suites

terme est u12 si le premier terme est noté u1. 5°) Formule permettant de calculer la somme des n premiers termes d'une suite arithmétique : a) S = nombre 

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) =18quotesdbs_dbs22.pdfusesText_28
[PDF] Statistiques et probabilités CORRECTION - sepia

[PDF] Pondichéry - Education Numerique

[PDF] Q ACTIVITÉ N° 1 : « L » D 'illustres scientifiques qui ont contribué ? l

[PDF] Exercice 1 - collège les Eyquems

[PDF] Bon de commande - Hachette Education - Hachette Éducation

[PDF] Règles de calcul concernant les puissances entières

[PDF] code sportif 2006 - Fédération Française de Boxe

[PDF] toi aussi, attache ta ceinture ? l 'arrière - Sécurité routière

[PDF] De la fécondation ? la naissance : 9 mois pour un - Exobiologie

[PDF] La sécurité de nos enfants en voiture - La préfecture de Police

[PDF] Comment faire du feu

[PDF] corr-EC1-environnement - copie - Cours Seko

[PDF] L 'efficacité de la collaboration entre les services de placement

[PDF] Código de la infancia y la adolescencia

[PDF] A quoi ça sert d 'aller ? l 'école?