cours d`introduction
Contents
1.2. cp D monstration Soit A 1 2 p 1 Soit B l ensemble des restes modulo p de a 2a 3a p lja Tous les l ments de B sont des l ments de en effet si 1 lt k lt p 1 alors ka n est pas divisible par p donc son reste modulo p est compris entre 1 et p 1 De plus les l ments a 2a p 1 a sont deux deux distincts modulo p en effet sil lt k lt lt p 1et ka fa p comme a est inversible modulo p en simplifiant par a on obtient k mod p donc k On en d duit que B poss de p 1 l ments Comme A poss de le m me nombre d l ments on a B et donc le produit de tous les l ments de est gal au produit de tous les l ments de B ce qui s crit 1X2x x p 1 a x 2a x 3a X p 1 a mod p En simplifiant par 1 x 2 x p 1 on obtient 1 aP p Exemple d application soit calculer 21000 modulo 7 On sait que 26 1 7 Comme 1000 6 x 166 4 on a 91000 96x166 94 28 268 x 16 116 x 2 72 7 Exercice 3 10 a Pour quelles valeurs de n N 6H 5n 2 est il divisible par 7 b Quel est le reste de la division de 70543250 par 11 c Pour quelles valeurs de n N 5 5 2 est il divisible par 7 d Pour quelles valeurs de n N 81n 45n 4n est il divisible par 5 Exercice 3 11 Quel est le dernier chiffre de l criture
3. Th or me 2 12 Euclide Il existe une infinit de nombres premiers D monstration Supposons par l absurde qu il n existe qu un nombre fini de nombres premiers p lt po lt lt pr avec p 2 p2 3 etc Soit n pip2 pr 1 On a n gt p 2 Soit p le plus petit diviseur premier de n D apr s la proposition pr c dente p est un nombre premier donc p figure dans la liste p1 pr Par cons quent p pipe pr n 1 Comme p n on en d duit que p n n 1 1 donc p lt 1 Impossible Exercice 2 13 1 Montrer que tout nombre premier gt 3 peut s crire soit sous la forme 4k 1 soit sous la forme 4k 1 2 Montrer qu il existe une infinit de nombres premiers de la forme 4k 1 On pourra former un nombre de la forme 4 p1 p 1 Remarque 2 13 Il y a des r sultats bien plus pr cis sur la r partition des nombres premiers Par exemple le postulat de Bertrand dit que pour tout n gt 2 il existe au moins un nombre premier p tel que n lt p lt 2n La d monstration de ce th or me est trop longue pour tre expos e ici D finition 2 14 Deux entiers a et b sont dits premiers entre eux si l unique diviseur commun strictement positif est 1 Autrement dit PGCD a b 1 Par exemple 6 et 35 sont premiers entre eux mais 14 et 35 ne le sont pas Exercice 2 14 1 Quels sont les enti
4. Quels sont les entiers n lt 1000 tels que T n 7 Exercice 2 30 Montrer que T n lt 24 n pour tout n Exercice 2 31 Un jardinier doit planter 480 arbustes en n rang es gales contenant au moins 6 arbustes De combien de mani res peut il le faire Exercice 2 32 N est divisible par 6 N n est pas divisible par 8 et N a exactement 15 diviseurs Que vaut N Exercice 2 33 quelle condition un entier n admet il un nombre impair de diviseurs Exercice 2 34 Montrer que si m et n sont premiers entre eux alors r mn T m r n Est il vrai que si r mn T m r n alors m et n sont premiers entre eux 17 3 Congruences 3 1 D finition et propri t s de base D finition 3 1 Soit n un entier non nul On dit que a et b sont congrus modulo n si n divise a b On note a b n ou encore a b mod n Lorsque l on effectue une division Euclidienne de a par n sous la forme a nq r on a a rfn donc tout entier est congru modulo n un et un seul entier parmi 0 1 n 1 Une autre mani re de d finir la congruence modulo n est de dire que a bjn si et seulement si les restes des divisions Euclidiennes de a et de b par n sont gaux La congruence se comporte comme l galit Proposition 3 2 Soient a b c des entiers et n un entier non nul r flexivit a a n sym trie si a b n a
5. ab b n op Qa tous les termes se sont simplifi s except le premier et le dernier L identit pr c dente tant vraie pour tout couple a b elle est vraie pour le couple a b donc a b a tb ar babe Si n est impair on a b b et b 1 b 71 d o la derni re galit Comme cas particulier de la septi me galit on trouve pour b 1 a 1 a 1 1 a a a t Ceci tant vrai pour tout entier n l galit est vraie pour n 1 la place de n ce qui donne a i 1 a 1 1 a a a En divisant par a 1 si a Z 1 on obtient l identit 1 a a a anti a 1 Exercice 4 1 Nombres premiers de Mersenne Montrer que si a gt 2 et n gt 2 sont des entiers tels que a 1 est un nombre premier alors a 2 et n est premier Remarque on constate que M2 3 M3 7 M5 31 M7 127 M 8191 M7 131071 et Mio 524287 sont premiers En revanche M 23 x 89 et M 3 47 x 178481 sont compos s On ignore s il existe une infinit de nombres premiers de Mersenne Exercice 4 2 Nombres premiers de Fermat Montrer que si 2 1 est premier alors n est une puissance de 2 On montrera que n n admet pas de diviseur impair Remarque on pose Fk 22 1 On constate que Fo 3 Fi 5 Fo 17 F3 257 F1 65537 s
6. 1 est un multiple de n donc il existe v tel que au 1 nv On obtient alors une relation de B zout au n v 1 donc a et n sont premiers entre eux R ciproquement si a et n sont premiers entre eux alors il existe une relation de B zout au nv 1 En passant modulo n les deux membres de l galit on en d duit que au 1 n donc a est inversible modulo n Montrons maintenant l unicit Supposons que b et b sont deux inverses de a modulo n Alors b b x 1 b ab ba b 1 x b b n donc b et b sont congrus modulo n Remarquons que la d monstration ci dessus donne un algorithme pour calculer l inverse d un nombre modulo n il suffit de trouver une relation de B zout gr ce l algorithme d Euclide tendu Proposition 3 11 Si a est inversible modulo n et si ax ay n alors x y n D monstration Soit b un inverse de a modulo n On a x ba x b ax b ay ba y y n On peut donc simplifier par a une congruence modulo n si a est inversible modulo n L hypoth se que a est inversible modulo n est n cessaire puisque 2 x 3 2 x 8 10 bien que 3 8 10 21 Exercice 3 8 V rifier que les inversibles modulo 8 sont 1 3 5 7 et qu ils sont tous gaux leurs inverses Exercice 3 9 Trouver l inverse de 37 modulo 53 Proposition 3 12 Si a et b sont inversibles modulo p alors a
7. Si n est premier on a n cessairement r s 1 donc p q1 Supposons donc n non premier D apr s le Lemme de Gauss comme p divise qg1q2 q il divise l un des nombres qi qs dont p est gal l un de ces nombres Quitte changer l ordre des q1 qs on peut supposer que p q On a alors P2 Pr 2 Or P p1 pr est vraie par hypoth se de r currence donc p2 p est gal g2 qs l ordre pr s Plut t que d crire une d composition sous la forme 84 2 x 2 x 3 x 7 on pr f re une criture du type 84 2 x 3 x 7 Plus g n ralement un entier n peut s crire sous la forme n pi p3 pe avec p lt p2 lt lt pr premiers L entier j s appelle la valuation pj adique de n et se note vp n Pour tout nombre premier p l entier v n est le plus grand entier m tel que p divise n Par exemple v2 84 2 v3 84 1 v5 84 0 vp 1 0 pour tout p Exercice 2 19 Combien vaut v3 18100 Exercice 2 20 Combien vaut v2 2100 2200 14 Exercice 2 21 Soitn 1x2x 3x x 100 a D terminer v7 n b D terminer le nombre de z ros de n dans son criture d cimale Proposition 2 24 Soient a et b des entiers 1 i vp ab vy a vp b pour tout p premier ii a b si et seulement si pour tout entier premier p on a w a lt vp b iii vpla Ab min v
8. a3 11 Exercice 3 4 98473092 est il divisible par 11 Proposition 3 7 n est divisible par 4 si et seulement si ajao est divisible par 4 D monstration a ta azaz_1 a200 est divisible par 100 donc par 4 Proposition 3 8 n est divisible par 8 si et seulement si azaiag est divisible par 8 D monstration Analogue Exercice 3 5 3645 45 est un entier Sans effectuer la division montrer que Exercice 3 6 Le PGCD de 193116 et de 127413 est il pair Est il divisible par 3 Par 9 Par 11 Par 33 Par 99 Exercice 3 7 T quelle condition sur les chiffres x et y le nombre 27r85y est il divisible par 33 20 3 3 Inverses modulo n D finition 3 9 Un entier b est appel inverse de a modulo n si et seulement si ab 1 n Si a poss de un inverse modulo n alors on dit que a est inversible modulo n Par exemple 3 est inverse de 5 modulo 7 car 3 x 5 15 est congru 1 modulo 7 Les nombres 4 3 10 17 24 31 sont tous inverses de 5 modulo 7 car 3 7k x 5 15 7 5k 15 1 7 Proposition 3 10 a est inversible modulo n si et seulement si a et n sont premiers entre eux L inverse de a est alors unique modulo n D monstration Si a est inversible modulo n alors il existe u tel que au 1 n Par d finition cela signifie que au
9. Alors il y a exactement pit carr s modulo p D monstration D apr s la discussion pr c dente tout carr modulo p est congru k pour un certain entier 0 lt k lt PT On voit d j qu il y a au plus PIL carr s modulo 2 p Pour conclure il reste montrer que S0 lt k lt 4 L lt alors k et ne sont pas congrus modulo p En effet dans le cas contraire p diviserait k l k l k Or 1 lt L k lt L Ek lt p 1 donc p ne divise ni l k ni k et par suite p ne divise pas k ce qui est contradictoire 24 Exercice 3 14 Donner la liste de tous les carr s modulo 5 et de tous les carr s modulo 8 Exercice 3 15 Existe t il des entiers a b c tels que a b c 1010 7 Exercice 3 16 3 est il un carr modulo 103 On s int resse la question suivante 1 est il un carr modulo n Par exemple pour n 5 on a 1 4 5 et 4 22 donc 1 est un carr modulo 5 Par contre on v rifie facilement que 1 n est pas un carr modulo 3 Proposition 3 18 Si p est un nombre premier impair et 1 est un carr modulo p alors p 1 4 D monstration Comme p est impair on peut crire p sous la forme p 2m 1 Soit a tel que a 1 p Alors a n est pas divisible par p sinon on aurait a 0 p donc on peut appliquer le petit th or me de Fermat a Si m est impair a
10. Si a 0 ou b 0 l assertion est vidente Supposons donc a gt 0 et b gt 0 Quitte changer a et b on peut supposer que a gt b On applique l algorithme d Euclide on pose ao a et a b On observe que ao aug bvo a au bvi avec uo l vo 0 u1 0 v1 1 L id e est de chercher crire ax sous la forme ax aux buk pour tout k On a ensuite a2 ao a1q auo bvo gi au bv1 uo qiu Ja vo qui donc az auz bu avec u2 uo Qui et V2 vo q1 On continue ainsi de proche en proche jusqu an comme an An 2 Qn 14n 1 et comme an 2 et an s expriment en fonction de a et b on peut exprimer a en fonction de a et b Plus pr cis ment on a an aUn bUn avec Un Un 2 Qn 1Un 1 t Un Un 2 Qn 1Vn 1 On obtient ainsi d au bv avec d an U Un et vY Vn Cet algorithme s appelle l algorithme d Euclide tendu Montrons ii Si m est un multiple de d alors il existe tel que m Ad On a alors m Au a Av b R ciproquement si m au bv alors comme d divise a et b il divise au bv donc d divise m Montrons iii Si au bv 1 alors PGCD a b divise 1 donc est gal 1 La r ciproque a d j t prouv e en premi re partie Remarque 2 18 Plus g n ralement pour tous a1 an il existe u1 Un tels que aiu azu2 anun PGC D a1
11. d cimale de 73 Exercice 3 12 271 est il divisible par 3 5 7 9 11 23 3 5 Carr s modulo n Pour illustrer la notion de carr modulo n commen ons par un exercice Exercice 3 13 Existe t il des entiers a et b tels que a b 10100 37 D monstration La r ponse est non L id e est de raisonner modulo 4 On a 0 0 4 1 1 4 22 0 4 32 1 4 On en d duit que pour tous a b les entiers a et b sont congrus 0 ou 1 modulo 4 Par cons quent a b est congru 0 1 ou 2 modulo 4 Or 10100 3 est congru 3 modulo 4 donc ne peut pas tre gal a b Ceci conduit la D finition 3 16 Un entier a est un carr modulo n s il existe b tel que a b n Observons par exemple les carr s modulo 13 x 0111213 41 51 6 7 8 1911011712 1011 419 3112 10 10 1 3 9 411 Dans la deuxi me ligne on a crit le reste de la division Euclidienne de x par 13 On constate une sym trie ce n est pas un hasard puisque 12 13 1 1 1 13 11 13 2 2 13 etc Pour trouver la liste des carr s modulo n il suffit juste de calculer k modulo n pour D lt EK SZ Dans l exemple pr c dent on voit qu il y a exactement sept carr s modulo 13 savoir 0 1 3 4 9 10 13 Plus g n ralement Proposition 3 17 Soit p un nombre premier impair
12. de a et b Calculons par exemple le PGCD de 183 et 117 par ce proc d 183 117 x 1 66 117 66 x 1 51 66 51 x1 15 51 115 x3 16 15 161xX2 13 6 131x2 10 On a encadr les termes ao 1 n 1 pour les mettre en vidence Le dernier reste non nul est 3 donc le PGCD de 183 et 117 est gal 3 Exercice 2 9 V rifier par l algorithme d Euclide que le PGCD de 364 et de 154 est gal 14 Exercice 2 10 Combien 10100 et 10121 10815 10 ont ils de diviseurs communs On peut g n raliser la notion de PGC D plusieurs entiers On a par exemple PGC D a b c PGCD PGCD a b c PGCD a PGCD b c En effet d aetd b etdilce d PGCD a bjetd c lt gt d PGCD PGCD a b c et de m me d a et d b et d c 4 gt d PGCD a PGC D b c On d finit galement le PGCD de deux ou plusieurs entiers relatifs par PGC D a b PGCD al b Proposition 2 8 Si a bq r alors PGC D a b PGC D b r D monstration Evident d apr s la Proposition 5 Exercice 2 11 D terminer le PGCD de 1000000000 et 1000000005 L une des notions les plus importantes en arithm tique est celle de nombre premier D finition 2 9 Un entier p est dit premie
13. haut Les exercices marqu s avec le symbole peuvent demander une petite id e non vidente ou un peu de calcul Les exercices marqu s avec 4 n cessitent un temps de r flexion un peu plus long 2 Divisibilit D finition 2 1 Soient a b deux entiers relatifs On dit que a divise b ou que b est divisible par a ou que b est un multiple de a s il existe un entier c tel que b ac On note a b Par exemple 2 6 247 1 n n n n 0 pour tout entier n Proposition 2 2 Soient a b b c des entiers i Transitivit Si a b et b c alors a c ii Si a b alors a bc iii Si a b et a b alors a b v iv Sia b et a b alors a b A vi Sia b et b 0 alors a lt b v Si 0 alors a b si et seulement si Aa Ab vii Sia b et b a alors b a ou b a D monstration i Par d finition il existe u et v tels que b au et c bv On a alors c au v a uv donc a c ii Il est clair que b bc D apr s i on en d duit que a bc ii Il existe u et v tels que b au et b av On a alors b b au av a u v donc a b b iv D apr s ii on a a Ab et d apr s iii on en d duit que a b Ab v Si a b alors il existe u tel que b au Ceci entra ne Ab Aa u donc Aa Ab R ciproquement si Aa Ab alors il existe v tel que b Aau Comme 0 on peut diviser par ce qui donn
14. or me On essaye 7x 1 7 7 x2 14 7 x 3 21 7 x 4 28 d passe la valeur a Donc le quotient q est gal 3 Pour calculer le reste on effectue la soustraction 25 7 x 3 Remarque 2 4 Si b est un entier relatif non nul quelconque il existe encore un et un seul couple q r d entiers tel que a bq r et 0 lt r lt b 1 Le cas b gt 1 ayant d j t trait supposons b lt 1 L unicit se montre de la m me fa on Pour l existence on effectue la division Euclidienne de a par b ce qui permet d crire a b q r On pose alors q q et on a a bq r Par exemple la division Euclidienne de 17 par 5 s crit 17 5 x 4 3 Proposition 2 5 Soient a b d q r des entiers On suppose que a bq r Alors d divise a et b si et seulement si d divise b et r D monstration Si d divise a et b alors d divise a bq d apr s la Proposition 2 iv donc d divise b et r De m me si d divise b et r alors d divise bq r a Soient maintenant a gt b gt 0 L algorithme Euclide consiste effectuer des divisions Euclidiennes successives on pose ap a et ay b puis pour tout k gt 0 on effectue la division Euclidienne de az par ax 1 et on appelle ax 2 le reste ao aq az Gi 2Q2 a3 a2 433 4 An 2 An 1Qn 1 An An 1 Ann An 1 jusqu tomber sur un reste nul a 1 0 Le processus s arr te bien car les r
15. qui peuvent s crire sous la forme avec a Z et b E N R l ensemble des nombres r els Q d signe l ensemble des rationnels non nuls Q l ensemble des rationnels strictement positifs et Q l ensemble des rationnels strictement n gatifs On introduit de m me les notations Z_ Z R R R Si a et b sont deux nombres alors ab d signe le produit a x b 1 2 Principe de r currence Dans ce document nous utiliserons fr quemment le principe de r currence suivant Soit P n une propri t d un entier n On suppose que i initialisation P 0 est vraie ii h r dit pour tout entier naturel n si P n est vraie alors P n 1 est vraie P 0 P 1 P 2 P 3 P po pe poe po Alors P n est vraie pour tout n Vocabulaire lorsque l on essaye de d montrer l implication P n P n 1 la propri t P n que l on suppose vraie s appelle l hypoth se de r currence Une variante de ce principe est la r currence forte supposons que i initialisation P 0 est vraie ii h r dit pour tout entier naturel n si P k est vraie pour tout k lt n alors P n 1 est vraie Alors P n est vraie pour tout n 1 3 Mode d emploi des exercices Trois niveaux de difficult s sans doute subjectifs sont indiqu s pour les exercices Les exercices non marqu s sont des tests de compr hension imm diate ou bien demandent simplement d appliquer une m thode indiqu e quelques lignes plus
16. v a vp b Exercice 2 23 Montrer que si a b alors a b 15 Exercice 2 24 Montrer que si p est premier et p a alors p a Exercice 2 25 Montrer que ab PGC D a b x PPCM a b Exercice 2 26 D terminer tous les couples d entiers naturels x y v rifiant PGCD x y 8 PPCM x y 440 x y 128 Exercice 2 27 Un nombre est dit parfait si la somme de tous ses diviseurs positifs est gale 2n Montrer que si 2k 1 2 1 est un nombre premier alors IRIEL 1 est parfait Montrer que tout nombre parfait pair est de cette forme 2 3 Nombre de diviseurs d un entier Th or me 2 26 Soit n gt 1 un entier dont la d composition en facteurs premiers s crit n pf p amp r Alors n admet a 1 a 1 diviseurs positifs b s Br 1 D monstration Les diviseurs de n s crivent sous la forme p pr avec 0 lt Bi lt Q1 O lt br lt ar Pour Bi on a a1 1 choix possibles pour B2 on a amp z 1 choix etc ce qui donne en tout i 1 ar 1 choix possibles Par exemple les diviseurs positifs de 100 2 x 5 sont 20 x 50 20 x 51 20 x 52 21 x 50 21 x 51 21 x 52 22 x 50 22 x 51 22 x 52 Notons T n le nombre de diviseurs positifs de n Exercice 2 28 Combien vaut 7 1000000 16 Exercice 2 29
17. Concepts de base en arithm tique Jean Louis Tu Objectifs de ce document Ce document s adresse tout l ve de fin de coll ge ou d but de lyc e souhaitant 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 comp tition pour les juniors Sa lecture est indispensable tout l ve d butant en arithm tique et souhaitant participer aux activit s de OFM envois d exercices par correspondance stages Les exercices de ce document sont pour l essentiel des exercices d apprentissage et permettent d acqu rir certains r flexes mais sont rarement des exercices de comp tition Par cons quent pour tre performant en situation de concours l l ve devra les compl ter par d autres par exemple ceux provenant de polycopi s de stages olympiques Une fois que l l ve aura acquis de l aisance avec les concepts de base pour se hisser au niveau des comp titions de type Olympiades Internationales il devra largir ses connaissances avec des notions plus avanc es ordre multiplicatif fonctions arithm tiques r ciprocit quadratique entiers de Gauss 1 Pr liminaires 1 1 Notations On note N 0 1 2 3 l ensemble des entiers naturels N l ensemble des entiers naturels non nuls Z 3 2 1 0 1 2 3 l ensemble des entiers relatifs Q l ensemble des nombres rationnels c est dire
18. Il suffit d appliquer k fois la Proposition 3 ii Exercice 3 1 Quels sont les entiers p tels que p et p 1 sont premiers Exercice 3 2 Quels sont les entiers p tels que p p 2 et p 4 sont premiers 3 2 Crit res de divisibilit Soit n un entier On note ag ag son criture d cimale Par exemple si n 147 alors k 2 ao 7 ai 4 a2 1 On a donc 0 lt a lt 9 pour tout j et n ao 10a1 10705 10ue Proposition 3 5 n est congru ao ax modulo 9 et modulo 3 Par cons quent n est divisible par 9 respectivement 3 si et seulement si ao ax l est D monstration On a 10 1 9 donc 10 1 9 D apr s la Proposition 4 on a 107 1 9 pour tout j donc n ao 10a 10242 10a ag ag 9 A fortiori n est congru ao ax modulo 3 Enfin n est divisible par 9 resp 3 si et seulement si n est congru 0 modulo 9 resp 3 si et seulement si ao ax est congru 0 modulo 9 resp 3 Exercice 3 3 48767621 est il divisible par 9 19 Proposition 3 6 n est congru ao a1 a2 a3 modulo 11 En particulier n est divisible par 11 si et seulement si la somme altern e de ses chiffres est divisible par 11 D monstration On a 10 1 11 donc 10 1 11 On en d duit que ao 10a 410 as 10 04 ee a0 Q1 a2
19. a v b pour tout p premier D monstration i Soient p1 p les nombres premiers qui divisent a ou b On crit b a pi p et b p pf avec qi gt 0 et B gt 0 pour tout i 1 2 r Alors ab pta per tr d o Vp ab Bi Vp a vp b pour tout i ii Si a b alors il existe c tel que b ac d o v b vpa vp c gt vpla R ciproquement si vp a lt v b pour tout entier premier p alors on peut crire a p p r et b pi ph on a b ac donc a b P avec a i lt pi Posons y bi a et c p p Alors iii Avec les notations pr c dentes posons 0 min a B et d i p r D apr s P P Pi Pr P i onadl aet d b D autre part pour tout d gt 1 on a d a et d b si et seulement Part p si Up d lt vp a et vp d lt vp b pour tout p premier Ceci quivaut vp d lt vp d pour tout p premier ou encore d d Ceci prouve que d a A b Exercice 2 22 Montrer sans calcul que 87457561565 ne divise pas 100000000000000000000000007 De la m me fa on que ci dessus on montrerait Proposition 2 25 Soient a b gt 1 des entiers Il existe un et un seul nombre appel le plus petit commun multiple de a et b et not PPCM a b ou aVb caract ris par la propri t suivante Soit m un entier non nul Alors a m et b m si et seulement si PPCM a b m De plus v a V b max
20. an La d monstration n est pas difficile mais nous l omettons pour que ce document garde une longueur raisonnable 11 Voici un corollaire important du th or me de B zout Th or me 2 19 Lemme de Gauss Soient a et b des entiers Soit m un nombre qui est premier avec a tel que m ab Alors m b D monstration Soient a b m comme dans l nonc Il existe u et v tels que mu av 1 On multiplie membre membre par b ce qui donne mu ab u b Comme m divise mu et ab v il divise le membre de gauche donc m b Exercice 2 16 Montrer que si x et y sont des entiers tels que 2x 1 divise 8y alors 2x 1 divise y Dans le cas particulier o m est un nombre premier on obtient le r sultat suivant Th or me 2 20 Soit p un nombre premier et a b des entiers Si p ab alors p a ou p b D monstration Soit p un nombre entier et a b des entiers tels que p ab Si p ne divise pas a alors p est premier avec a donc p b d apr s le lemme de Gauss Remarque 2 21 L hypoth se que p est premier est indispensable ici Par exemple 6 divise 10 x 21 mais 6 ne divise ni 10 ni 21 Plus g n ralement Th or me 2 22 Soit p un nombre premier Si p divise le produit a a alors p divise l un des nombres amp 1 2 y D monstration On le d montre par r currence sur r Si r 1 c est vident Sup
21. b est inversible modulo p L id e est assez naturelle si on peut diviser par a et par b alors on peut diviser par ab en divisant d abord par a puis par b D monstration Il existe a et b tels que aa 1 p et bb 1 p On en d duit ab a b aa bb 1 x 1 1 p donc ab est inversible modulo p et son inverse est a b Proposition 3 13 Soit p un nombre premier et a un entier non divisible par p Alors a est gal son inverse modulo p si et seulement si a 1 p ou a 1 p D monstration a est gal son inverse modulo p a 1 p a 1 0 p a 1 a 1 0 p pl a 1 a 1 p a 1 ou p a 1 d apr s le Lemme de Gauss a 1 0 p oua 1 0 fp a 1 p ou a 1 p 1111111 Th or me 3 14 Wilson Si p est premier alors p 1 1 p D monstration Rappelons que p 1 1x2x3x x p 1 Si p 2 on a p 1 1 1 2 Supposons p gt 3 Notons que p 1 1 p Les nombres 2 3 p 2 ne sont congrus ni 1 ni 1 modulo p Dans le produit 2x3x xp 2 on regroupe chaque terme avec son inverse modulo p On obtient ainsi 2x3x x p 2 1 p Ainsi 2x 3x x p 2 x p 1 p 1 1 p ce qui s crit p 1 1 p 22 3 4 Petit th or me de Fermat Th or me 3 15 Soit p un nombre premier Alors pour tout entier a non divisible par p on a
22. b sont premiers entre eux v a et v b ne peuvent pas tre tous deux non nuls Si vp a 0 alors m divise videmment vp a Si vp b 0 alors v ab vp a vp b vpla donc m divise vp a Dans tous les cas m divise vp a pour tout p donc pour tout j il existe yj tel que Qj MYj Soit y p p On a a y On proc de de m me pour b Proposition 4 2 Soient a et b deux entiers naturels On suppose qu il existe un nombre premier p et un entier m tel que ab p Alors a et b sont des puissances de p D monstration Un nombre premier divisant a doit diviser ab p donc doit tre gal p Ainsi p est le seul nombre premier divisant a Par cons quent a est une puissance de p 4 1 Identit s remarquables Voici quelques identit s remarquables m moriser et qui sont fr quemment utiles dans des probl mes d arithm tique a b a 2ab b a b a 2ab b b a 3a b 3ab b a ab a 3a b 3ab b a b a b a b a b a b a ab b a b a bite ap ab a b a a b a 3b bt a b a b a t a b at Sp b si n impair 27 Les six premi res galit s se v rifient en d veloppant Montrons la septi me a b a7 a b a 3b DRE cor leg pa bT bat at bb H bT a hat ba 2024 ab 1 ap at 267 La Sp
23. c est solution alors pour tout entier d da db dc est une solution Par exemple 6 8 10 est encore un triplet Pythagoricien Ceci conduit poser la d finition suivante D finition 4 3 Une solution primitive est une solution telle que a b c sont premiers entre eux dans leur ensemble Si a b c est une solution quelconque posons d PGC D a b c On peut crire a da b db c dd pour certains entiers a b c En divisant l quation a b par d il vient a b c De plus a b c sont premiers entre eux dans leur ensemble donc a b c est une solution primitive Par cons quent le probl me revient chercher toutes les solutions primitives de l quation Remarquons galement que a et b sont premiers entre eux car s il y avait un nombre premier p divisant a et b alors p diviserait a b donc p diviserait c ce qui entra nerait que p divise c et a b c ne seraient pas premiers entre eux De m me a et c ainsi que b et c sont premiers entre eux Autrement dit a b c sont premiers entre eux deux deux 29 Ainsi a et b ne peuvent pas tre tous les deux pairs Ils ne peuvent pas non plus tre tous deux impairs sinon a b 1 1 2 4 et on a vu que 2 n est pas un carr modulo 4 Quitte changer a et b on peut supposer que a est impair et que b est pair On 2 _ 2e E Se Comme a et c sont impairs 55 et ce sont bien des entiers Si un no
24. de tester si un entier est divisible par un autre Th or me 2 3 Soient a et b deux entiers tels que b gt 1 Alors il existe un et un seul couple q r d entiers tel que e a bq r e 0 lt r lt b 1 Les entiers q et r s appellent respectivement le quotient et le reste de la division Euclidienne de a par b D monstration Montrons d abord l unicit Si a bg r bg r avec 0 lt r lt b 1 et 0 lt 7 lt b 1 alors bq bg r r donc b q g r r lt b En divisant par b on en d duit q q lt 1 donc q g I vient r r bq bq 0 puis r r Montrons l existence Traitons d abord le cas a gt 0 Remarquons d abord que e il existe des entiers x tels que bx lt a par exemple x 0 e six gt a alors bz gt a puisque bz gt ba Il existe donc un plus grand entier q tel que bq lt a Par d finition de q on a b q 1 gt a c est dire bq b gt a Posons r a bq on a alors 0 lt r lt b ce qui prouve l existence dans le cas a gt 0 Si maintenant a lt 0 on remarque que a ba b 1 a gt 0 On applique la division Euclidienne de a ba par b il existe g et r tels que a ba bg r et 0 lt r lt b On a alors a b a g r bg r avec q a d Exemple pour a 25 et b 7 le quotient est 3 et le reste est 4 Pour d terminer ces valeurs on a en fait proc d exactement comme dans la preuve du th
25. e b au autrement dit a b vi Soit u tel que b au Comme b 0 on a u 0 donc 1 lt u En multipliant membre membre par a on obtient a lt au b vii On suppose que a b et b a Si a 0 alors le fait que a b entra ne b 0 donc on a bien b a ou b a De m me si b 0 alors b a ou b a Si a 0 et b 0 alors d apr s vi on a a lt b et b lt Ja donc a b ce qui donne bien b a ou b a Exercice 2 1 Montrer que si a b et c d alors ac bd Exercice 2 2 Quels sont les entiers n tels que n n 77 Exercice 2 3 Quels sont les entiers n tels que n 1 n Exercice 2 4 Montrer que pour tout entier n l entier n n 1 est pair Exercice 2 5 Montrer que pour tout entier n l entier n n 1 n 2 est divisible par 6 Exercice 2 6 Soient a b c des entiers Montrer que si n est un entier v rifiant an bn c 0 alors n c Exercice 2 7 D terminer les entiers n tels que n 2n Exercice 2 8 Soient a gt 1 et n des entiers tels que a n 2 et a n n 5 Montrer que a 1 ou amp 7 D monstration On a a n n 2 n 2n donc a n n 5 n 2n n 5 On en d duit que a n 2 n 5 7 puis que a 1 ou a 7 La division Euclidienne permet
26. ers n tels que n et n 2 sont premiers entre eux 2 Quels sont les entiers n tels que n 1 et n 2n 1 sont premiers entre eux Plus g n ralement D finition 2 15 Des entiers a1 a2 an sont dits premiers entre eur dans leur ensemble si l unique entier strictement positif les divisant tous est 1 Autrement dit PGCD a 1 a oag Km S Par exemple 6 10 15 sont premiers entre eux dans leur ensemble mais ne sont pas premiers entre eux deux deux Proposition 2 16 Soient a et b deux entiers non nuls et d leur PGCD Alors on peut crire a da et b db avec a et b premiers entre eux Par exemple pour a 15 et b 21 on crit 15 3 x 5 et 21 3 x 7 les entiers 5 et 7 sont bien premiers entre eux D monstration Comme d divise a et b les nombres a et b sont entiers Si un d d entier naturel c divise a et b alors cd divise da a et db b donc cd divise d ce qui entra ne c 1 puis c 1 Par cons quent a et b n ont pas d autre diviseur commun que 1 autrement dit a et b sont premiers entre eux 2 1 Le th or me de B zout Th or me 2 17 B zout i Soient a et b deux entiers Notons d a A b Alors il existe des entiers relatifs u et v tels que d au bv ii Plus pr cis ment pour tout entier m il existe u et v tels que au bu m si et seulement si m est un multiple de d iii En pa
27. estes sont de plus en plus petits a1 gt a2 gt a3 gt On note n l indice tel que a est le dernier reste non nul D finition 2 6 Soient a et b deux entiers Un entier d gt 0 est appel PGCD plus grand commun diviseur de a et b s il v rifie la propri t suivante pour tout d entier d divise a et b si et seulement si d divise d Par exemple pour a 15 et b 21 l entier d 3 est le PGCD de a et b En effet les diviseurs positifs communs de 15 et 21 sont 1 et 3 et un entier naturel divise 3 si et seulement s il est gal 1 ou 3 Remarquons que le PGCD divise a et b il suffit de prendre d d dans la caract risation du PGCD puisque d divise d il divise a et b De plus le PGCD est unique car si d et d v rifient la propri t du PGCD alors d d2 et d d1 ce qui entra ne d d2 Le th or me suivant montre l existence du PGCD Th or me 2 7 Si a et b sont non nuls alors dans l algorithme d Euclide a est le PGCD de a et b Si b 0 alors a est le PGCD de a et b D monstration Premier cas a et b sont non nuls D apr s la proposition pr c dente on a d aetd b d a etd a lt 4 d a ctd a 4 d an et d anr1 lt d an cette derni re quivalence d coule du fait que an 0 et que d 0 est vrai pour tout d Deuxi me cas b 0 Alors d a et d b si et seulement si d a donc a est le PGCD
28. lors 1 1 p donc p 2 ce qui est impossible Donc m est pair On l crit sous la forme m 2k On en d duit que p 4k 1 est bien congru 1 modulo 4 Remarque 3 19 La r ciproque est vraie mais un peu plus difficile d montrer si p 1 4 alors 1 est un carr modulo p 3 6 Nombres rationnels et irrationnels d veloppement d cimal Un nombre est dit d cimal s il a un nombre fini de chiffres apr s la virgule Tout entier est un nombre d cimal Le nombre 3 8 0 375 est d cimal Un nombre est dit rationnel s il est le quotient de deux entiers Par exemple 83 70 1 1857142857142857142 est rationnel On constate que son d veloppement d cimal est p riodique le motif 857142 se r p te Ceci s explique par le fait que lorsque l on pose la division il n y a qu un 25 nombre fini de restes possibles Le motif commence se r p ter lorsque l on tombe sur un reste d j obtenu pr c demment R ciproquement un nombre dont le d veloppement d cimal est p riodique est rationnel Sans le prouver formellement expliquons le sur un cas particulier Soit x 3 1212121212 On a 100x 312 12121212 donc 99x 100x x 309 Il vient x 300 Cette fraction n est pas irr ductible elle se simplifie en 13 Exercice 3 17 Ecrire le nombre 3 157157157157 sous forme d une fraction irr ductible Certains nombres n ont pas de d vel
29. lors b a n transitivit si a b n et b c n alors a c n D monstration a a 0 est divisible par n d o la r flexivit Si n divise a b alors n divise a b b a d o la sym trie Si n divise a b et n divise b c alors n divise a b b c donc n divise a c Ceci prouve la transitivit La congruence est compatible avec l addition et la multiplication Proposition 3 3 Soient a b c d des entiers et n un entier non nul Supposons a bjn et c dfn Alors i a c b dfnl ii ac bd n D monstration Par hypoth se n divise a b et c d i n divise a b c d a c b d donc a c b dfn ii ac bd a c d d bd a c d ad bd a c d a b d est divisible par n puisque c d et a b le sont donc ac bd n On raisonne couramment modulo 12 dans la vie de tous les jours S il est 9 heures du matin alors dans 5 heures il sera 2 heures de l apr s midi ceci correspond au fait que 9 5 2 12 18 Le fait de raisonner modulo 10 est aussi tr s intuitif car il correspond regarder le dernier chiffre d un entier Par exemple 857382993 est congru 3 modulo 10 car 857382993 3 857382990 est un multiple de 10 Proposition 3 4 Si a b n alors pour tout entier k gt 1 on a af b n D monstration
30. mbre p divise la fois 55 et dire que p divise c et a Or a et c sont premiers entre eux donc p 1 Par cons quent c a c a et sont premiers entre eux Or leur produit est un carr donc d apr s la Proposition 1 ce sont tous deux des carr s Ainsi il existe u et v tels que c a 2 Le de 2 FH il divise leur somme et leur diff rence c est e e En faisant la somme des deux galit s on obtient c u w En faisant la diff rence on trouve a u v et en faisant le produit on voit que B u 2v donc b 2uv Conclusion quitte changer a et b les solutions primitives sont donn es par les formules a u v b 2uv c u pour certains entiers u et v On v rifie qu on a bien u v Rw u v 4 4 Exercices suppl mentaires Exercice 4 3 R soudre dans les entiers naturels x y 24 Exercice 4 4 Trouver les entiers a b n et p tels que p est premier a gt b 2 et a b p Exercice 4 5 Trouver tous les nombres premiers tels qu il existe des entiers x et y v rifiant P q y z y p ylz p 5p 30 Exercice 4 6 D terminer les entiers naturels m et n tels que 2 37 1 M me chose pour l quation 37 27 1 Exercice 4 7 D terminer tous les entiers a b c gt 0 tels 2230 9 31
31. ner tous les couples d entiers x y v rifiant l quation 16r 26y n 2 2 Le th or me fondamental de l arithm tique Th or me 2 23 Tout entier gt 2 admet une d composition en produit de nombres premiers Cette d composition est unique l ordre pr s Par exemple 84 2 x 2 x 3 x 7 est une d composition de 84 en facteurs premiers Les autres d compositions s obtiennent en permutant les termes comme 84 3 x 2 x 7 x 2 13 D monstration Soit P n la propri t n admet une et une seule d composition en produit de nombres premiers Nous allons montrer par r currence que P n est vraie pour tout n gt 2 La propri t P 2 est vraie si n p1 p est produit de nombres premiers alors r puisque n est premier et par suite p 2 Soit n gt 3 et supposons P 2 P 3 P n 1 vraies Montrons que P n est vraie Il faut d abord prouver l existence d une d composition de n en produit de nombres premiers Soit p le plus petit diviseur de n On sait que p est premier Si n p alors n est bien produit de nombres premiers Si p lt n alors comme 2 lt 7 lt n par hypoth se de r currence il existe des nombres premiers P1 p tels que p p Pr Par cons quent n pp1 p admet bien une d composition en facteurs premiers Montrons maintenant l unicit de la d composition Supposons que n D1P2 Pr q102 ds avec p1 pPr et q1 qr premiers
32. ont premiers En revanche Fs 641 x 6700417 est compos Actuellement on ne conna t pas d autre nombre premier de Fermat 28 4 2 L quation a b n A n fix on consid re l quation a b n d inconnues a b N Rappelons que a b a b a b Comme a b a b 2b les entiers a b et a b ont la m me parit S ils sont tous deux impairs alors n est impair et s ils sont tous deux pairs alors n est divisible par 4 Par cons quent l quation ne peut avoir de solution que si n est impair ou si n est divisible par 4 Supposons que n a b a b Alors a b est un diviseur de n Notons le d On a alors a b d et a b donc a a 3 et a z a a Il y a donc autant de solutions que d entiers naturels d tels que d et sont des diviseurs de n de m me parit Ecrivons n 2 m avec m impair Si r 0 alors n importe quel diviseur de n convient et si r gt 2 alors d est de la forme 2d avec 1 lt j lt r 1 et d m Par exemple pour n 2016 25 x 3 x 7 d est de la forme 2 d avec 1 lt j lt 4 et d 1 3 9 7 21 63 ce qui donne 24 solutions en tout 4 3 L quation a b c Les solutions de cette quation s appellent les triplets Pythagoriciens car elles correspondent aux triangles rectangles dont les c t s sont entiers Le plus connu d entre eux est 3 4 5 puisque 32 4 5 On remarque tout d abord que si a b
33. oppement d cimal p riodique Proposition 3 20 V2 est irrationnel D monstration Supposons par l absurde que V2 5 avec irr ductible On a 2 A donc a 2b On regarde la 2 valuation 2u2 a va a v2 2b 1 2v2 b Or 2v2 a est pair et 1 2v2 b est impair Contradiction Plus g n ralement Exercice 3 18 Soit n gt 2 Montrer que si a est un entier positif qui n est pas la puissance n i me d un entier alors la racine n i me de a not e a est un irrationnel N B a est l unique nombre r el positif tel que a a Exercice 3 19 Montrer que 4 2 3 est irrationnel Exercice 3 20 Montrer que V2 v3 est irrationnel On peut montrer que 7 est irrationnel mais les outils n cessaires pour le d montrer d passent le cadre de ce document 26 4 Utilisation de factorisations Le fait d crire un entier n sous la forme n ab avec a gt 2 et b gt 2 permet d une part de voir que n n est pas premier et d autre part d utiliser les deux propositions suivantes Proposition 4 1 Soient a et b deux entiers naturels premiers entre eux et x m deux entiers naturels Si ab x alors il existe des entiers y et z tels que a y et b 2 D monstration Ecrivons a pf p Pour tout nombre premier p on a vplab vp x mvp x donc v ab est un multiple de m Comme a et
34. posons la propri t vraie au rang r 1 Sip a1 a alors d apr s le lemme de Gauss p divise a ou p divise av ap Or par hypoth se de r currence p a2 a entra ne que p divise l un des nombres a2 ar Il vient que p divise l un des nombres a1 r 12 Soient a et b deux entiers premiers entre eux Revenons l quation au bu 1 d inconnues u et v L algorithme d Euclide tendu permet d en trouver un couple de solutions Notons ugo vo cette solution particuli re on a donc aug bvo 1 Cherchons maintenant toutes les solutions Soit u v un couple d entiers tels que au bu 1 On a au bv auo bvo a u uo b vo v 1 Or a divise a u uo donc a divise b vo v Comme de plus a est premier avec b il divise vo v d apr s le Lemme de Gauss Soit k Z tel que vo v ak On reporte dans 1 a u uo bak ce qui donne u uo bk et finalement u uo bk v vo ak R ciproquement si u uo bk et v vo ak on v rifie que u v est une solution au bu a uo bk b vo ak auo bvo abk abk auo bvo 1 Conclusion u v v rifie l quation au bv 1 si et seulement s il existe k Z tel que u uo bk et v vo ak Exercice 2 17 D terminer toutes les solutions de l quation 9u 7u 1 Exercice 2 18 Soit n un entier fix D termi
35. r si p 2 et si les seuls diviseurs positifs de p sont 1 et p La liste des nombres premiers commence par 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 A noter que 1 n est pas premier La raison de cette convention est que l on veut que tout entier gt 2 admette une d composition unique en facteurs premiers voir plus loin Exercice 2 12 131 est il premier 221 est il premier Remarque 2 10 Si p est premier alors pour tous entiers naturels a et b l galit p ab entra ne a 1 et b p ou a p et b 1 D monstration p ab entra ne que a est un diviseur de p donc a 1 ou a p Si a 1 alors p ab 1 x b b et si a p alors p pb donc b 1 Proposition 2 11 Soit n gt 2 un entier Le plus petit diviseur gt 2 de n est un nombre premier Exemple pour n 75 les diviseurs gt 2 de n sont 3 5 15 25 75 Le plus petit de ces nombres est gal 3 qui est bien premier D monstration Notons p le plus petit entier tel que i p n ii p gt 2 Notons que p est bien d fini puisqu il existe des entiers par exemple n v rifiant les deux conditions i et ii Soit d est un diviseur gt 2 de p Comme d p et p n on a d n De plus p tant le plus petit diviseur gt 2 de n on a p lt d Or d lt p puisque d divise p donc d p Ceci prouve que l unique diviseur gt 2 de p est p lui m me donc p est premier
36. rticulier a et b sont premiers entre eux si et seulement s il existe u et v tels que au bu 1 Avant de d montrer ce th or me commen ons par un exemple reprenons le calcul de PGCD 183 117 183 117 1Xx1 1 66 117 66 x1 51 66 51 x1 15 5l 15 x 3 6 15 6 x2 3 6 3 x2 0 On va crire les restes successifs en fonction de 183 et 117 66 1183 117 51 117 66 117 183 117 117 x 2 183 15 66 51 183 117 117 x 2 183 183 x 2 117 x 3 6 51 15 x 3 117 x 2 183 183 x 2 117 x 3 x 3 183 x 7 117 x 11 10 3 15 6 x 2 183 x 2 117 x 3 1183 x 7 1117 x 11 x 2 183 x 16 117 x 25 On a ainsi trouv que 3 183u 117v avec u 16 et v 25 Exercice 2 15 Trouver des entiers relatifs u et v tels que 364u 154v 14 D monstration du th or me Montrons i Il suffit d expliquer formellement l algorithme utilis plus haut
Download Pdf Manuals
Related Search