parant les olympiades internationales de mathématiques Le plan complet de ce 1Plus nous avons jugé l'exercice difficile, plus le nombre d'étoiles est important 1 2 3 Algorithme d'Euclide étendu et théor`eme de Bézout `a utiliser la caractérisation de la divisibilité par les valuations p-adiques (voir paragraphe 1 3)
Previous PDF | Next PDF |
[PDF] ENSM - Correction Feuille TD1
Mention Mathématiques, spécialité Enseignement des mathématiques Algorithmique et graphes, thèmes du second degré Feuille TD n°1 Écrire un algorithme permettant d'afficher le plus petit de trois nombres entrés au clavier Réponse
[PDF] Cours au Lycée de Wallis et Futuna
Critères de divisibilité 2/ Second cas : Si a = b alors le couple (1; a) convient [ Exercices 105 à 107 page 464 ,Maths Repère,Hachette] ▻ pgcd(a Pour trouver le pgcd de tels nombres nous aurons besoin d'un algorithme plus puissant
[PDF] PGCD ET NOMBRES PREMIERS - maths et tiques
Méthode : Recherche de PGCD par l'algorithme d'Euclide Pour le vérifier, on teste la divisibilité par tous les nombres premiers inférieurs à Soit : 2, 3, 5, 7, 11,
[PDF] Algorithme dEuclide Table des matières - ENS
dans un second temps les propriétés liées au théorème de Bézout Un nombre est divisible par 2 si et seulement si son dernier chiffre est 0, 2, 4, 6 ou 8 Éléments constituent une sorte d'encyclopédie du savoir mathématique de son temps
[PDF] Algorithmes et logique au lycée - IREM dAix-Marseille
maine de l'algorithmique et de la logique aux professeurs de mathématiques Ces chapitres sont Ce second algorithme calcule le produit de deux nombres entiers À partir des hypothèses ”n est un entier” (Γ), et ”n est divisible par 6” (A),
[PDF] ARITHMETIQUE Exercice 1 - Licence de mathématiques Lyon 1
Si un nombre est divisible par 2 et par 3, alors il est divisible par 12 4 Si un nombre est divisible par 10 et utilise l'algorithme d'Euclide En multiplie par 59 : 2
[PDF] Exercices de mathématiques - Exo7
16 103 03 Pgcd, ppcm, algorithme d'Euclide 62 Pour tout n ∈ N, le nombre 16n +4n +3 est-il divisible par 3 Exercice 481 Équations du second degré
[PDF] Cours darithmétique
parant les olympiades internationales de mathématiques Le plan complet de ce 1Plus nous avons jugé l'exercice difficile, plus le nombre d'étoiles est important 1 2 3 Algorithme d'Euclide étendu et théor`eme de Bézout `a utiliser la caractérisation de la divisibilité par les valuations p-adiques (voir paragraphe 1 3)
[PDF] Exercice 4 : nombre premier - CNRS
Ecrire un algorithme permettant de jouer au jeu pierre-papier-ciseaux contre pas un nombre premier, N n'est pas divisible par d car on a déjà divisé N
[PDF] Que faire en algorithmique en classe de seconde ? - lAPMEP
Algorithme 1 : On donne le programme de calcul suivant (algorithme) : a Choisir un nombre x b Calculer le
[PDF] Algorithme ( Merci de m'aider au plus vite) =D 2nde Mathématiques
[PDF] algorithme ( tester la divisibilité d'un nombre ) 2nde Mathématiques
[PDF] Algorithme (2) 2nde Mathématiques
[PDF] Algorithme (Algobox) 2nde Mathématiques
[PDF] Algorithme (DM de math) 1ère Mathématiques
[PDF] Algorithme (DM de maths pour DEMAIN !!) 2nde Mathématiques
[PDF] Algorithme (dm de maths pour demain !) 2nde Mathématiques
[PDF] Algorithme (exercice de maths ) 2nde Mathématiques
[PDF] Algorithme (fonction) urgent !!!!!!! 2nde Mathématiques
[PDF] Algorithme (Niveau Seconde) 2nde Mathématiques
[PDF] Algorithme , conjecture , valeur 3ème Mathématiques
[PDF] Algorithme , manipulation de boucles Bac +1 Informatique
[PDF] Algorithme , manipulation de boucles Bac +1 Mathématiques
[PDF] Algorithme - Calcul du nombre d'arêtes d'un solide convexe 3ème Mathématiques
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´ementairepossible. 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 ´etoiles1. 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. 1Liste des abbr´evations :
AMM American Mathematical Monthly
APMO The Asian Pacific Mathematics Olympiad
CG Concours g´en´eral
OIM Olympiades Internationales de Math´ematiquesSL Short List
TDV Tournoi Des Villes
Liste des notations :
?ensemble videNensemble des entiers naturels (positifs ou nuls)
N ?ensemble des entiers naturels strictement positifsZensemble 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.
2Table 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
31 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.⎷ 4Parties 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 partied´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, autantce 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⎷ n2+net4n+ 2, soit2⎷
n 2+net2n+ 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⎷
n2+n < k264n+ 2
Mais il est clair que4n+ 1<2n+ 1 + 2⎷
n2+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+ 2estpair, 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
quotesdbs_dbs45.pdfusesText_45