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"exercicesArithmé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 et06rTerminologie :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 alors6789=34199+23
On a bien 0623<34 (sinon c"est que l"on n"a pas été assez loin dans les calculs).678934 19934338306
329306
23dividendediviseur
quotient resteDé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=aqbSupposons 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 part06r0Soienta,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 : Pour touta2Z,aeta+1sont premiers entre eux. En effet soitdun diviseur commun àaet àa+1. Alorsddivise Pour deux entiers quelconquesa,b2Z, notonsd=pgcd(a,b). La décomposition suivante est souvent utile : ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT43.Calculer pgcd (560,133), pgcd(12121,789), pgcd(99999,1110). 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 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 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 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 N"oubliez pas de vérifier vos calculs! C"est rapide et vous serez certains que vos calculs sont exacts. Ici on vérifie à Calculons les coefficients de Bézout correspondant à pgcd(9945,3003) =39.9945=30033+93639=9945(16)+3003533003=9363+19539= Si dja et djb alors djpgcd(a,b).Exemple : 4j16 et 4j24 donc 4 doit diviser pgcd(16,24)qui effectivement vaut 8. 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 Si on trouve deux entiersu0,v0tels queau0+bv0=d, cela n"impliquepasqued=pgcd(a,b). On sait seulement alors Soient a,b,c2Z.Si ajbc etpgcd(a,b) =1alors ajcExemple : si 4j7c, et comme 4 et 7 sont premiers entre eux, alors 4jc. pour obteniracu+bcv=c. Maisajacuet par hypothèseajbcvdoncadiviseacu+bcv=c.2.3. Équationsax+by=cProposition 1. Sipgcd(a,b)jcalors il existe même une infinité de solutions entières et elles sont exactement les(x,y) = (x0+ 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 à Doncpgcd(368,161) =23. Comme115=523alorspgcd(368,161)j115. Par le théorème de Bézout, l"équation Deuxième étape. Trouver une solution particulière : la remontée de l"algorithme d"Euclide. Troisième étape. Recherche de toutes les solutions.Soit(x,y)2Z2une solution de (E). Nous savons que (on n"a aucun intérêt à remplacerx0ety0par leurs valeurs). La différence de ces deux égalités conduit à Nous avons simplifié par23qui est le pgcd de161et368. (Attention, n"oubliez surtout pas cette simplification, 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. Le ppcm(a,b)(plus petit multiple commun) est le plus petit entier>0 divisible paraet parb.Par exemple ppcm(12,9) =36. 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 : 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 : le lemme précédent), alors d"une partpest l"un des entierspidoncpjp1pn, d"autre partpjNdoncpdivise la 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. 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 Le premier nombre restant de la liste est3et est nécessairement premier : il n"est pas divisible par un diviseur plus 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). 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 Exemple :24=233est la décomposition en facteurs premiers. Par contre36=229n"est pas la décomposition en La principale raison pour laquelle on choisit de dire que1n"est pas un nombre premier, c"est que sinon il n"y aurait 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 Nous allons démontrer qu"une telle décomposition est unique en effectuant cette fois une récurrence sur la Soit>2. On suppose que les entiers dont la somme des exposants est< ont une unique décomposition. Soitnun Sip1>q1un même raisonnement conduit aussi à une contradiction. On conclut quep1=q1. On pose alors L"hypothèse de récurrence qui s"applique àn0implique que ces deux décompositions sont les mêmes. Ainsir=set 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. C"est une conséquence du point précédent : aveca=cetb=don obtienta2b2(modn). On continue par Pour prouver cela nous utilisons les congruences. Remarquons d"abord que9jNéquivaut àN0(mod9)et notons Nous allons donc calculerNmodulo9. ÉcrivonsNen base10:N=aka2a1a0(a0est le chiffre des unités,a1celui DoncNest congru à la somme de ses chiffres modulo9. AinsiN0(mod9)si et seulement si la somme des chiffresExemple 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. Exemple 7.
2.1. Théorème de BézoutThéorème 2(Théorème de Bézout).
Exemple 8.
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.
Exemple 9.
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.
ARITHMÉTIQUE2. THÉORÈME DEBÉZOUT5
Démonstration.
Commepgcd(a,b) =1alors il existeu,v2Ztels queau+bv=1. On multiplie cette égalité parc 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. 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
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). 161x+368y=115 et 161x0+368y0=115
161(xx0)+368(yy0) =0
=)237(xx0)+2316(yy0) =0 =)7(xx0) =16(yy0) () 2.4. ppcmDéfinition 4.
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.
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
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
23 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
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
2doncpb2=a2.
3.3. Décomposition en facteurs premiersThéorème 3.
Soitn>2un entier. Il existe des nombres premiersp1De plus les p
iet lesi(i=1,...,r) sont uniques. Remarque.
Démonstration.
Existence.Nous allons démontrer l"existence de la décomposition par une récurrence surn. 1
q1 1q2 Unicité.
2prr=q1
1q2 2qss. (On ap12qss=n. Ce qui est absurde. Doncp1>q1.
2prr=q11
1q2 2qss 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 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. N=10kak++102a2+101a1+a0
ak++a2+a1+a0(mod 9)
[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