[PDF] Cours darithmétique précédents : Exercice : On





Previous PDF Next PDF



LES NOMBRES PREMIERS – PPCM

La multiplication de deux nombres même très grands



PGCD ET NOMBRES PREMIERS

Théorème de Bézout : Soit a et b deux entiers naturels non nuls. a et b sont premiers entre eux si et seulement si



PGCD et PPCM

Combinaisons : Les combinaisons aZ + bZ sont exactement les multiples du PGCD. 1. Page 2. 2 Nombres premiers entre eux. Deux nombres sont premiers entre 



PGCD - PPCM Théorèmes de Bézout et de Gauss

15 ?.?. 2559 Définition 1 : Soit a et b deux entiers relatifs non nuls. ... Il ne faut pas confondre des nombres premiers entre eux et des nombres pre-.



PGCD et PPCM de deux entiers :

On suppose a et b premiers entre eux donc pgcd(a ; b) = 1. L'un des deux nombres est non nul



Remédiation – PGCD et PPCM Plus grand commun diviseur (PGCD)

Une fraction est irréductible si le PGCD de ses termes est 1. On dit alors que leurs termes sont premiers entre eux. Vérification du PGCD de deux nombres. Vrai 



Cours darithmétique

précédents : Exercice : On définit le n-i`eme nombre de Fermat par la formule Fn = 22n + 1. Montrer que les Fn sont deux `a deux premiers entre eux.



PEI Math 1 Module 2 / Feuille nOl/page l

La propriété « le produit du PGCD de deux nombres par leur PPCM est égal au produit des ces a' et b' sont donc deux diviseurs de 36 premiers entre eux.



Untitled

g) Faux car 6 et 12 sont deux nombres non premiers entre eux dont le PPCM vaut 12. h) Vrai



calcul-multiples-et-diviseurs.pdf

Les multiples de deux nombres (ou plus) sont les multiples du ppcm de ces Deux nombres naturels dont le pgcd est 1 sont dits « premiers entre eux ».



[PDF] LES NOMBRES PREMIERS – PPCM - Pierre Lux

La multiplication de deux nombres même très grands n'est pas compliquée : avec du papier Si a et b sont premiers entre eux on a PPCM(a ; b) = a × b



[PDF] ppcmpdf

cherche des multiples communs à deux nombres on peut même si l'énoncé ne demande pas de trouver le plus petit d'entre eux chercher le PPCM des deux 



[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques

Définition : Soit a et b deux entiers naturels non nuls On dit que a et b sont premiers entre eux lorsque leur PGCD est égal à 1 Exemple :



[PDF] Nombres premiers pgcd et ppcm - Lycée dAdultes

27 jui 2016 · Nombres premiers pgcd et ppcm 3 3 Nombres premiers entre eux il admet exactement deux diviseurs 1 et lui-même



[PDF] PGCD et PPCM de deux entiers :

Montrer que les nombres 3 920 et 1 089sont premiers entre eux et déterminer des entiers u et v tels que 3920u +1089v = 1 Méthode : on écrit toutes les 



[PDF] Leçon 7 : Le plus petit commun multiple (ppcm) et le plus grand

Le plus petit des multiples corlmuns à deux nombres a et b s'appelle leur plus petit commun multiple et se note ppcm(ab)



[PDF] PGCD PPCM nombres premiers décomposition en produit de

Quand le PGCD de deux nombres vaut 1 on dit qu'ils sont premiers entre eux Par exemple : • deux nombres premiers distincts sont toujours premiers entre



[PDF] I PGCD et PPCM de deux nombres entiers - My MATHS SPACE

I 3 Nombres premiers entre eux Définition 2 On dit que deux entiers relatifs non nuls a et b sont premiers entre eux lorsque leur PGCD est égal



[PDF] PGCDPPCM nombres premiers entre-eux:

Prop: Tous les diviseurs communs à deux entiers sont les diviseurs de leur PGCD Déf: Deux nombres sont dits premiers entre-eux s'ils ont 1 pour PGCD



PPCM - Maxicours

Quel que soit l'entier naturel p les nombres 9p + 4 et 2p + 1 sont premiers entre eux et leur PPCM est égal à leur produit

  • Comment calculer le PPCM avec les nombres premiers ?

    Le ppcm (plus petit commun multiple), de plusieurs nombres décomposés en facteurs premiers est égal au produit de tous les facteurs premiers communs ou non, chacun d'eux n'est pris qu'une seule fois, avec son exposant le plus grand. 45 = 3?? = 3²?. Le ppcm = 2²?²? = 180.

  • Comment trouver le PPCM de deux nombres ?

    Cette méthode consiste à diviser simultanément les nombres dont on cherche le PPCM par des diviseurs premiers. Le PPCM sera alors le produit de ces diviseurs premiers. Attention, la méthode est légèrement différente de celle présentée pour le PGCD.

  • Quel est le PPCM de 5 et 7 ?

    Exemples. Trouver le PPCM de 5 et 7 : 1.
  • Le PPCM est donné par le rapport du produit des 2 entiers donnés et de leur PGCD. On obtient la formule suivante PPCM (a,b) = a × b ÷ PGCD (a,b). Vous pouvez rechercher le PPCM d'entiers jusqu'à 20 chiffres.

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