Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él` eves pré- Z ensemble des entiers relatifs Q ensemble des nombres rationnels R Une récurrence directe permettra ensuite de l'avoir dans toute sa généralité
Previous PDF | Next PDF |
[PDF] Algèbre 1 Généralités et Arithmétique dans Z Table des - Unblogfr
Généralités et Arithmétique dans Z Table des matières Z, l'ensemble des entiers relatifs, Z = { , −2, −1, 0, 1, 2, } (voir cours d'Analyse) Ce n'est pas le
[PDF] Arithmétique dans Z - Maths-francefr
1 Divisibilité dans Z 1 1 Définitions Définition 1 1) Soient a et b deux entiers relatifs tels que a = 0 On dit que a divise b ou que a est un diviseur de b si et
[PDF] Cours darithmétique
mais il est fortement recommandé de lire ce chapitre avant d'aborder le cours Les chapitres ou 2 2 Généralités sur les groupes finis 6 Arithmétique Il existe des variantes de démonstrations par récurrence, par exemple : Variante 1 Pour
[PDF] Résumé du cours darithmétique
Dans ce qui suit, entier est synonyme d'entier relatif 1 Divisibilité dans Z a) Diviseurs et multiples Définition Soit a et b deux entiers
[PDF] Cours darithmétique
Ce document est la premi`ere partie d'un cours d'arithmétique écrit pour les él` eves pré- Z ensemble des entiers relatifs Q ensemble des nombres rationnels R Une récurrence directe permettra ensuite de l'avoir dans toute sa généralité
[PDF] Chapitre 4 :Arithmétique dans Z - Melusine
Mais, afin de conserver la généralité des énoncés, nous n'allons pas, pour le cours, nous limiter aux entiers positifs A) PGCD et algorithme d'Euclide Etant
[PDF] Algèbre et arithmétique pour Master-1
Ce livre est écrit à partir d'un cours dans le cadre de la première année du Master Il existe une analogie profonde entre l'ensemble Z des nombres entiers et l'ensemble Nous donnons ici les premières généralités sur ces anneaux qui
[PDF] ALGÈBRE ET ARITHMÉTIQUE 1 - Université de Rennes 1
définitions qui seront données au fil de ce cours) et des propriétés qui découlent de ces concepts, énoncées 6 CHAPITRE 1 LOGIQUE ET THÉORIE DES ENSEMBLES de l'addition, qui sera démontrée ci-dessous en toute généralité
[PDF] Cours arithmétique et groupes Licence première année, premier
Cours arithmétique et groupes z = x ou z = y ; on le notera x−1 (on montrera en exercice qu'un prédécesseur On peut supposer sans perte de généralité
[PDF] Arithmétique - Maths au lycée
Soit a et b deux entiers relatifs tels que : b 0 Il existe un entier relatif n tel que : nb a On dit que Z est archimédien Démonstration 1er cas
[PDF] generally
[PDF] generate code for aiims 2019
[PDF] generation of alternating current
[PDF] generation of code for final registration aiims
[PDF] generation of computer 1st to 5th
[PDF] generation of computer notes
[PDF] generation of computer notes pdf
[PDF] generation of computer ppt
[PDF] generation of computer wikipedia
[PDF] generation of programming languages
[PDF] generations of programming languages pdf
[PDF] generic abn form pdf
[PDF] generic type java
[PDF] generics collection
Cours d"arithm´etique
Premi`ere partie
PierreBornsztein
XavierCaruso
PierreNolin
MehdiTibouchi
D´ecembre 2004
Ce document est la premi`ere partie d"un cours d"arithm´etique ´ecrit pour les ´el`eves pr´e-
parant les olympiades internationales de math´ematiques. Le plan complet de ce cours est :1. Premiers concepts
2. Division euclidienne et cons´equences
3. Congruences
4.´Equations diophantiennes
5. Structure deZ/nZ
6. Sommes de carr´es
7. Polynˆomes `a coefficients entiers
8. Fractions continues
Cette premi`ere partie traite les quatre premiers chapitres. Les quatre derniers chapitres forment quant `a eux la deuxi`eme partie de ce cours. Contrairement `a la seconde partie, cette premi`ere partie se veut le plus ´el´ementairepossible. Les notions abstraites, souvent plus difficiles `a assimiler, mais qui clarifient les id´ees
lorsqu"elles sont comprises, ne sont ´evoqu´ees que dans la seconde partie. Nous conseillons au lecteur de bien maˆıtriser ce premier tome avant de passer `a la lecture du second.Les notions et les th´eor`emes introduits ici sont g´en´eralement tout `a fait suffisants pour
traiter les exercices propos´ees aux olympiades internationales de math´ematiques.Vous trouverez `a la fin de chaque chapitre une s´erie d"exercices de difficult´e variable mais
indiqu´ee par des ´etoiles1. Toutes les solutions sont rassembl´ees `a la fin du document.
Nous vous souhaitons bon apprentissage et bonne lecture. 1 Plus nous avons jug´e l"exercice difficile, plus le nombre d"´etoiles est important. 1Liste des abbr´evations :
AMM American Mathematical Monthly
APMO The Asian Pacific Mathematics Olympiad
CG Concours g´en´eral
OIM Olympiades Internationales de Math´ematiquesSL Short List
TDV Tournoi Des Villes
Liste des notations :
?ensemble videNensemble des entiers naturels (positifs ou nuls)
N ?ensemble des entiers naturels strictement positifsZensemble des entiers relatifs
Qensemble des nombres rationnels
Rensemble des nombres r´eelsPsymbˆole de sommation2Qsymbˆole de produit3 a|b adiviseb [x]partie enti`ere dex {x}partie d´ecimale dex pgcdplus grand commun diviseur a?bpgcd(a,b) ppcmplus petit commun multiple a?bppcm(a,b) a≡b(modN)aest congru `abmoduloN pun nombre premier v p(n)valuationp-adique den d(n)nombre de diviseurs positifs denσ(n)somme des diviseurs positifs den
?fonction indicatrice d"Euler s b(n)somme des chiffres denen baseb π(n)nombre de nombres premiers inf´erieurs ou ´egaux `an a n...a0b´ecriture en baseb n!factorielle den:n! = 1×2× ··· ×n C k ncoefficient binomial : Ck n=n! k!(n-k)! u n≂vnles suites(un)et(vn)sont ´equivalentes 2 Une somme index´ee par l"ensemble vide est ´egale `a0.3Un produit index´e par l"ensemble vide est ´egale `a1.
2Table des mati`eres
1 Premiers concepts 4
1.1 Divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Valuationp-adique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Quelques fonctions arithm´etiques . . . . . . . . . . . . . . . . . . . . . . . . 14
1.5 Nombres rationnels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Division euclidienne et cons´equences 24
2.1 Division euclidienne et d´ecomposition en baseb. . . . . . . . . . . . . . . . 24
2.2 Algorithme d"Euclide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Algorithme d"Euclide ´etendu et th´eor`eme de B´ezout . . . . . . . . . . . . . . 28
2.4 Lemme de Gauss et cons´equences . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Congruences 37
3.1 D´efinition, premi`eres propri´et´es . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Crit`eres de divisibilit´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Ordre d"un ´el´ement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4 Th´eor`eme chinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Congruences modulop. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Congruences modulopn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.7 Coefficients binomiaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.8 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4´Equations diophantiennes 56
4.1 Quelques r´eflexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Utilisation des congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3 Descente infinie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.4´Equations de degr´e2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5´Equations de degr´e3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.6 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5 Corrig´e des exercices 75
5.1 Exercices de"Premiers concepts». . . . . . . . . . . . . . . . . . . . . . . 75
5.2 Exercices de"Division euclidienne et cons´equences». . . . . . . . . . . . . 103
5.3 Exercices de"Congruences». . . . . . . . . . . . . . . . . . . . . . . . . . 118
5.4 Exercices de"´Equations diophantiennes». . . . . . . . . . . . . . . . . . . 143
31 Premiers concepts
Cette section, comme son nom l"indique, pr´esente le concept de base de l"arithm´etique,`a savoir la divisibilit´e. On introduit ensuite les nombres premiers ce qui permet d"´enoncer le
th´eor`eme fondamental de l"arithm´etique (c"est-`a-dire la d´ecomposition en facteurs premiers)
dans lequel les nombres premiers jouent le rˆole de briques ´el´ementaires pour la fabrication
des nombres.1.1 Divisibilit´e
D´efinition 1.1.1Siaetbsont deux entiers, on dit queadiviseb, ou quebestdivisible para, s"il existe un entierqtel queb=aq. On dit encore queaest undiviseurdeb, ou que best unmultipledea. On le notea|b.Propri´et´es
+Siaetbsont deux entiers avecb?= 0,bdiviseasi et seulement si la fractiona b est un entier. +Tous les entiers divisent0, et sont divisibles par1. +Un entiernest toujours divisible par1,-1,net-n. +Sia|b, etb|c, alorsa|c. +Sia|b1,b2,...,bn, alorsa|b1c1+b2c2+...+bncn, quels que soient les entiersc1,c2,...,cn. +Siadivisebetb?= 0, alors|a|6|b|. +Siadivisebetbdivisea, alorsa=±b. +Siaetbsont deux entiers tels quean|bnpour un entiern>1, alorsa|b.Toutes les propri´et´es list´ees pr´ec´edemment sont imm´ediates, `a l"exception de la derni`ere dont
la d´emonstration n"est pas triviale sans bagage arithm´etique. Une preuve possible consiste`a utiliser la caract´erisation de la divisibilit´e par les valuationsp-adiques (voir paragraphe
1.3). Voyons imm´ediatement deux exercices qui montrent comment on peut manipuler la no- tion de divisibilit´e :Exercice
: Soientxetydes entiers. Montrer que2x+ 3yest divisible par7si et seulement si5x+ 4yl"est.Solution
: Supposons que7divise2x+3y, alors il divise6(2x+ 3y)-7(x+ 2y) = 5x+4y. R´eciproquement si7divise5x+ 4y, il divise6(5x+ 4y)-7(4x+ 3y) = 2x+ 3y.⎷Exercice
: Pour quels entiersnstrictement positifs, le nombren2+ 1divise-t-iln+ 1?Solution
: Sin2+1divisen+1, comme tout est positif, on doit avoirn2+16n+1, ce qui n"est v´erifi´e que pourn= 1. On v´erifie ensuite quen= 1est bien solution.⎷ 4Parties enti`eres
D´efinition 1.1.2Sixest un r´eel, on appellepartie enti`eredex, et on note[x], le plus grand entier inf´erieur ou ´egal `ax. Ainsi, on a[x]6x <[x] + 1. Remarque.On d´efinit aussi lapartie d´ecimaledex, comme la diff´erencex-[x]. La partied´ecimale dexest souvent not´ee{x}. Cette notion est moins utilis´ee que la notion de partie
enti`ere et les conventions de notations sont moins usuelles `a ce propos : lors d"un exercice,ou d"un expos´e, il est toujours de bon goˆut de commencer par pr´eciser les notations qui vont
ˆetre employ´ees par la suite.
Notons qu"il fautˆetre prudent avec les nombres n´egatifs : autant pour les nombres positifs, la partie enti`ere correspond au nombre auquel on retire ses chiffres apr`es la virgule, autantce n"est pas le cas pour les nombres n´egatifs. En effet, si on suit la d´efinition, on voit par
exemple que[-3,5] =-4.Les parties enti`eres et parties d´ecimales ob´eissent `a quelques propri´et´es ´el´ementaires que
nous listons ci-dessous :Propri´et´es ´el´ementaires
+On a toujoursx= [x] +{x}. +Pour tout r´eelx, on ax-1<[x]6x +Sixest entier,[x] =xet{x}= 0. Et r´eciproquement si l"une des deux ´egalit´es est v´erifi´ee, alorsxest entier. +[-x] =-[x]-1sauf sixest entier, auquel cas[-x] =-[x]. +Sixetysont deux r´eels,[x] + [y]6[x+y]6[x] + [y] + 1. +Sim >0est un entier, alors il y a exactement[x m ]multiples demcompris entre1et x.La d´emonstration des propri´et´es consiste en de simples manipulations de la d´efinition et
principalement de l"in´egalit´e[x]6x <[x] + 1. Elle est laiss´ee au lecteur. On remarquera que tr`es souvent les questions faisant intervenir des parties enti`eres se r´esument `a de la manipulation d"in´egalit´es comme le montre par exemple l"exercice suivant :Exercice
: On suppose que4n+ 2n"est pas le carr´e d"un nombre entier. Montrer que pour n>0, on a :h⎷ n+⎷ n+ 1i =h⎷4n+ 2i
Solution
: Remarquons tout d"abord que l"on a toujours l"in´egalit´e : n+⎷ n+ 1<⎷ 4n+ 2 En effet, en ´elevant au carr´e, on a `a comparer2n+ 1 + 2⎷ n2+net4n+ 2, soit2⎷
n 2+net2n+ 1et l"in´egalit´e devient ´evidente apr`es une nouvelle ´el´evation au carr´e.
Il reste `a prouver qu"il n"existe aucun entierktel que : n+⎷ n+ 1< k6⎷ 4n+ 2 5 soit, encore en ´elevant au carr´e qu"il n"existe aucun entierktel que :2n+ 1 + 2⎷
n2+n < k264n+ 2
Mais il est clair que4n+ 1<2n+ 1 + 2⎷
n2+net un tel entierkv´erifiraita fortiori
4n+ 1< k264n+ 2. Commekest entier, il vient forc´ementk2= 4n+ 2, mais cela n"est
pas possible puisque l"on a suppos´e que4n+ 2n"´etait pas le carr´e d"un entier.⎷ Remarque.En fait,4n+ 2n"est jamais le carr´e d"un entier. En effet, le nombre4n+ 2estpair, et s"il ´etait le carr´e d"un entier, il serait le carr´e d"un entier pair. Mais alors4n+ 2
devrait ˆetre un multiple de4, ce qui n"est, `a l"´evidence, pas le cas. L"´egalit´e pr´ec´edente de
parties enti`eres est donc valable pour tout entiern>1, sans hypoth`ese suppl´ementaire. Une propri´et´e amusante des parties enti`eres qui montre ´egalement que parfois (souvent)les manipulations d"in´egalit´es ne sont pas faciles est le th´eor`eme de Beatty que voici :
Th´eor`eme 1.1.3 (Beatty)Soientαetβdeux r´eels strictements positifs. On noteSα(resp.Sβ) l"ensemble des entiers strictement positifs qui s"´ecrivent sous la forme[nα](resp.
[nβ]) pour un certain entiern. Les ensemblesSαetSβforment une partition deN?si, et seulement siαetβsont irrationnels et v´erifient 1 +1 = 1. D´emonstration.Commen¸cons par supposer queαetβsont des irrationnels v´erifiant1 1 = 1. Soitkun entier strictement positif. Il est dans l"ensembleSαsi et seulement s"il existe un entierntel que : nα-1< k < nαl"in´egalit´e de droite ´etant stricte carαest suppos´e irrationnel. L"´equation se transforme et
donne :k ff¡ n ¡k
ff +1 ff ,k ff +1£contient un entier. De mˆeme
k?Sβsi et seulement si l"intervallei k fi ,k fi +1 h contient un entier. ff ,k ff + 1£est de longueur1et ses bornes sont irrationnelles, donc il contient un et un seul entiern. Sinet donck?Sβ. Sik´etait `a la fois ´el´ement deSαet deSβ, il y aurait un entier dans
ff ,k ff +1