maths 2009-2010_{Terminale S}_{Arithmétique} 121 90  91  92  93  94  95  96  97 120 89  66  67  68  69  70  71  98 119 88  65  50  51  52  53  72  99 118 87  64  49  42  43  54  73 100 117 86  63  48  41  44  55  74 101 116 85  62  47  46  45  56  75 102 115 84  61  60  59  58  57  76 103 114 83  82  81  80  79  78  77 104 113 112 111 110 109 108 107 106 105 Lycée Saint-Henri IV-Le Grand

arithmétique

cours avec exercices

S O M M A I R E

1 Divisibilité, PGCD, PPCM  6
1.1 Divisibilité dans � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Division euclidienne dans � . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Diviseurs communs à deux entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Propriétés du pgcd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Notion de ppcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6 Exercices et problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Nombres premiers  13
2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Propriétés de divisibilité des nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Décomposition en facteurs premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Quelques propriétés de l’ensemble des nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Exercices et problèmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1

Divisibilité, PGCD, PPCM

C H A P I T R E

Euclide, en grec ancien Eukleidês (né vers −325, mort vers −265 à Alexandrie) est un mathématicien de la Grèce antique ayant probablement vécu en Afrique, auteur des Éléments, qui sont considérés comme l’un des textes fondateurs des mathématiques modernes. Peu d’informations sont connues à propos de la vie d’Euclide. Contemporain d’Archimède (né en −287 et mort en −212), il naît vers −325 et meurt vers −265, mais, selon le mathématicien Christian Velpryses, ses dates de naissance et de mort sont inconnues. Il part en Égypte pour y enseigner les mathématiques sous le règne de Ptolémée I^{er}. Il travaille au musée d’Alexandrie et à l’école de mathématiques. Entouré de ses disciples, il mène de nombreux travaux de recherche.

(Source : Wikipédia)

Divisibilité dans � 1

1 1 Diviseurs

Soient et des entiers naturels. On dit que divise (ou « est un diviseur de » ou « est divisible par ») s’il existe � tel que .

Définition 1

Exemple. Le nombre 385 est divisible par 5 car 385 5 77.

Remarques.

a. Le nombre 1 divise tous les nombres. C’est le seul à avoir cette propriété. b. Un nombre est toujours divisible par . c. Le seul nombre divisible par 0 est 0 lui-même. d. Le nombre 0 est divisible par tous les nombres. C’est le seul à avoir cette propriété.

Soit un entier naturel. L’ensemble des diviseurs de , noté (() ), est l’ensemble des � qui divisent .

Définition 2

Exemple. On a (385) 1 5 7 11 35 55 77 385 é

a. Si ^{}divise , alors divise et ^{}divise .

b. Si 0 et si divise , alors 1 .

c. Si divise et si divise , alors divise .

d. Si divise et , alors divise pour tous les entiers et .

Propriétés 1

1 2 Multiples

Soient et deux entiers naturels. On dit que est un multiple de s’il existe � tel que .

Définition 3

Exemple. Le nombre 42 est un multiple de 6 car 42 6 7.

est un multiple de si et seulement si divise . Propriété 2

Division euclidienne dans � 2

Soient et deux entiers naturels. Si 0, alors il existe un unique couple ( ) tel que

avec 0 .

Théorème 1

Démonstration. Puisque est non nul, il existe tel que ( 1). On pose et on a le résultat voulu. □

Exemple. Trouvons la division euclidienne de 314 par 78. On a 2 78 156, 3 78 234, 4 78 312 et 5 78 390 et donc 312 314 390, d’où 4 et 314 312 2. La division euclidienne est donc 314 78 4 2.

L’entier est appelé le quotient de la division euclidienne et l’entier est le reste de la division euclidienne.

Définition 4

a. Le nombre divise si et seulement si 0.

b. Si , alors 0 et .

c. Tout entier positif s’écrit sous la forme  avec 0, 1, ... ou  1.

Propriétés 3

Diviseurs communs à deux entiers 3

3 1 Définition

Si et sont deux entiers naturels, on note ( ) l’ensemble des diviseurs communs à et .

