[PDF] Cours darithmétique PDF arith

Exercice 30* Soient (an) et (bn) deux suites d'entiers On suppose que les suites (an + bn) et (anbn) sont arithmétiques Montrer qu'il existe une constante c tel

Previous PDF

Next PDF

[PDF] Cours darithmétique

Exercice 30* Soient (an) et (bn) deux suites d'entiers On suppose que les suites (an + bn) et (anbn) sont arithmétiques Montrer qu'il existe une constante c tel

[PDF] Exercices avec Solutions

des exercices des séries des travaux dirigés et examens (avec corrigés) du séries d'exercices, comparer leurs solutions avec celles proposées et prévoir des Ecrire un algorithme qui permet à l'utilisateur de saisir une suite caractère se paramétrées : SommeZ, DiffZ et ProdZ nécessaires à l'arithmétique sur les

[PDF] Exo7 - Exercices de mathématiques

51 121 02 Suite définie par une relation de récurrence Calculer pgcd(18,385) par l'algorithme d'Euclide, en déduire un couple (u0,v0) ∈ Z2 solution de l' équation Exercice 458 Moyennes géométrique et arithmétique Exercice 584 Examen novembre 2001 Comme il se fatigue, ses pas sont de plus en plus courts

[PDF] Algorithmique et programmation - USTO

programmation Il constitue un support de cours pour des étudiants n'ayant aucune On trouvera l'ensemble des questions posées aux différents examens écrits L'algorithmique est un terme d'origine arabe, composé d'une suite d' instructions Les opérateurs arithmétiques qui permettent d'effectuer des opérations

[PDF] SUITES ARITHMÉTIQUES et SUITES GÉOMÉTRIQUES : exercices

Suites arithmétiques - Définition Ex 1 : Vrai ou faux : restituer les notions du cours Soit (un ) la suite arithmétique de 1er terme 3 et de raison 4 1 ) u9−4=u8

[PDF] Suites Exercices corrigés - Free

Soit (un) une suite géométrique de premier terme u0 = 1 et de raison q ∈ ]0 ; +∞ [ C'est du cours la condition de monotonie des deux suites n'est pas l' utilise par exemple pour calculer les décimales de π , c'est l'algorithme de Brent et

[PDF] Exercices de mathématiques pour la classe terminale - 2e - BDRP

6 août 2020 · Ce document fait suite à celui publié à l'automne 20141 et vise à mêmes La seconde partie propose des exercices nouveaux déclinés en deux À l'aide de la calculatrice, déterminer la valeur que cet algorithme affichera si = 60 connaissent une panne au cours de la première année et 61 des

[PDF] cours

Ceci est valable également pour les examens et Il est possible de trouver des cours et des exercices dans de nombreux ouvrages dispo- C'est ce que nous appellerons la somme d'une suite arithmétique, que nous verrons avec les Les coefficients de Bézout u et v s'obtiennent en remontant l'algorithme d'Euclide

[PDF] suites arithmetiques et geometriques exercices corriges

Cours et exercices de mathématiques M CUAZ SUITES Exercice n°7 1) En reconnaissant la somme des termes d'une suite arithmétique, calculer 1 1 5 19

[PDF] Cours darithmétique

L'algorithme d'Euclide étendu permet de déterminer d = pgcd(a, b) ainsi que deux entiers u et v vérifiant d = au + bv Reprenons la suite (DE) des divisions

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´ementaire

possible. 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 ´etoiles

1. 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. 1

Liste des abbr´evations :

AMM American Mathematical Monthly

APMO The Asian Pacific Mathematics Olympiad

CG Concours g´en´eral

OIM Olympiades Internationales de Math´ematiques

SL Short List

TDV Tournoi Des Villes

Liste des notations :

?ensemble vide

Nensemble des entiers naturels (positifs ou nuls)

N ?ensemble des entiers naturels strictement positifs

Zensemble 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.

Table 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

´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

1 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

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.⎷ 4

Parties 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 partie

d´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, autant

ce 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⎷ n

2+net4n+ 2, soit2⎷

n 2+n

et2n+ 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⎷

2+n < k264n+ 2

Mais il est clair que4n+ 1<2n+ 1 + 2⎷

2+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+ 2est

pair, 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. Sin ¡ k+ 1-n fi +1

et donck?Sβ. Sik´etait `a la fois ´el´ement deSαet deSβ, il y aurait un entier dans

ff ,k ff +1

£et un dans l"intervallei

k fi ,k fi +1 h et donc par le mˆeme raisonnement ff ,k ff + 1£, ce qui n"est pas possible. 6 R´eciproquement, supposons queSαetSβforment une partition deN?. Consid´erons un entierkstrictement positif. Il y a£k ff y ah k fi i entiers dans{1,...,k}qui sont dansSβ. Du fait de la partition, il vient : ·k ff +·k fi =k pour toutk. En faisant tendrekvers l"infini, il vient : 1 +1quotesdbs_dbs46.pdfusesText_46

[PDF] [PDF] Cours darithmétique

Cours d"arithm´etique

Premi`ere partie

PierreBornsztein

XavierCaruso

PierreNolin

MehdiTibouchi

D´ecembre 2004

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

1. Toutes les solutions sont rassembl´ees `a la fin du document.

Liste des abbr´evations :

AMM American Mathematical Monthly

APMO The Asian Pacific Mathematics Olympiad

CG Concours g´en´eral

SL Short List

TDV Tournoi Des Villes

Liste des notations :

Nensemble des entiers naturels (positifs ou nuls)

Zensemble des entiers relatifs

Qensemble des nombres rationnels

σ(n)somme des diviseurs positifs den

3Un produit index´e par l"ensemble vide est ´egale `a1.

Table 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

´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

1 Premiers concepts

1.1 Divisibilit´e

Propri´et´es

Exercice

Solution

Exercice

Solution

Parties enti`eres

ˆetre employ´ees par la suite.

Propri´et´es ´el´ementaires

Exercice

4n+ 2i

Solution

2+net4n+ 2, soit2⎷

2n+ 1 + 2⎷

2+n < k264n+ 2