[PDF] Cours darithmétique 1Plus nous avons jugé l'

View - Download Cours darithmétique

Previous PDF

Next PDF

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.

2

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

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

3

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

+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.quotesdbs_dbs2.pdfusesText_3

[PDF] arithmétique dans z cours exo7

[PDF] arizona cardinals 87

[PDF] arizona charitable organization registration

[PDF] arizona charitable organizations

[PDF] arizona charitable tax credit list 2020

[PDF] arizona civics test flashcards

[PDF] arizona coin buy list

[PDF] arizona court of appeals forms

[PDF] arizona court of appeals rules

[PDF] arizona dashboard

[PDF] arizona foster charities

[PDF] arizona non profit organizations list

[PDF] arizona private school tax credit 2019

[PDF] arizona qcfo

[PDF] arizona qualifying contributions