[PDF] [PDF] Cours darithmétique

[PDF] Les nombres premiers

Les deux propositions suivantes vont montrer qu'il existe beaucoup de nombres premiers Proposition 4 1 Tout entier n ≥ 2 admet un diviseur premier Si n n'est  

[PDF] Nombres premiers - Labomath

Les nombres entiers dont la somme des chiffres est divisible par 3 sont eux- mêmes Pour montrer qu'un nombre entier est premier, il suffit de vérifier qu'il n' est 

[PDF] Les nombres premiers - Lycée dAdultes

22 juil 2015 · Définition 1 : Un nombre premier est un entier naturel qui admet exacte- Exemple : Montrer que 109 est un nombre premier On a 10 < √109 

[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

http://www maths-et-tiques fr/telech/Euclide pdf admet un couple solution d' entiers Méthode : Démontrer que deux entiers sont premiers entre eux 1 n'est pas un nombre premier car il ne possède qu'un seul diviseur positif Liste des 

[PDF] NOTION DE MULTIPLE, DIVISEUR ET NOMBRE PREMIER

Un nombre entier naturel est un nombre entier qui est positif L'ensemble des Montrer que la somme de trois entiers consécutifs est toujours un multiple de 3

[PDF] Démonstrations de primalité Nombres de Mersenne et de Fermat

aurait pu trouver un nombre premier de 7 chiffres dès 1732 Pour montrer que M17 est premier, il faudrait tester tous les diviseurs premiers jusqu'à 362

[PDF] Cours darithmétique

Expliquons comment on proc`ede pour montrer qu'un pgcd en divise un autre en donnant un Un nombre qui n'est pas premier est appelé nombre composé

[PDF] Nombres premiers - Annuaire IMJ-PRG

Ah, j'oubliais, c'est un nombre premier EXERCICE 2 1 Si tous les facteurs premiers p d'un entier n vérifient p ≡ 1 (mod 4), montrer 

[PDF] Exercice 4 : nombre premier - CNRS

L'utilisateur entre 1, 2 ou 3 et l'ordinateur tire un nombre aléatoire compris entre 1 et 3 On affiche à La partie est remportée par le premier à atteindre 10 points On n'a pas pu montrer ni qu'il existe un nombre infini de paires ni qu'il existe

[PDF] Exercices sur les nombres premiers EXERCICE 1 : Démontrer que

p > 3 est un nombre premier 1 Quels sont les restes possibles dans la division de p par 12 ? 2 Prouver que p2 + 11 est divisible par 12 

[PDF] savoir si un nombre est premier algorithme

[PDF] décomposition en série de fourier exercices corrigés

[PDF] transformée de fourier signal carré

[PDF] décomposition en série de fourier d'un signal triangulaire

[PDF] signal triangulaire transformée de fourier

[PDF] décomposition en série de fourier de signaux usuels

[PDF] décomposition en série de fourier pdf

[PDF] décomposition en série de fourier d'un signal dent de scie

[PDF] décomposition en série de fourier d'un signal sinusoidal redressé

[PDF] décomposition d une feuille

[PDF] matière organique pdf

[PDF] matière organique sol pourcentage

[PDF] recomposer un nombre ce2

[PDF] l hydrogénocarbonate de sodium nahco3 s est un solide blanc

[PDF] technique de construction batiment 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.

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⎷

n

2+n < k264n+ 2

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

n

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