Arithmétique dans Z - Exo7
Exo7 Arithmétique dans Z 1 Divisibilité, division euclidienne Exercice 1 Sachant que l’on a 96842=256 375+842, déterminer, sans faire la division, le reste de la division du nombre 96842 par chacun des nombres 256 et 375 Indication H Correction H Vidéo [000251] Exercice 2 Montrer que 8n2N : n(n+1)(n+2)(n+3) est divisible par 24;
Exo7 - Cours de mathématiques
On a bien 0 623 0 pour simplifier Soit N= n 2N jbn 6 a C’est un ensemble non vide car n = 0 2N De plus pour n 2N, on a n 6 a
Exo7 - Cours de mathématiques
« (non P) ou (non Q) » est faux Ainsi dans ce premier cas les assertions sont toutes les deux fausses On dresse ainsi les deux tables de vérités et comme elles sont égales les deux asser-tions sont équivalentes P \ Q V F V F V F V V FIGURE 1 6 – Tables de vérité de « non(P et Q) » et de « (non P) ou (non Q) » 6
Exo7 - Cours de mathématiques
site Exo7 toutes les vidéos correspondant à ce cours, ainsi que des exercices corrigés Au bout du chemin, le plaisir de découvrir de nouveaux univers, de chercher à résoudre des problèmes et d’y parvenir Bonne route
Daniel ALIBERT Arithmétique et algèbre commutative : entiers
Dans cette partie, on rappelle rapidement les principales définitions et les principaux énoncés utilisés Vous devrez vous référer à votre cours pour les démonstrations Vous trouverez des exemples dans la partie 2*Pour Voir 1-1 Arithmétique des entiers Théorème Soient p et q des entiers relatifs, avec q différent de 0
ALGÈBRE ET ARITHMÉTIQUE 1 - Lionel Fourquaux
utiliser le raisonnement par récurrence Ceci sera expliqué dans le chapitre suivant, consacré à l’ensemble des entiers naturels 1 2 Un peu de théorie des ensembles Il est hors de question dans ce cours de fonder rigoureusement la théorie des ensembles et nous nous contenterons des quelques définitions informelles qui suivent
Suites arithmétiques et géométriques - Corrigé
N Duceux – Lycée Paul Doumer – Année 2012/13 Page 1 Suites arithmétiques et géométriques - Corrigé Exercice 1 1) La suite définie pour tout entier par
Brahim BESSAA - الموقع الأول للدراسة في
2- Recherche du minimum et du maximum dans un ensemble de N nombres 3- Calcul du quotient et reste de la division de deux entiers A et B sans utiliser l’opération de division 4- Le calcul du produit de deux entiers en utilisant uniquement l'opération d'addition '+’ 5- Détermination si A est divisible par B Avec A et B des entiers
PYTHON AU LYCÉE - pdfbibcom
Tu découvriras dans ce livre des fractales, des L-systèmes, des arbres browniens et la beauté de phénomènes mathématiques complexes Vous pouvez récupérer l’intégralité des codes Pythondes activités ainsi que tous les fichiers sources sur la page GitHub d’Exo7 : «GitHub : Python au lycée»
Algorithmique et Structures de Données
Dans le cinquième chapitre, l’utilisation des enregistrements et des fichiers dans le cadre de l’algorithmique est expliquée Le sixième chapitre traite la récursivité afin de faciliter l’écriture des algorithmes qui peuvent être récursifs Dans le septième chapitre, nous avons illustré comment calculer la complexité
[PDF] Divisiones de la Geografía - GEOG 3100: Elementos de Geografía
[PDF] geografía humana - Editorial Club Universitario
[PDF] REGIÓN Y REGIONALIZACIÓN - Universidad del Bío-Bío
[PDF] Les démarches visant ? établir l 'identité et l 'obtention de documents
[PDF] 21 rue Jaboulay 69309 LYON cedex 07 T 04 72 80 67 67 F 04 72 71
[PDF] Chapitre 12 : Polynômes - Normalesuporg
[PDF] Polynômes - Exo7 - Emathfr
[PDF] Exercices sur la division euclidienne des polynômes
[PDF] Les organisations vues par Henry Mintzberg - Skynetbe
[PDF] Organisation Territoriale des Collectivités - cci haiti
[PDF] LE TAYLORISME 1 Premier principe : la division verticale du travail
[PDF] Les organisations vues par Henry Mintzberg - Skynetbe
[PDF] Mariage en algerie/divorce en france - Experatoo
[PDF] LISTE DES DOCUMENTS A FOURNIR EN VUE DE LA
![Exo7 - Cours de mathématiques Exo7 - Cours de mathématiques](https://pdfprof.com/Listes/16/27616-16ch_arithmetique.pdf.pdf.jpg)
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 chiffres Voyons cela sur un exemple :N=488889. Icia0=9est le chiffre des unités,a1=8celui des dizaines,... Cette Pour trouver un " bon » représentant dea(modn)on peut aussi faire la division euclidienne deaparn:a=bn+r Les calculs bien menés avec les congruences sont souvent très rapides. Par exemple on souhaite calculer221(mod37) Alors221=2162421. Et il est facile de calculer successivement chacun de ces termes car les exposants sont des Résolvons l"équation9x6(mod24). Commepgcd(9,24) =3divise6la proposition ci-dessus nous affirme qu"il existe des solutions. Nous allons les calculer. (Ilesttoujours préférable de refaire rapidementles calculs que d"apprendre la formule). Trouverxtel que9x6(mod24)est équivalent à trouverxetktels que9x=6+24k. Mis sous la forme9x24k=6il s"agit alors d"une équation que nous avons étudiée en détails (voir section2.3 ). Il y a bien des solutions car pgcd(9,24) =3 divise 6. En divisant par le pgcd on obtient l"équation équivalente : Pour le calcul du pgcd et d"une solution particulière nous utilisons normalement l"algorithme d"Euclide et sa remontée. avons donc trouvé lesxqui sont solutions de3x8k=2, ce qui équivaut à9x24k=6, ce qui équivaut encore à Expliquons le terme de " classe » utilisé ici. Nous avons considéré ici que l"équation9x6(mod24)est une équation d"entiers. On peut aussi considérer que9,x,6sont des classes d"équivalence modulo24, et l"on noterait alors9x=6. Nous avons juste transformé notre équationaxb(modn)en une équationaxkn=bétudiée auparavant Supposons qu"il existe des solutions. Nous allons noterd=pgcd(a,n)et écrirea=da0,n=dn0etb=db0(car par le premier pointdjb). L"équationaxkn=bd"inconnuesx,k2Zest alors équivalente à l"équationa0xkn0=b0, notée(?). Nous savons résoudre cette équation (voir de nouveau la proposition1 ), si(x0,k0)est une solution particulière de(?)alors on connaît tous les(x,k)solutions. En particulierx=x0+`n0avec`2Z(leskne nous Ainsi les solutionsx2Zsont de la formex=x0+`npgcd(a,n),`2Zoùx0est une solution particulière deaxb pask!(sinonpdivise l"un des facteurs dek!mais il sont tous lemme d"Euclidepdivisep k.Preuve du théorème.Nous le montrons par récurrence pour lesa>0. Fixonsa>0et supposons queapa(modp). Calculons(a+1)pà l"aide de la formule du binôme de Newton :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. 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) N=4105+8104+8103+8102+810+9
4+8+8+8+8+9(mod 9)
45(mod 9)et on refait la somme des chiffres de 45
9(mod 9)
0(mod 9)
Ainsi nous savons que 488889 est divisible par 9 sans avoir effectué de division euclidienne. Remarque.
On calcule 2
21, puis on fait la division euclidienne de 221par 37, le reste est notre résultat. C"est laborieux!
2. On calcule successivement les2kmodulo37:212(mod37),224(mod37),238(mod37),2416 (mod37),2532(mod37). Ensuite on n"oublie pas d"utiliser les congruences :266427(mod37). 272262275417(mod37)et ainsi de suite en utilisant le calcul précédent à chaque étape. C"est assez
efficace et on peut raffiner : par exemple on trouve2834(mod37)mais donc aussi28 3(mod37)et donc 292282(3) 631(mod 37),...
3. Il existe une méthode encore plus efficace, on écrit l"exposant21en base2:21=24+22+20=16+4+1. ARITHMÉTIQUE4. CONGRUENCES11
4.2. Équation de congruenceaxb(modn)Proposition 7.
Soit a2Z, b2Zfixés et n>2. Considérons l"équationaxb(modn)d"inconnue x2Z: 1. Il existe des solutions si et seulement si pgcd(a,n)jb. 2.Les solutions sont de la formex=x0+`npgcd(a,n),`2Zoùx0est une solution particulière. Il existe doncpgcd(a,n)
classes de solutions.Exemple 16. 3x8k=2.
9x6(mod 24). Les solutions sont de la formex=6+8`. On préfère les regrouper en 3 classes modulo 24 :
x 1=6+24m,x2=14+24m,x3=22+24mavecm2Z.
Remarque.
2=14,x
3=22. Démonstration.
1. x2Zest un solution de l"équationaxb(modn) () 9k2Zax=b+kn () 9k2Zaxkn=b ()pgcd(a,n)jbpar la proposition1 ARITHMÉTIQUE4. CONGRUENCES12
4.3. Petit théorème de FermatThéorème 4(Petit théorème de Fermat).
Si p est un nombre premier et a2Zalorsa
pa(modp)Corollaire 4. Si p ne divise pas a alorsa
p11(modp)Lemme 3. p divisep kpour16k6p1, c"est-à-direp k0(modp).Démonstration. p k=p!k!(pk)!doncp!=k!(pk)!p k. Ainsipjk!(pk)!p k. Or comme16k6p1alorspne divise Sia=0 alors 00(modp).
Réduisons maintenant modulop:
p1 a p2 a 1quotesdbs_dbs29.pdfusesText_35