Définition 5

Exemple. On a (12 8) 1 2 4

a. Si et sont deux entiers naturels, ( ) ( ) ( ).

b. On a toujours 1 ( ).

c. Si ( ) avec 0 et 0, alors max( ).

d. ( 0) ( ).

Propriétés 4

Si et ne sont pas tous nuls, l’ensemble ( ) a un plus grand élément que l’on appelle le pgcd (plus grand diviseur commun) de et .

Théorème 2

Démonstration. Si 0 et  0, on a ( ) ( 0) ( ) et donc  convient ;
si 0 et  0, de même  convient. Si  0 et  0, alors, d’après la propriété 4,

l’ensemble ( ) est non vide et est majoré ; il possède donc un plus grand élément . □

Remarque. Le pgcd de 0 et 0 n’est pas défini car (0 0) (0) � n’a pas de plus grand élément.

3 2 Algorithme d’Euclide

L’algorithme d’Euclide permet de trouver le pgcd de deux nombres. L’idée est de construire une suite d’entiers _{}tels que

( ) ( _{1}) ( _{1} _{2}) ( _{}0) ( _{})

auquel cas _{}sera le plus grand diviseur commun à et .

1.Ensemble des diviseurs et division euclidiennes

Soient et deux entiers naturels non nuls. Si on peut écrire  avec  �

(on ne suppose pas a priori que 0 ), alors ( ) ( ).

Lemme 1

Démonstration. Si ( ), alors divise et donc divise et donc ( ).

Réciproquement, si  ( ), alors divise  et donc  ( ).  □

2.Divisions euclidiennes successives

Algorithme d’Euclide

Soient et deux entiers naturels non nuls. On écrit les divisions euclidiennes successives

1 _{1}  avec 0 _{1}
1 _{2} _{2} avec 0 _{2} _{1} (possible si _{1} 0)
1 _{2} _{3} _{3} avec 0 _{3} _{2} (possible si _{2} 0)

Il existe un rang �^{}tel que _{}0.

Théorème 3

Démonstration. Il suffit de remarquer que s’il n’existait pas de rang tel que _{}0, alors la suite ( _{}) serait une suite strictement décroissante d’entiers naturels, ce qui est absurde. □

3.Conséquence pour le pgcd

Soient et deux entiers naturels non tous nuls. Le pgcd de et est l’unique entier tel que ( ) ( ).

Corollaire 1

Démonstration. C’est juste une reformulation de l’algorithme d’Euclide : ( ) ( _{1}) ( _{}0) ( _{}) et donc le plus grand élément de ( ) est _{}. □

3 3 Relation de Bézout

Soient et deux entiers naturels non tous nuls. Un entier est le pgcd de et si et seulement si divise et et s’il existe et tels que

Théorème 4

Démonstration. : Supposons que divise et et qu’on puisse écrire . Si est un diviseur commun à et , alors divise ; autrement dit, tout élément de ( ) divise ; on en déduit que le pgcd de et est . Puisqu’il est aussi car ( ) , on conclut que est le pgcd de et ; : Soit le pgcd de et ; il est évident que divise et ; montrons l’existence de et . On utilise l’algorithme d’Euclide :

1 _{1} avec 0 _{1}
1 _{2} _{2} avec 0 _{2} _{1} (possible si _{1} 0)
1 _{2} _{3} _{3} avec 0 _{3} _{2} (possible si _{2} 0)
1 _{}_{1} 0

On a _{}. Montrons par récurrence sur que l’on peut écrire _{}_{}_{}. On a

1  _{1}  _{1} 1 et _{1}  _{1}
Supposons que _{}_{}_{}avec  et montrons que _{1}  _{1}  _{1}. On a

1 _{1} _{1} _{}_{1} _{1} _{1}( _{}_{}) ( _{1} _{1} _{}) ( _{1} _{1} _{})

et donc le choix _{1} _{1} _{1} _{}et _{1} _{1} _{1} _{}convient. En particulier, pour , on obtient, en posant _{}et _{},

La démonstration est terminée. □

Propriétés du pgcd 4

4 1 Entiers premiers entre eux

