Cours darithmétique PDF parant les olympiades internationales de

Cours darithmétique

parant les olympiades internationales de mathématiques. Le plan complet de ce cours est : 1. Premiers concepts. 2. Division euclidienne et conséquences.

Exercices de mathématiques - Exo7

2 Division pgcd. Exercice 2. 1. Effectuer la division euclidienne de A par B : (a) A = 3X5 +4X2 +1

Algèbre - Cours de première année

a b ? et pgcd(a

fondmath1.pdf

5.4 Pgcdppcm . Ceci est valable également pour les examens et ... Il est possible de trouver des cours et des exercices dans de nombreux ouvrages dispo ...

ficall.pdf

le cours d'analyse. Montrer que si a ? 1 et b ? 1 sont des entiers de pgcd d et si on pose a = da ;b = db

LATEX pour le prof de maths !

11-Jan-2021 2.6.1 Caractères réservés. 2.6.1.1 Le symbole de pourcentage %. Remarquez le %Cours après le <begin{document}. Le texte Cours est un ...

Exercices et problèmes de statistique et probabilités

Science Sup 19.3x250) — 2012/4/27 — 14:21 — page i — #1 Corrigés des exercices . ... 1. Probabilités. RAPPEL DE COURS. 1.1 Rappels de Mathématiques.

Algèbre et Analyse Recueil dExercices Corrigés

08-Mar-2018 que certains sujets d'examens. Avant chaque série d'exercices nous faisons un bref rappel des notions de cours ; qu'on pourra retrouver en ...

PPCM PGCD Nombres Premiers

Exercice 1 : Trouver le PPCM et le PGCD des couples de nombres suivants : (33 ;12) Exercice 4 : Dans un lycée est organisé une course par équipes.

Examen dalgèbre du 18 juin 2012 durée : 4h Questions de cours

Barême indicatif :question de cours3 points ; exercice 1

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 plusquotesdbs_dbs4.pdfusesText_8

[PDF] Cours darithmétique parant les olympiades internationales de

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