Deux entiers naturels non nuls et sont dit premiers entre eux si et seulement si leur pgcd vaut 1.

Définition 6

lemme de Gauss

Soient , et des entiers naturels non nuls. Si divise avec et premiers entre eux, alors divise ou divise .

Lemme 2

Démonstration. Puisque et sont premiers entre eux, il existe et tels que 1 ; en multipliant par , on obtient . Puisque divise , on en déduit que divise . □

Soient et deux entiers naturels premiers entre eux. Si et divisent , alors divise .

Corollaire 2

Démonstration. Puisque divise , on peut écrire ; puisque divise , il divise et puisque et sont premiers entre eux, divise et donc on peut écrire et donc , ce qui montre que divise . □

4 2 Mutliplicativité

Soient , et trois entiers naturels non nuls et le pgcd de et . Le pgcd de et est .

Propriété 5

Démonstration. Il est évident que est un diviseur commun à et . C’est le pgcd car

on peut écrire  et donc ( ) ( )  .  □

Notion de ppcm 5

5 1 Définition

L’ensemble des multiples communs à et est non vide (il contient ) et minoré par min( ) ; il possède donc un plus petit élément, noté et appelé le ppcm (plus petit commun multiple) de et .

5 2 Lien avec le pgcd

Soient et deux entiers naturels non nuls, leur pgcd et leur ppcm.

a. .

b. Tout multiple commun à et est multiple de .

Propriété 6

Démonstration.

a. Notons tout d’abord que ^{}\frac{}{}est un multiple commun à et ; en effet, si on pose ^{}et ^{}, on a ^{}^{}donc ^{}est un multiple de et ^{}^{}donc est un multiple de .

Reste à montrer que ^{}. Soit un multiple quelconque de et ; puisque est un multiple commun à et donc on peut écrire et ^{}. On a donc d’où ^{}^{}^{}; puisque ^{}et ^{}sont premiers entre eux (conséquence de la relation de Bézout), on en déduit que ^{}divise ^{}et donc ^{}^{}^{}; ainsi, et donc ^{}, ce qui montre que est multiple de ^{}; le multiple étant arbitraire, on en déduit que ^{}est le ppcm de et .

b. Comme on vient de le voir, tout multiple de et est multiple de ^{}, d’où le

résultat.

□

Exercices et problèmes

Diviseurs et multiples

1 Écrire la liste des diviseurs des nombres suivants.

13 56 198 6754 12553

2 Écrire la liste des multiples 200 des nombres suivants.

7 36 27 89 101 59 13

3 Si �, montrer que ( 1) est pair et que ( ^{2} 1) est divisible par 3.

4 ^{⋆} Déterminer les entiers tels que _{}^{2} 3 6 soit un multiple de .

Division euclidienne

5 Effectuer les divisions euclidiennes de par dans les cas suivants.

{a. 87 et 5. \atop b. 454 et 33.}  {c. 765 et 890. \atop d. 8997 et 654.}

6 On effectue la division euclidienne de 124 par un entier et on trouve un quotient un reste égal à 9. Quelles sont les valeurs possibles de et ?

7 On écrit la division euclidienne de par . Quelle est la division euclidienne de 1 par ? de par ?

Algorithme d’Euclide, pgcd

8 En utilisant l’algorithme d’Euclide, calculer le pgcd des nombres et suivants.

{a. 87 et 5. \atop b. 454 et 33.}  {c. 765 et 890. \atop d. 8997 et 654.}

9 On effectue l’algorithme d’Euclide pour des nombres et et on trouve pour pgcd _{4} 39 et comme suite de quotients successifs _{1} 1, _{2} 5, 3 1, _{4} 6 et _{5} 2. Quelle est la valeur de et ?

10 ^{⋆} Trouver des entiers naturels tels que 72 et pgcd( ) 8.

11 Reprendre les entiers de l’exercice 8et écrire une relation de la forme où pgcd( ).

ppcm

12 Reprendre les entiers de l’exercice 8 et trouver leur ppcm.

13 Trouver deux entiers naturels et tels que pgcd( ) 24 et ppcm( ) 2160.

14 Vérifier que

ppcm(1 2 3 4)2sin \frac{}{2} 2sin \frac{}{3} 2sin \frac{2}{3}
2sin \frac{}{4} 2sin \frac{3}{4}

(On fait le produit sur les 2sin \frac{}{}avec et premiers entre eux pour 2, 3 ou 4.)

2

Nombres premiers

C H A P I T R E

Johann Carl Friedrich Gauss (30 avril 1777 – 23 février 1855) est un mathématicien, astronome et physicien allemand. Doté d’un grand génie, il a apporté de très importantes contributions à ces trois sciences. Surnommé « le prince des mathématiciens », il est considéré comme l’un des plus grands mathématiciens de tous les temps. La qualité extraordinaire de ses travaux scientifiques était déjà reconnue par ses contemporains. Dès 1856, le roi de Hanovre fit graver des pièces commémoratives avec l’image de Gauss et l’inscription Mathematicorum Principi (« prince des mathématiciens » en latin). Gauss n’ayant publié qu’une partie infime de ses découvertes, la postérité découvrit la profondeur et l’étendue de son œuvre uniquement lorsque son journal intime, publié en 1898, fut découvert et exploité. Considéré par beaucoup comme distant et austère, Gauss ne travailla jamais comme professeur de mathématiques, détestait enseigner et collabora rarement avec d’autres mathématiciens. Malgré cela, plusieurs de ses étudiants devinrent de grands mathématiciens, notamment Richard Dedekind et Bernhard Riemann. Gauss était profondément pieux et conservateur. Il soutint la monarchie et s’opposa à Napoléon qu’il vit comme un semeur de révolution.

(Source : Wikipédia)

Définitions 1

Un nombre entier 2 est premier s’il divisible uniquement par 1 et par lui-même. Définition 1

Remarque. Noter que 1 n’est pas un nombre premier. La raison est que c’est le seul nombre qui divise tous les autres. Les nombres premiers ont une propriété moins forte : tout nombre 2 est divisible par un nombre premier.

Exemples.

a. Les premiers nombres premiers sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, etc. Il y a une infinité de nombre premiers, comme on le verra dans le corollaire 2.

b. L’un des nombres premiers les plus grands est 2^{43112609} 1 (c’est un nombre premier de Mersenne, c’est-à-dire un nombre premier de la forme 2^{}1).

Propriétés de divisibilité des nombres premiers 2

Lemme de Gauss

Un nombre 2 est premier si et seulement si ou .

Lemme 1

Démonstration. Soit 2 vérifiant  ou  . Si divise , alors on peut
écrire  et donc  ou  . Dans le premier cas,  , et dans le second, 1, ce

qui montre que les seuls diviseurs de sont 1 et . Réciproquement, considérons un nombre premier et supposons que . Le pgcd de et est soit 1 soit ; si ce n’est pas , alors on peut écrire 1 et donc

c’est-à-dire que divise vu que  .  □

Décomposition en facteurs premiers 3

3 1 Théorème fondamental

Théorème fondamental de l’arithmétique

Tout nombre premier 2 s’écrit comme produit de nombres premiers.

Théorème 1

Démonstration. Pour l’existence, on procède par récurrence. Si 2, c’est évident car est premier. Si 3 n’est pas premier, alors on peut l’écrire sous la forme avec 1 et 1 . Par hypothèse de récurrence, et sont des produits de nombres premiers et donc il en est de même de . Montrons l’unicité en utilisant le lemme de Gauss (lemme 1). Si _{1} _{}_{1} _{}avec les _{}et les _{}premiers, alors, puisque _{1} _{1} _{}, _{1} divise un des _{}, disons _{1} (quitte à ré-indexer les _{}si nécessaire) ; ces deux nombres étant premiers, on en déduit que _{1}

1 et donc on obtient _{2}  _{}_{2}  _{}. Le même raisonnement fournit _{2} _{2} (quitte à
réindexer les _{}au besoin), etc. Finalement,  et _{}_{}pour tout .  □

Tout entier 2 s’écrit donc de manière unique sous la forme ^{_{1}} _{}^{_{}}avec les _{}des nombres premiers distincts et les _{}des entiers 1.

Exemples.

a. 24 2^{3} 3 b. 255 3 5 17 c. 663 7 13 17

3 2 Conséquences

Soit 2 qu’on écrit sous la forme  ^{_{1}}  _{}^{_{}}avec les _{}des nombres premiers deux

à deux distincts. On pose _{_{}}( ) _{}et _{}( ) 0 si n’est pas l’un des _{}. Ceci permet d’écrire

_{premier} ^{_{}( )}

Calcul du pgcd

pgcd( ) _{premier} ^{min( _{}( ) _{}( ))}

Corollaire 1

Exemple. Le pgcd de 24 2^{3} 3 et 306 2 3^{2} 17 est 2^{1} 3^{1} 17^{0} 6.

Calcul du ppcm

ppcm( ) _{premier} ^{max( _{}( ) _{}( ))}

Corollaire 2

Exemple. Le ppcm de 24 2^{3} 3 et 306 2 3^{2} 17 est 2^{3} 3^{2} 17^{1} 1224.

Quelques propriétés de l’ensemble des nombres premiers 4

Théorème d’Euclide

Il existe une infinité de nombre premiers.

Théorème 2

Démonstration. Considérons un ensemble fini _{1} _{}de nombre premiers et posons 1 _{}1. Le nombre est 2 donc est divisible au moins par un nombre premier , mais ce nombre premier ne peut être l’un des _{}car aucun des _{}ne divise (dans le cas contraire, ce _{}diviserait 1). Ceci montre qu’à chaque fois qu’on a un nombre fini de nombres premiers, on peut en construire un autre ; c’est le résultat voulu. □

Exercices et problèmes

Nombres premiers

Pour les deux exercices suivants, dire si les nombres donnés sont premiers.

1 353 ; 457 ; 101 ; 89 ; 113.

2 1453 ; 1267 ; 7651 ; 1789.

3 Les nombres 1, 11, 111, 1111, 11111, 111111 sontils premiers ?

4 Écrire la liste des nombres premiers compris entre 100 et 200.

Décompositions en facteurs premiers

Pour les deux exercices suivants, trouver la décomposition en facteurs premiers des nombres donnés. En déduire l’ensemble des diviseurs de chacun des nombres

5 567 ; 546 ; 897 ; 564 ; 890.

6 4637 ; 3560 ; 9884 ; 2010.

7 ^{⋆} On pose 900 0. Combien faut-il de zéros pour que admette 108 diviseurs (positifs) ?

8 Comment reconnaît-on sur la décomposition en facteurs premiers de que est un carré ?

9 On pose _{0} 2 et _{1} 1 _{premier} ^{_{}( _{})} .

a. Où a-t-on déjà rencontré cette suite ?

b. Calculer _{1}, _{2}, _{3}, _{4}, _{5}.

10 a. Montrer que si et sont deux nombres premiers entre eux tels que est un carré, alors et sont des carrés ?

b. Le résultat précédent reste-t-il valable pour des puissances -ièmes avec 2 ?

Pgcd et ppcm

11 Pour chacun des couples suivants, trouver leur pgcd et leur ppcm en utilisant la décomposition en facteurs premiers.

(1236 764) ; (784 8760) ; (765 875)

Ensemble des nombres premiers

12 Démontrer que la suite (( 2)! )_{2 1} est une suite de nombres tous non premiers.

13 ^{⋆} Montrer qu’il existe une infinité de nombre premiers de la forme 4 1.

14 ^{⋆}^{⋆} Montrer qu’il existe une infinité de nombre premiers de la forme 4 1.

Exercices de recherche

15 ^{⋆}^{⋆}^{⋆} Montrer que si est premier et si est premier à , alors ^{1} 1 est divisible par .

16 ^{⋆}^{⋆} Soit un nombre tel que, pour tout premier à , le nombre ^{1} 1 est divisible par . Est-ce que est premier ?

17 ^{⋆}^{⋆}^{⋆} Montrer que est premier si et seulement si ( 1)! 1 est divisible par .