Arithmétique dans PGCD et PPCM

Nous utiliserons la notion d’idéal (fon-damentale en arithmétique) pour cons-truire le PGCD et le PPCM de deux polynômes. Autrefois, en terminale C c’est de la même façon qu’on construisait ces deux notions avec les entiers relatifs (qui sera d’ailleurs reprise en licence 2).

xIntroductionx Quand on fait de l’arithmétique (et pas forcément dans ), il y a deux notions fondamentales : le PGCD et le PPCM. Ces deux objets mathématiques sont très techniques à construire dans le cadre des entiers relatifs et l’est encore plus avec les polynômes (chapitre 15). Nous étudierons d’abord le PGCD et le PPCM de deux entiers relatifs avant de traiter le cas général avec un nombre fini d’entiers relatifs.

xPrérequisx

• Arithmétique dans : divisibilité et congruences (chapitre 9)

xObjectifs du chapitrex

• Démontrer les propriétés liées à l’ensemble des diviseurs d’un entier relatif • Définir le PGCD d’entiers relatifs • Démontrer les propriétés du PGCD • Mise en place de l’algorithme d’Euclide • Introduire la notion de nombres premiers entre eux (dans leur ensemble et deux à deux) • Démontrer le théorème de Bézout (algorithme d'Euclide étendu) • Démontrer le théorème de Gauss • Démontrer un critère de divisibilité par 7 • Etudier les éléments inversibles de n ( 1n ) • Définir le PPCM d’entiers relatifs • Démontrer les propriétés du PPCM • Démontrer la relation PGCD-PPCM

Arithmétique dans : PGCD et PPCM

Compte tenu du théorème 4 du cha-pitre 9, l’ensemble des diviseurs d’un entier relatif est un ensemble fini.

On rappelle que tous les entiers relatifs divise 0.

En effet, quand a est négatif on a :

{ , | } { , | }a k k a k k a

a .

Preuve par double-inclusion.

Le théorème 3 est une conséquence du théorème 2. Attention, dans ce cas on a nécessaire-ment r b .

x1x PGCD de deux entiers relatifs xAx Diviseurs d’un entier relatif Quel que soit l’entier relatif n, on note n l’ensemble des diviseurs de n et n

l’ensemble des diviseurs positifs de n.

Il est alors clair que pour tout entier relatif n : { , | }n k k n et n n

.

Par exemple, 6 { 6, 1, 2, 3, 1, 2, 3, 6} et 6 {1, 2, 3, 6} .

Théorème 1

Soient a et b deux entiers relatifs. 1) 0a a 2) 1 { 1, 1}a 3) a a 4) | a b bb a .

Preuve 1) 0a a a (car a ).

2) Il est clair que 1 { 1, 1} et que 1 a , d’où 1 { 1, 1}a .

3) C’est une conséquence directe du théorème 2 du chapitre 9. 4) Supposons que |b a . Alors b a , en effet, si d désigne un élément de b , alors |d b . Comme par hypothèse |b a , il vient que |d a .

Par suite, a b b .

Théorème 2

2( , ) , , a b a kb ba b k .

Preuve - Soit d un élément de a b .

Alors d est un diviseur à la fois de a et de b. Il vient (théorème 7 du chapitre 2), que d divise a kb et donc a kbd .

Ainsi, comme bd , a b a kb b .

- Soit d un élément de a kb b .

Alors d est un diviseur à la fois de a kb et de b. Il vient (théorème 7 du chapitre 2), que d divise ( )a kb kb , c’est-à-dire a, et donc ad .

Ainsi, comme bd , a kb b a b .

Finalement, a b a kb b .

Remarque En choisissant 1k dans le théorème 2, on a en particulier a b a b b .

Théorème 3

Soient a et b deux entiers relatifs avec b non nul. En désignant par r le reste de la division euclidienne de a par b, on a a b r b .

Preuve Comme r est le reste de la division euclidienne de a par b, il existe un entier relatif q tel que a bq r . Donc r a bq et alors r b a bq b .

D’après le théorème 2, il vient que r b a b .

xBx PGCD de deux entiers relatifs La notion de PGCD est connue du lecteur depuis la classe de troisième. Mais ni son existence, ni son unicité n’ont été justifiées. C’est ce que nous allons faire dans ce paragraphe.

Le cours du chapitre 10

Le théorème 4 est très important.

En effet, on sait que 1 (et -1) divise tous les entiers relatifs.

L’entier b n’est pas nul car a et b ne doivent pas être nul en même temps. Le lecteur sera ravi de montrer que quel que soit l’entier relatif d :

d d .

Soyons très précis, il s’agit du plus grand diviseur commun au sens de la relation d’ordre usuelle dans . Nous verrons que ce plus grand élé-ment coïncide avec la relation d’ordre « divise » dans .

Selon la définition 1, le PGCD de 0 et de 0 désignerait le plus grand élé-ment de . Un tel élément n’existant pas, nous convenons à la convention ci-contre.

Autrement dit, un diviseur commun de a et b est inférieur ou égal au PGCD de a et b. Si bien que nous pouvons toujours nous ramener à des entiers naturels pour la détermination du PGCD. Il est inutile de considérer les diviseurs négatifs (voir la troisième remarque précédente).

Le théorème 5 est très important pour toute la suite du cours.

Rappel de notation :

2{ , ( , ) ,a b x u v }x au bv . Ainsi, si a et b sont nuls, la relation ci-contre devient claire.

Utilisation du théorème 7 du cha-pitre 9.

Théorème 4

Soient a et b deux entiers relatifs non simultanément nuls. L’ensemble a b admet un plus grand élément.

Preuve - L’ensemble a b est par définition une partie de .

- L’ensemble a b n’est pas vide car il contient 1 (on peut aussi dire -1).

- Il reste à montrer que cet ensemble est majoré. Soit d un élément de a b .

Supposons que a est nul. Alors b n’est pas nul et donc 0a b b b .

Ainsi, d est un diviseur de b et donc (via le théorème 4 du chapitre 9) d b . Supposons que b est nul. Alors a n’est pas nul et donc 0a b a a .

Ainsi, d est un diviseur de a et donc d a . En résumé max(d a b . Supposons enfin que a et b sont non nuls. Comme a bd , on a d a et d b , d’où min(d a b .

Dans tous les cas, l’ensemble a b est majoré.

Finalement, l’ensemble a b est une partie non vide de et majoré : il admet un plus grand élément.

Définition 1

Soient a et b deux entiers relatifs non simultanément nuls. Le plus grand élément de l’ensemble a b est appelé le plus grand diviseur commun de a et b.

Remarque 1. Le plus grand diviseur commun de a et b est noté PGCD( , )a b mais il est parfois commode de le noter a b . 2. On se permet d’étendre la définition 1 en posant PGCD(0, 0) 0 . 3. Il est clair que PGCD( , ) 1a b . 4. Par définition, en notant a b , il est clair que :

|,

|k a

k kk b

.

5. En vertu du théorème 1-3, il est aussi clair que PGCD( , ) PGCD( , )a b a b . Exemple Déterminons le PGCD des nombres 12 et 30. On a 12 {1, 2, 3, 4, 6, 12} et 30 {1, 2, 3, 5, 6, 10, 15, 30} .

Donc 12 30 {1, 2, 3, 6} et alors PGCD(12, 30) 6 .

xCx Propriétés du PGCD Les propriétés du PGCD sont nombreuses. C’est le théorème suivant qui va les justifier. On rappelle que si a désigne un entier relatif, alors a désigne l’ensemble de ses multiples.

Théorème 5 Soient a et b deux entiers relatifs et leur PGCD.

a b . Preuve Soit x un élément de a b .

Par définition, il existe un couple 2( , )u v tel que x au bv . Comme est un diviseur commun des entiers a et b ( a b ), on a |au bv , c’est à dire | x .


Relation fondamentale du PGCD de deux entiers relatifs

Cette partie de la démonstration est très délicate.

Le cas où a et b sont nuls est exclu (la relation devient évidente). On est par conséquent sûr que l’un des entiers a ou b n’est pas nul. Ici, on a choisi a et il n’y a pas perte de généralité.

N’oubliez pas : d .

On va montrer que a b d .

Faire l’exercice 2 pour montrer que l’ensemble a b est un sous-groupe de . Raisonnement par l’absurde.

Voir l’exercice 1.

L’égalité 1) traduit la commutativité du PGCD. Pour finir les preuves, le lecteur pourra prouver à titre d’exercice :

2( , ) ,a b a b a b . On pourra aussi voir l’exercice 3.

On utilise le fait que a a a qui est immédiat justifier.

Le théorème 7 traduit l’homogénéité du PGCD. Attention à ne pas oublier la valeur ab-solue au second membre de l’égalité.

Bien entendu, désigne de PGCD de a et b.

Le théorème 8 explique que le PGCD des entiers a et b est le plus grand di-viseur de a et b au sens de la relation « divise » (qui jusqu’ici était au sens de la relation d’ordre usuelle).

Utilisation de l’exercice 9 du cha-pitre 4.

Il vient alors que x d’où a b . Pour démontrer l’inclusion réciproque, il nous faut passer par autre chose. On va montrer que l’ensemble ( )a b admet un plus petit élément. - C’est évidemment par construction une partie de .

- Il n’est pas vide car si a est strictement positif, alors clairement ( )a a b (prendre 1u et 0v ) et si

a est strictement négatif, alors comme a a b (prendre 1u et 0v ) ( )a a b .

L’ensemble ( )a b admet ainsi un plus petit élément qu’on notera d. Comme d a b , on a d a b . En effet, considérons y d . Alors |d y et il existe un entier relatif e tel que y de .

Par ailleurs, comme d a b , il existe un couple 2( , )u v tel que d au bv . Par conséquent, ( ) ( )y de a eu b ev et donc y a b : c’est l’inclusion recherchée. Effectuons la division euclidienne de x par d. Il existe un couple 2( , )q r tel que x dq r et 0 r d . Comme x et d sont dans a b , on a dq a b (puisque d a b ) et alors x dq a b , soit r a b .

Si 0r , alors ( )r a b , ce qui est absurde puisque min(( ) )r d a b . Donc r est nul et alors x dq , d’où x d . Ainsi, on a montré que a b d et donc a b d . Enfin, comme d (puisque a b ), divise d donc d . Comme d divise a et b (car a b d et ,a b a b ), on a par définition de , d , d’où d . Bilan : d et donc a b . Nous sommes maintenant amenés à démontrer les propriétés du PGCD.

Théorème 6 Soient a et b deux entiers relatifs.

1) PGCD( , ) PGCD( , )a b b a 2) PGCD( , 0)a a 3) PGCD( , 1) 1a 4) | PGCD( , )a b a b a .

Preuve 1) On a : ( ) ( )a b a b b a b a , ce qui permet de conclure. 2) On a : 0 ( 0)a a a , ce qui permet de conclure. 3) Il est clair que a , donc ( 1)a . 4) Supposons que |a b . Alors b a et donc (en vertu de l’exercice 9 du chapitre 4) b a a . De plus, l’inclusion a b a étant claire, on obtient a b a d’où ( )a b b .

Théorème 7 2( , ) , , PGCD( , ) PGCD( , )a b k a b a b .

Preuve On a immédiatement : ( ) ( ) ( )a b a b . Ainsi PGCD( , )a b .

Théorème 8 Soient a et b deux entiers relatifs et leur PGCD.

|, |

|k a

k kk b

.

Preuve

On dispose des équivalences suivantes : |

||

k a a ka b k k k

k b b k

.


Homogénéité du PGCD

Le théorème 9 traduit l’associativité du PGCD. Il est plus commode de citer le théo-rème avec la notation « ».

Euclide d’Alexandrie (~300 av JC) était un mathématicien grec.

C’est une conséquence immédiate du théorème 3.

On remarque alors que le PGCD de a et b est le dernier reste non nul dans les divisions euclidiennes.

On a : 0 1 2 ...r r r .

Une suite décroissante d’entiers natu-rels ne « stationne pas » nécessaire-ment en 0.

Remarque Une conséquence immédiate du théorème 8 et que les diviseurs du PGCD de a et b sont exactement les diviseurs commun de a et b et ainsi :

a b .

Théorème 9

3( , , ) , ( ) ( )a b c a b c a b c .

Preuve En utilisant l’associativité de l’addition dans ( ) , on a : ( ) ( )a b c a b c . Remarques 1. D’après le théorème 9 on pourra écrire a b c au lieu de ( )a b c (ou ( )a b c ). 2. Le couple ( , ) est un demi-groupe commutatif. xDx Algorithme d’Euclide Jusqu’ici, pour déterminer le PGCD de deux entiers relatifs on dressait la liste de leurs diviseurs positifs commun et on prenait le plus grand de cette liste. Cette méthode a bien sûr ses limites. L’algorithme d’Euclide permet de déterminer rapidement le PGCD de deux entiers relatifs. Limitons-nous aux entiers naturels et choisissons deux entiers naturels a et b avec 0 b a . - Si b divise a, on sait déjà que a b b . - Supposons alors que b ne divise par a. Effectuons la division euclidienne de a par b. Il existe un couple 2

0 0( , )q r tel que 0 0a bq r et 00 r b .

Il est clair que 0a b b r . Deux cas sont alors à traiter :

- ou bien 0 0r et dans ce cas 0a b b b ;

- ou bien 0 0r et on effectue à nouveau la division euclidienne de b par 0r .

On obtient alors un couple 21 1( , )q r tel que 0 1 1b r q r avec 1 00 r r .

Il est alors clair que 0 0 1a b b r r r . Deux cas sont alors à traiter :

- ou bien 1 0r et dans ce cas 0 0 00a b b r r r ;

- ou bien 1 0r et on effectue à nouveau la division euclidienne de 0r par 1r .

On construit alors des couples 0 0( , )q r , 1 1( , )q r ... tels que :

0 0

00a bq r

r b

, 0 1 1

1 00b r q r

r r

...

Considérons la suite r des restes définis sur . Que peut-on dire de cette suite ? Supposons qu’aucun des termes de cette suite s’annule. On aurait alors une suite strictement décroissante d’entiers naturels. Comme vous le savez, une telle suite n’existe pas. Mais une suite décroissante d’entiers naturels est station-naire (théorème 36 du chapitre 7). Ainsi, puisque qu’il existe au moins un terme nul de cette suite, cette dernière finit par « stationner en 0 », autrement dit, l’algorithme d’Euclide prend fin à partir d’un moment. Il existe alors un entier naturel N tel que :

0 0

00a bq r

r b

, 0 1 1

1 00b r q r

r r

... 2 1

10N N N N

N N

r r q rr r

, 0Nr et 1 0Nr .

Donc 0 1 2 1 1... N N N N Na b b r r r r r r r r qui correspond au dernier reste non nul.

Exemple Déterminons le PGCD des entiers 455 et 312. 455 312 1 143 . 312 143 2 26 . 143 26 5 13 . 26 2 13 0 .


Associativité du PGCD

Attention à ne pas confondre avec la notion de nombre premier (étudiée dans le chapitre 13).

Une méthode pour montrer que deux entiers relatifs a et b sont premiers entre eux consiste à montrer que tout diviseur commun à a et à b vaut néces-sairement -1 ou 1. Cette méthode est mise en œuvre dans la démonstration du théorème 11.

Pour plus de souplesse dans les théo-rèmes qui suivent, nous avons noté le PGCD de a et b.

Toute paire d’entiers relatifs premiers entre eux convient.

On se sert du fait que le PGCD est ho-mogène.

Autrement dit, si a et b sont premiers entre eux, alors a est premier avec tout diviseur de b.

Claude-Gaspard Bachet de Mézi-riac (1581-1638) était un mathémati-cien français. Le théorème 12 est le plus important de ce chapitre. Il fournit une caracté-ristique de la définition 2. De nombreux résultat vont se déduire de ce théorème.

Le dernier reste non nul étant 13, on a PGCD(455, 312) 13 . Remarque En 1844, le mathématicien Gabriel Lamé (1795-1870) montre que le nombre d’étapes dans l’algorithme d’Euclide est majoré par cinq fois le nombre de chiffres du plus grand des deux entiers choisis. Pour l’exemple ci-dessus, le nombre d’étapes est majoré par 15 mais il est en pratique inférieur à la moitié, soit 7 étapes (ici 4 étapes ont suffi). x2x Nombres premiers entre eux xAx Généralités

Définition 2 Soient a et b deux entiers relatifs. Dire que les entiers a et b sont premiers entre eux signifie que leur PGCD est égal à 1.

Exemples 1. Les entiers 3 et 7 sont premiers entre eux. 2. Les entiers 10 et 14 ne sont pas premiers entre eux car 2 est un diviseur commun de ces entiers.

Théorème 10

2 2 ,( , ) , ( , ) ,

1a a b b

a b a ba b

.

Preuve Si a et b sont nuls, le résultat est évident. On suppose désormais que ( , ) (0, 0)a b . L’existence d’entiers relatifs a’ et b’ tels que a a et b b est évidente puisque est un diviseur de a et b. Il faut en revanche vérifier la dernière condition. On a : PGCD( , ) PGCD( , ) PGCD( , )a b a b a b . Par régularité de la multiplication dans (vu que 1 ), il vient que 1a b .

Théorème 11

3 1( , , ) , 1

|a b

a b c a cc b

.

Preuve Supposons que 1a b et |c b . Considérons un diviseur positif d de a et c. Par définition de d, on a |d a et |d c . Comme par hypothèse |c b , on a |d b , et donc 1d (puisque a et b sont premiers entre eux). Ainsi, les entiers a et c sont premiers entre eux. Exemple 17 et 15 sont premiers entre eux. Donc 17 est premier avec tout diviseur de 15 comme 5. Remarque La réciproque du théorème 11 est évidemment fausse. xBx Théorème de Bézout

Théorème 12 2 2( , ) , 1 ( , ) , 1a b a b u v au bv .

Preuve ( ) Supposons que les entiers a et b soient premiers entre eux.


Théorème de Bézout

On rappelle que désigne le PGCD de a et b. Le théorème 13 permet d’obtenir des coefficients u et v « assez petits ».

Attention ! La deuxième inégalité est large contrairement à la première. Il est tout de même possible de la rendre strict mais c’est plus délicat à justifier.

Le couple (a,b) peut être remplacé par le couple (-a,-b) pour que b soit positif puisque :

( )( ) ( )( )au bv a u b v .

Johann Carl Friedrich Gauss (1777-1855) était un mathématicien al-lemand. Le théorème de Gauss est très im-portant pour la suite du cours.

On a alors a b .

Mais 1 et donc il existe un couple 2( , )u v tel que 1au bv .

( ) Supposons qu’il existe un couple 2( , )u v tel que 1au bv . On sait que a b . Puis, comme 1 a b , 1 , donc divise 1 et alors 1 . Remarque Si a et b désignent des nombres relatifs non nuls, l’équation d’inconnue ( , )x y : 1ax by admet des solutions dans

2 si et seulement si 1a b .

Théorème 13

2 2 1( , ) ( ) , 1 ( , ) ,

au bva b a b u v

u b v a

.

Preuve Supposons que 1a b . Compte tenu de ce qu’on doit obtenir, il est raisonnable de supposer 0b (pour la division euclidienne par b).

D’après le théorème de Bézout, il existe un couple 2( , )u v tel que 1au bv .

En effectuant la division euclidienne de u’ par b, il existe un couple 2( , )q u tel que u bq u et 0 u b . La condition u b est alors remplie. Puis, en notant v aq v , on a ( ) ( ) 1au bv a u bq b aq v au abq abq bv au bv . De plus, comme 1au bv , 1 1 1bv au a u a b et donc v b a b , soit v a . Remarque La réciproque du théorème 13 est évidemment vraie : qui peut le plus peu le moins ! xCx Algorithme d’Euclide étendu Soient un couple ( , )a b tel que 1a b . On va élaborer un algorithme, appelé algorithme d’Euclide étendu permettant de déterminer un couple d’entiers relatifs ( , )u v tel que 1au bv . D’après l’algorithme d’Euclide, il existe un entier naturel N et des entiers 0 0 1 1, , ..., , , ,N N N Nq r q r q r tels que :

0 0

00a bq r

r b

, 0 1 1

1 00b r q r

r r

... 2 1

10N N N N

N N

r r q rr r

, 0Nr , 1 0Nr .

Donc, puisque 1Nr , 2 1 1N N Nr r q .

Puis, 3 2 1 1N N N Nr r q r , donc 1 3 2 1N N N Nr r r q , d’où 2 3 2 1( ) 1.N N N N Nr r r q q

On remonte ainsi les divisions euclidiennes jusqu’à atteindre les entiers a et b. Exemple Cherchons un couple 2( , )u v tel que 412 11 1u v . - On prend le réflexe de regarder si 412 et 11 sont bien premiers entre eux : c’est bien le cas car 11 n’est pas un divi-seur de 412 et que 11 { 11, 1, 1, 11} .

- On applique l’algorithme d’Euclide au couple (412,11) : 412 11 37 5 ; 11 5 2 1 et 2 1 2 0 . - On forme un couple d’entier relatif (u,v) tel que 412 11 1u v : 1 11 5 2 11 (412 11 37) 2 11 (412 2 11 74) 412 ( 2) 11 75 . Ainsi le couple ( 2, 75) convient. xDx Théorème de Gauss

Théorème 14

3 |( , , ) , |

1a bc

a b c a ca b

.


Théorème de Gauss

On laisse le soin au lecteur de vérifier que si l’un des trois entiers a, b et c est nul, l’implication reste toujours vraie. Utilisation du théorème 7 du cha-pitre 9.

Autrement dit, un entier est premier avec un produit si et seulement s’il est premier avec chacun des facteurs du produit.

Multiplication membre à membre.

Le théorème 16 est très utile en pra-tique. Attention à ne pas oublier que a et b doivent être premiers entre eux !

Autrement dit, N est divisible par 7 si et seulement si la différence entre son nombre de dizaines et le double du chiffre des unités est divisible par 7.

Preuve Supposons que |a bc et 1a b .

D’après le théorème de Bézout, il existe un couple 2( , )u v tel que 1au bv . Donc acu bcv c . Puis, comme a divise bc et lui-même, il divise acu bcv , c’est-à-dire c. xEx Conséquences du théorème de Bézout et de Gauss Les conséquences de ces deux théorèmes sont nombreuses et très pratiques. Vous devez les connaître.

Théorème 15

3 1( , , ) , ( )

1a b

a b c a bca c

.

Preuve Naturellement, on écarte les cas où l’un des entiers a, b et c est nul. ( ) Supposons que 1a b et 1a c . Il existe alors des entiers relatifs , , ,u v u v tels que 1au bv et 1au cv .

Donc ( )( ) 1au bv au cv , soit 2 1a uu acuv abu v bcvv , soit ( ) ( )( ) 1a auu cuv bu v bc vv . Puisque auu cuv bu v et vv , on conclut que ( ) 1a bc . ( ) Réciproquement, supposons que ( )a bc . Comme |b bc et |c bc , il vient que (théorème 11) a b et 1a c .

Théorème 16

3 1( , , ) , |

| , |a b

a b c ab ca c b c

.

Preuve Naturellement, on écarte les cas où l’un des entiers a, b et c est nul. Supposons à présent que 1a b , |a c et |b c . Comme |a c , il existe un entier relatif k tel que c ak . Donc |b ak et comme 1a b , on d’après le théorème de Gauss, |b k . Il existe donc à nouveau un entier relatif l tel que k bl . Ainsi, ( ) ( )c a bl ab l et alors |ab c . Remarque La réciproque du théorème 16 est fausse mais si la condition « 1a b » est supprimée, elle devient vraie. xFx Application des théorèmes de Bézout et de Gauss Application 1 : critère de divisibilité Nous avons démontré dans le chapitre précédent les critères de divisibilité de 2, 3, 4, 5, 8, 9, 10 et 11. Nous allons à présent démontrer un critère de divisibilité par 7. Rappelons le théorème des systèmes de numération appliquer à la base 10 :

20 1 2

10 0

10 10 ... 10, , !( , ..., ) , 0 , ...,

0

nn

nn n

n

a a a a aa n a a a a n

a

.

Pour toute la suite, on notera 0

10n

kk

k

N a

. L’entier N s’écrit alors 1 0...na a a où nous avons omis la base 10 car il

n’y aura pas d’ambiguïté.

Théorème 17 L’entier N est divisible par 7 si et seulement si 1 07 | ... 2na a a .


Critère de divisibilité par 7

Remarquez que 7 ( 7) 10 5 1 .

Utilisation du théorème 5 du cha-pitre 9.

Autrement dit, les éléments inversibles de n sont les éléments x tel que

1x n .

On va montrer que tout représentant de x est premier avec n.

Dans n , 0n .

On rappelle que pour un anneau A, la notation A désigne l’ensemble des éléments inversibles de A.

( ) Supposons que N est divisible par 7.

Comme 7 | 21 , alors (théorème 7 du chapitre 9) 00

7 | 10 21n

kk

k

a a

.

Or, 10 0 0 0 0

0 1 1 1

10 21 10 21 10 20 10 10 2n n n n

k k k kk k k k

k k k k

a a a a a a a a a

.

Donc 10

1

7 | 10 10 2n

kk

k

a a

.

L’entier 7 étant premier avec 10, on a d’après le théorème de Gauss 10

1

7 | 10 2n

kk

k

a a

.

Ainsi, 1 07 | ... 2na a a .

( ) Supposons que 1 07 | ... 2na a a .

Alors 1 07 | 10( ... 2 )na a a soit 10

1

7 | 10 10 2n

kk

k

a a

, soit encore 0

1

7 | 10 20n

kk

k

a a

.

Mais 7 divise 21, d’où 7 divise 021a et alors 0 01

7 | 10 20 21n

kk

k

a a a

, soit 01

7 | 10n

kk

k

a a

, soit 0

7 | 10n

kk

k

a .

Ainsi N est divisible par 7. Exemple Le nombre 868 est-il divisible par 7 ? On a : 86 2 8 86 16 70 7 10 . Réponse : oui. Application 2 : éléments inversibles dans Z/nZ Le théorème suivant est très important :

Théorème 18 Soit n un entier naturel non nul. Les éléments inversibles de n sont ceux dont les représentants sont premiers avec n.

Preuve On considère l’anneau ( , , )n .

- Soit x un élément inversible de n (il existe alors un entier relatif a tel que x a ).

Il existe alors un élément y (il existe aussi un entier relatif b tel que y b ) de n tel que 1xy .

L’égalité 1xy est équivalente à l’égalité 1a b ab , c’est-à-dire 1 [ ]ab n , soit | 1n ab . Il existe donc un entier relatif k tel que 1ab nk et alors ( ) 1ab n k . D’après le théorème de Bézout, a et n sont premiers entre eux. - Réciproquement, soit x un élément de n (il existe alors un entier relatif a tel que x a ). Supposons que a et n sont premiers entre eux. D’après le théorème de Bézout, il existe deux entiers relatifs u et v tels que 1au nv . Donc 1au nv au nv a u n v x u . Ce qui prouve que x est inversible dans n . Exemple ( 8 ) {1, 3, 5, 7} . x3x PGCD de plusieurs entiers relatifs Nous allons généraliser la théorie du PGCD avec un nombre fini d’entiers relatifs. Les preuves seront plus succinctes. Reportez-vous aux cas avec deux entiers relatifs si certaines preuves vous semblent difficiles à comprendre.


Les entiers x1,...,xn ne doivent pas être tous nuls.

En réalité, seul le premier cas suffit puisqu’il est clair que :

1 1min( max(n nx x x x .

Il s’agit du plus grand diviseur com-mun pour l’ordre usuel.


xAx Définition Commençons par une constatation :

Théorème 19

Soient n et 1( , ..., ) \ {(0, ..., 0)}nnx x .

L’ensemble des diviseurs communs à 1, ..., nx x admet un plus grand élément.

Preuve Notons l’ensemble des diviseurs communs à 1, ..., nx x .

- L’ensemble est une partie de . - L’ensemble n’est pas vide puisqu’il contient 1. - L’ensemble est majoré par :

1max( nx x si l’un au moins des entiers est nul ;

sinon il est majoré par 1min( nx x si aucun des entiers est nul.

Ainsi l’ensemble admet un plus grand élément.

Définition 3

Soient n et 1( , ..., ) \ {(0, ..., 0)}nnx x .

Le plus grand élément de l’ensemble des diviseurs communs à 1, ..., nx x est appelé le plus grand diviseur commun

de 1, ..., nx x .

Remarque 1. Le plus grand diviseur commun de 1, ..., nx x est noté 1PGCD( , ..., )nx x où encore 1PGCD(( ) )i i nx . Parfois, on pourra pour plus de commodité employer la notation pour le PGCD de 1, ..., nx x . 2. On se permet d’étendre la définition 3 en posant PGCD(0, ..., 0) 0 . 3. Il est clair que 1PGCD( , ..., ) 1nx x (quand les entiers 1, ..., nx x ne sont pas tous nuls).

4. Par définition, en notant 1PGCD( , ..., )nx x , il est clair que :

, ( {1, ..., }, | )ik i n k x k .

5. En vertu du théorème 1-3, il est clair que 1 1PGCD( , ..., ) PGCD( , ..., )n nx x x x .

Exemple PGCD(10, 16, 20) 2 . xBx Propriétés du PGCD

Théorème 20 Soient n un entier naturel non nul, 1, ..., nx x des entiers relatifs et leur PGCD.

1

n

ii

x

.

Preuve

Soit x un élément de 1

n

ii

x .

Il existe alors un n-uplet 1( , ..., ) nnu u tel que

1

n

i ii

x x u

.

Comme pour tout i de {1, ..., }n on a | ix , il vient que | x et alors x .

On obtient l’inclusion 1

n

ii

x

.

Il reste à établir l’inclusion réciproque qui n’est pas simple.


Relation fondamentale du PGCD de plusieurs entiers relatifs

Raisonnement par l’absurde.

Le théorème 21 traduit l’homogé-néité du PGCD. Attention à ne pas oublier la valeur ab-solue au second membre de l’égalité.

Ainsi, le PGCD des entiers x1,...,xn cor-respond au plus grand élément (au sens de la relation « divise ») des diviseurs communs de ces entiers.

Comparer la définition 4 avec la dé-finition 5.

L’ensemble 1

n

ii

x

est une partie de et non vide (il contient 1x ) : il contient un plus petit élément qu’on

notera d.

Puisque 1

n

ii

d x

, on a 1

n

ii

d x

.

Effectuons la division euclidienne de x par d. Il existe un couple 2( , )q r tel que x dq r et 0 r d .

L’ensemble 1

n

ii

x étant un sous-groupe de avec

1

n

ii

x x

et 1

n

ii

d x

, on a 1

n

ii

r x

.

Supposons que 0r .

Alors 1

n

ii

r x

, ce qui est absurde puisque

1

minn

ii

r d x

.

Donc r est nul et alors x dq d .

L’inclusion 1

n

ii

x d

est donc établie.

Ainsi 1

n

ii

x d

(et donc d ).

La dernière inclusion entraîne que |d , soit d . Puis, comme d divise chacun des entiers 1, ..., nx x , il vient que d , d’où d .

Finalement, 1

n

ii

x

.

Théorème 21

1 1 1, ( , ..., ) , , PGCD( , ..., ) PGCD( , ..., )nn n nn x x k kx kx k x x

Preuve

En notant 1PGCD( , ..., )nx x , on a 1 1

( ) ( ) ( )n n

i ii i

kx k x k k

.

Donc 1PGCD( , ..., )nkx kx k k .

Théorème 22 Soient n un entier naturel non nul, 1, ..., nx x des entiers relatifs et leur PGCD.

, ( {1, ..., }, | ) |ik i n k x k .

Preuve

On dispose des équivalences suivantes :1

{1, ..., }, | {1, ..., },n

i i ii

i n k x i n x k x k k

|k . x4x Nombres premiers entre eux : cas général xAx Généralités Avec trois entiers ou plus, une subtilité existe avec la notion de nombres premiers entre eux.

Définition 4

Soient n et 1( , ..., ) nnx x .

Dire que les entiers 1, ..., nx x sont premiers entre eux dans leur ensemble signifie que 1PGCD( , ..., ) 1nx x .


Homogénéité du PGCD

Puisque 2 est un diviseur commun des trois entiers.

En réalité, ce n’est pas si simple à jus-tifier rigoureusement. Il nous faudrait pour cela énoncer l’associativité du PGCD dans le cadre général mais ce théorème est admis (il a été simple-ment vu dans le cas de trois entiers).

Utilisation de la négation :

2( , ) {1, ..., } ,1i j

i ji j n

x x

.

Ici, désigne de PGCD de x1,...,xn.

Exemples 1. Les entiers 2, 3 et 4 sont premiers entre eux dans leur ensemble. 2. Les entiers 4, 6 et 20 ne sont pas premiers entre eux dans leur ensemble.

Définition 5


Dire que les entiers 1, ..., nx x sont premiers entre eux deux à deux signifie que : 2( , ) {1, ..., } , 1i ji j n i j x x .

Exemples 1. Les entiers 2, 3 et 4 ne sont pas premiers entre eux deux à deux (il y a 2 et 4). 2. Les entiers 3, 4 et 5 sont premiers entre eux deux à deux. Remarques 1. Selon le principe de qui peut le plus, peut le moins, des nombres premiers entre eux deux à deux sont premiers entre eux dans leur ensemble. 2. Attention, ce n’est pas parce que des entiers sont premiers entre eux dans leur ensemble qui sont premiers entre eux deux à deux. En effet, par exemple, les entiers 10, 13 et 14 sont premiers entre eux dans leur ensemble mais 10 et 14 ont 2 comme diviseur commun (donc un PGCD différent de 1). 3. Deux entiers relatifs sont premiers entre eux si et seulement s’ils sont premiers entre eux dans leurs ensembles. 4. Deux entiers relatifs sont premiers entre eux si et seulement s’ils sont premiers entre eux deux à deux.

Théorème 23

1 11

{1, ..., },, ( , ..., ) , ( , ..., ) ,

... 1n n i i

n nn

i n x xn x x x x

x x

.

Preuve Si tous les entiers 1, ..., nx x sont nuls, le résultat est évident.

Supposons que 1( , ..., ) (0, ..., 0)nx x .

Puisque est un diviseur de chacun des entiers 1, ..., nx x , il existe un n-uplet 1( , ..., )nx x tel que pour tout i de

l’ensemble {1, ..., }n , i ix x .

Puis, 1 1 1PGCD( , ..., ) PGCD( , ..., ) PGCD( , ..., )n n nx x x x x x .

Ainsi, 1PGCD( , ..., ) 1nx x .

xBx Théorème de Bézout : cas général

Théorème 24


Les entiers 1, ..., nx x sont premiers entre eux dans leur ensemble si et seulement s’il existe un u-uplet 1( , ..., )nu u

d’entiers relatifs tel que :

1

1n

i ii

x u

.

Preuve ( ) Supposons que les entiers 1, ..., nx x sont premiers entre eux dans leur ensemble.

Alors 1

n

ii

x

, puis comme 1 , il existe un u-uplet 1( , ..., ) nnu u tel que

1

1n

i ii

x u

.

( ) Supposons qu’il existe un u-uplet 1( , ..., ) nnu u tel que

1

1n

i ii

x u

.


Théorème de Bézout (version 2)

Autrement dit, un entier est premier avec plusieurs entiers si et seulement s’il est premier avec leur produit.

Autrement dit, deux entiers sont pre-miers entre eux si et seulement si leurs puissances sont premiers entre eux.

Comme 1

n

ii

x

et que 1

1n

ii

x

, il vient que 1 , soit 1 .

Ainsi, 1PGCD( , ..., ) 1nx x et les entiers 1, ..., nx x sont premiers entre eux (dans leur ensemble).

xCx Conséquences du théorème de Bézout et de Gauss Voici une généralisation du théorème 15 :

Théorème 25

Soient n , 1( , ..., ) nnx x et a .

1

( {1, ..., }, 1) 1n

i ii

i n a x a x

.

Preuve ( ) Effectuons une récurrence sur n. Il est clair que l’implication est vraie quand 1n (puisque, en particulier 1 1a x ).

Soit n et supposons que pour des entiers 1 1, ..., nx x donnés, on ait :

1

( {1, ..., }, 1) 1n

i ii

i n a x a x

.

Admettons aussi que : {1, ..., 1}, 1ii n k x .

On a 1

11 1

n n

i i ni i

k x k x x

.

Ainsi, comme 1

n

ii

k x

et 1nk x , on a 1

1

1n

ii

k x

.

( ) Supposons que 1

1n

ii

k x

.

Alors d’après le théorème 11, on a immédiatement : {1, ..., }, 1ii n k x .

Le théorème précédent permet d’énoncer le théorème qui suit :

Théorème 26 2( , ) , ( , ) ( ) , 1 1n ma b n m a b a b .

Preuve ( ) Supposons que a et b sont premiers entre eux.

D’après le théorème 25, pour tout entier naturel n non nul on a 1

1n

i

a b

, soit 1na b .

En appliquant encore le théorème 25, on a pour tout couple 2( , ) ( )n m , 1

1m

n

i

b a

, soit 1m na b .

( ) Supposons que tout couple 2( , ) ( )n m , 1n ma b .

Alors d’après le théorème 25, pour tout entier naturel n non nul 1na b . Puis, toujours d’après le même théorème, 1a b . Exemple Déterminons le PGCD de 12346 et 19147 . Les entiers 7 et 46 sont premiers entre eux, donc (théorème 26) les entiers 12346 et 19147 sont premiers entre eux. Le théorème suivant est une conséquence immédiate du théorème 26 :


Utilisation du théorème 26.

Attention, on demande à ce que les en-tiers soient premiers entre eux deux à deux (et non dans leur ensemble). Autrement dit, si plusieurs entiers (qui sont premiers entre eux deux à deux) divisent un même entier, alors leur pro-duit divise cet entier.

Le théorème 29 est fondamentale. La notation ( )a b , lourde, désigne l’ensemble des multiples com-mun strictement positifs de a et b.

Il s’agit du plus petit multiple commun pour l’ordre usuel.

En particulier, PPCM(0, 0) 0 .

Autrement dit, tout multiple stricte-ment positif de a et de b est supérieur ou égal au PPCM de a et b.

Théorème 27

( , ) , , ( )n n na b n a b a b .

Preuve Notons a b . On sait qu’il existe deux entiers relatifs a et b tels que a a , b b et 1a b . Donc pour tout entier naturel n non nul, ( ) ( ) ( ) ( )n n n n n n n n n n n n n na b a b a b a b a b .

Ainsi, pour tout entier naturel n non nul, ( )n n na b a b .

Théorème 28

Soient n , 1, ..., nx x des entiers relatifs deux à deux premiers entre eux et a un entier relatif.

1

{1, ..., }, | |n

i ii

i n x a x a

.

Preuve Récurrence sur n. L’implication est claire quand 1n . Soit n et supposons que pour les entiers 1 1, ..., nx x deux à deux premiers entre eux, on ait :

1

{1, ..., }, | |n

i ii

i n x a x a

.

Supposons aussi que : {1, ..., 1}, |ii n x a .

Pour tout i de {1, ..., }n on a 1 1n ix x , d’où (théorème 25) 11

1n

n ii

x x

.

Puis, comme 1

|n

ii

x a et 1 |nx a , il vient que 1

1

n

i ni

x x

divise a, c’est-à-dire

1

1

n

ii

x

divise a.

x5x PPCM de deux entiers relatifs xAx Généralités

Théorème 29 Soient a et b deux entiers relatifs non nuls. L’ensemble ( )a b admet un plus petit élément.

Preuve L’ensemble ( )a b est une partie de qui n’est pas vide car il contient ab . Cet ensemble admet donc un plus petit élément.

Définition 6 Soient a et b deux entiers relatifs non nuls. Le plus petit élément de l’ensemble ( )a b est appelé le plus petit multiple commun de a et b.

Remarque 1. Le plus petit multiple commun de a et b est noté PPCM( , )a b mais il est parfois commode de le noter a b . 2. On se permet d’étendre la définition 6, en posant PPCM( , ) 0a b dès lors où l’un des entiers a et b est nul. 3. Il est clair que PPCM( , ) 1a b quand a et b sont non nuls. 4. Par définition, en notant a b , il est clair que :

|,

|a k

k kb k

.

5. Puisque pour tout entier relatif a on a a a , on a PPCM( , ) PPCM( , )a b a b .


Cette méthode ne semble pas efficace. D’autres méthodes comme pour le PGCD seront travaillées.

Le théorème 30 est fondamental pour toute la suite du cours.

Dans le cas contraire, la relation de-vient triviale.

L’entier m ne peut pas être nul puisque a et b ne le sont pas.

L’égalité 1) traduit la commutativité du PPCM. L’implication 4) dit en particulier que PPCM( , )a a a (puisque |a a ).

Le théorème 32 traduit l’homogé-néité du PPCM.

Bien entendu, désigne de PPCM de a et b.

Le théorème 33 explique que le PPCM des entiers a et b est le plus pe-tit multiple commun strictement posi-tif de a et b au sens de la relation « di-vise » (qui jusqu’ici était au sens de la relation d’ordre usuelle).

Exemple Déterminons le PPCM des nombres 6 et 15. Les premiers multiples strictement positifs de 6 sont : 6, 12, 18, 24, 30... Les premiers multiples strictement positifs de 15 sont : 15, 30, 45, 60, 75... Donc PPCM(6, 15) 30 . xBx Propriétés du PPCM Comme pour le PGCD, il existe une relation fondamentale pour le PPCM. Nous pourrons ensuite déduire de cette dernière toutes les propriétés du PPCM.

Théorème 30 Soient a et b deux entiers relatifs et leur PPCM.

a b .

Preuve On peut supposer que a et b sont non nuls pour la suite. Puisque |a et |b , on a a et b . Donc a b . Mais (théorème 23 du chapitre 4) l’ensemble a b est un sous-groupe de , donc (théorème 25 du chapitre 4) il existe un entier naturel m tel que a b m . De l’inclusion a b , on en tire que m et donc m (ils sont positifs et non nuls). Puis, comme et m sont des multiples de a et b, on a m (remarque n°4 de la définition 6). Ainsi, m et a b .

Théorème 31 Soient a et b deux entiers relatifs.

1) PPCM( , ) PPCM( , )a b b a 2) PPCM( , 0) 0a 3) PPCM( , 1)a a 4) | PPCM( , )a b a b b .

Preuve 1) On a : ( ) ( )a b a b b a b a , ce qui permet de conclure. 2) Immédiat compte tenu de la définition étendue du PPCM. 3) On a : ( 1)a a a , ce qui permet de conclure. 4) Supposons que |a b . Alors b a et alors a b b , ce qui permet de conclure puisque a b .

Théorème 32 2( , ) , , PPCM( , ) PPCM( , )a b k ka kb k a b .

Preuve On a : ( ) ( ) ( )ka kb k a b k k . Ainsi, PPCM( , )ka kb k k .

Théorème 33 Soient a et b deux entiers relatifs et leur PPCM.

|, |

|a k

k kb k

.

Preuve

On dispose des équivalences suivantes : |

||

a k k ak a b k k

b k k b

.

L’associativité déjà rencontrée avec le PPCM de deux entiers reste encore valable avec le PPCM :


Relation fondamentale du PPCM de deux entiers relatifs

Homogénéité du PPCM

Le théorème 34 traduit l’associativité du PPCM.

Le théorème 35 donne un moyen pra-tique de calculer le PPCM de deux en-tiers. Mais attention, on demande aux deux entiers d’être premiers entre eux.

On parle ici du plus petit au sens de la relation divise !

Le théorème 36 permet de calculer le PPCM de deux entiers à partir du PGCD de ces mêmes entiers.

Utilisation de l’homogénéité du PPCM et du théorème 35.

Théorème 34

3( , , ) , ( ) ( )a b c a b c a b c .

Preuve En utilisant l’associativité de l’intersection dans ( ) , on a : ( ) ( )a b c a b c . Remarques 1. D’après le théorème 34 on pourra écrire a b c au lieu de ( )a b c (ou ( )a b c ). 2. Le couple ( , ) est un demi-groupe commutatif.

Théorème 35 Soient a et b deux entiers relatifs premiers entre eux.

PPCM( , )a b ab .

Preuve On écarte le cas où l’un des entiers a et b est nul (sinon l’égalité devient triviale). On note a b . Il est clair que ab est un multiple commun de a et b. Le PPCM étant le plus petit multiple commun strictement positif de a et b, on a (théorème 33) |ab . Puis, comme |a et |b , alors (théorème 16) |ab . Ainsi, ab . Remarque A titre d’exercice, le lecteur pourra démontrer le théorème 35 sans utiliser le théorème 33 (et donc en utilisant la relation d’ordre usuelle).

Théorème 36 2( , ) , ( )( )a b a b a b ab .

Preuve On écarte le cas où l’un des entiers a et b est nul (sinon l’égalité devient triviale). Notons a b et a b . D’après le théorème 10, il existe deux entiers relatifs a’ et b’ tels que a a et b b et 1a b . Donc, ( ) ( ) ( )a b a b a b a b .

Ainsi, 2 ( )( )a b a b ab . Exemple Déterminons le PPCM des entiers 315 et 196. Grâce à l’algorithme d’Euclide on a : 315 196 1 119 ; 196 119 1 77 ; 119 77 1 42 ; 77 42 1 35 ; 42 35 1 7 ; et 35 7 5 0. Donc PGCD(315, 196) 7 .

Puis, en utilisant le théorème 36, il vient que 315 196PPCM(315, 196) 45 196 88207

.

Remarque Le théorème 36 ne se généralise pas ! Considérons les entiers 2, 4 et 5. On a PGCD(2, 4, 5) 1 et PPCM(2, 4, 5) PPCM(1, 2) 2 . Il est alors clair que PGCD(2, 4, 5) PPCM(2, 4, 5) 2 4 5 . x6x PPCM de plusieurs entiers relatifs Nous allons généraliser la théorie du PPCM avec un nombre fini d’entiers relatifs. Les preuves seront plus succinctes. Reportez-vous aux cas avec deux entiers relatifs si certaines preuves vous semblent difficiles à comprendre.


Associativité du PPCM

Relation PGCD-PPCM

Il s’agit du plus petit multiple commun pour l’ordre usuel.


xAx Définition Commençons par une constatation :

Théorème 37

Soient n et 1( , ..., ) ( )nnx x .

L’ensemble des multiples communs strictement positifs de 1, ..., nx x admet un plus petit élément.

Preuve

L’ensemble des multiples communs strictement positifs à 1, ..., nx x est une partie de et contient 1

n

ii

x .

Cet ensemble admet donc un plus petit élément.

Définition 7

Soient n et 1( , ..., ) ( )nnx x .

Le plus petit élément de l’ensemble des multiples communs strictement positifs de 1, ..., nx x est appelé le plus petit

multiple commun de 1, ..., nx x .

Remarque 1. Le plus petit élément de l’ensemble des multiples communs strictement positifs de 1, ..., nx x est noté

1PPCM( , ..., )nx x où encore 1PPCM(( ) )i i nx . Parfois, on pourra pour plus de commodité employer la notation pour le PPCM de 1, ..., nx x . 2. On se permet d’étendre la définition 7 en posant 1PGCD( , ..., ) 0nx x dès lors où l’un des entiers 1, ..., nx x est

nul. 3. Il est clair que 1PPCM( , ..., ) 1nx x quand les entiers 1, ..., nx x sont tous non nuls.

4. Par définition, en notant 1PPCM( , ..., )nx x , il est clair que :

, ( {1, ..., }, | )ik i n x k k .

5. Il est clair que 1 1PPCM( , ..., ) PPCM( , ..., )n nx x x x .

xBx Propriété du PPCM

Théorème 38 Soient n un entier naturel non nul, 1, ..., nx x des entiers relatifs non nuls et leur PPCM.

1

n

ii

x

.

Preuve On va supposer que tous les entiers 1, ..., nx x sont non nuls (sinon la relation devient évidente).

Pour tout i de {1, ..., }n on a |ix , donc pour i de {1, ..., }n on a ix et donc 1

n

ii

x

.

Puisque (théorème 23 du chapitre 4) l’ensemble 1

n

ii

x

est un sous-groupe de , il existe un entier naturel m

non nul tel que 1

n

ii

x m

(théorème 25 du chapitre 4).

On a alors m , d’où m . Pour tout i de {1, ..., }n , comme et m sont des multiples communs de 1, ..., nx x , on a m et ainsi m .

On conclut donc que 1

n

ii

x m

.


Relation fondamentale du PPCM de plusieurs entiers relatifs

Le théorème 39 traduit l’homogé-néité du PGCD. Attention à ne pas oublier la valeur ab-solue au second membre de l’égalité.

Ainsi, le PPCM des entiers x1,...,xn cor-respond au plus petit élément (au sens de la relation « divise ») des multiples communs strictement positifs de ces entiers.

Le théorème 41 donne un moyen de calculer le PPCM de plusieurs entiers. Mais attention, ces entiers doivent être premiers entre eux.

Théorème 39

1 1 1, ( , ..., ) , , PPCM( , ..., ) PPCM( , ..., )nn n nn x x k kx kx k x x .

Preuve

En notant 1PPCM( , ..., )nx x , on a 1 1

( ) ( )n n

i ii i

kx k x k k

.

Donc 1PPCM( , ..., )nkx kx k k .

Théorème 40 Soient n un entier naturel non nul, 1, ..., nx x des entiers relatifs et leur PPCM.

, ( {1, ..., }, | ) |ik i n x k k .

Preuve

On dispose des équivalences suivantes : 1

{1, ..., }, | {1, ..., },n

i i ii

i n x k i n k x k x k

| k . Terminons ce chapitre par une généralisation du théorème 35 :

Théorème 41 Soient n un entier naturel non nul, 1, ..., nx x des entiers relatifs deux à deux premiers entre eux.

11

PPCM( , ..., )n

n ii

x x x

.

Preuve On écarte le cas où tous les entiers 1, ..., nx x est nuls (le résultat devient trivial sinon).

Notons 1PPCM( , ..., )nx x .

Il est clair que 1

n

ii

x est un multiple commun des entiers 1, ..., nx x .

Le PPCM étant le plus petit multiple commun strictement positif de 1, ..., nx x , on a (théorème 40) 1

|n

ii

x .

Enfin, pour tout i de {1, ..., }n , comme |ix , on a (théorème 28) pour tout i de {1, ..., }n , 1

|n

ii

x .

Ainsi, 1

n

ii

x

.


Homogénéité du PPCM

11133 Démonstrations supplémentaires de cours Montrer que : 2( , ) , |a b a b b a . 11233 Démonstrations supplémentaires de cours Soient a et b deux entiers relatifs. Montrer que l’ensemble a b est un sous-groupe additif de . 11333 Démonstrations supplémentaires de cours Montrer que : 3( , , ) , ( )a b c a b a bc a b . 11433 Démonstrations supplémentaires de cours Montrer que deux entiers relatifs consécutifs sont nécessairement pre-miers entre eux. 11533 Démonstrations supplémentaires de cours Montrer que : 2( , ) , , ( )n n na b n a b a b . 11633 Démonstrations supplémentaires de cours 1) Montrer que :

2( , ) ( {0, 1}) , sup( , )a b a b a b . 2) Montrer que :

2( , ) ( {0, 1}) , inf( , )a b a b a b .

11733 Nombres premiers entre eux Montrer que pour tout entier naturel n non nul :

1) 2( ) (2 1) 1n n n 2) 3 4 2( 2 ) ( 3 1) 1n n n n

3) 2 2( 1) (( 1) 1) {1, 5}n n .

11833 Divisibilité Déterminer tous les entiers relatifs n tel que :

277 | 3 5n .

11933 Congruences Soit n un entier relatif impair tel que 3 ne divise pas n. Montrer que :

2 1 [24]n . 1 10 3 Système d’équations diophantiennes Résoudre dans 2 le système d’équations d’inconnu ( , )x y :

18540

x yx y

.

1 11 3 Système d’équations diophantiennes Résoudre dans 2 le système d’équations d’inconnu ( , )x y :

100824

x yx y

.


( ) ( ) 534( ) 5( ) 510x y x yx y x y

.

1 13 3 Equation diophantienne Résoudre dans 2 l’équation d’inconnue ( , )x y :

( ) 3( ) 135x y x y .


2 2 19 4761260

x yx y

.


( ) ( ) 9x y x y y . 1 16 3 Equation diophantienne 1) Montrer que 442 et 495 sont premiers entre eux. 2) Trouver tous les couples d’entiers relatifs ( , )u v tels que :

442 495 1u v . 3) Résoudre dans 495 l’équation d’inconnue x :

442 314x .

1 17 3 Démonstrations supplémentaires de cours Théorie Soit ( , , )a b c .

1) Résoudre dans 2 l’équation d’inconnue ( , )x y : ax by c .

Application 2) Résoudre dans 2 l’équation d’inconnue ( , )x y :

a) 9 15 11x y b) 9 15 18x y .

1 18 3 Système d’équations diophantiennes Résoudre dans 4 le système d’équations d’inconnu ( , , , )x y z t :

8409002100

xyzxytyzt

.

1 19 3 Divisibilité Montrer que : 2 2 2, 360 | ( 1)( 4)n n n n . 1 20 3 Equation diophantienne

Montrer que : 2 2 2

42 2 2

10( , , , ) , 0

10x y z

x y z t x y z tx y t

.

1 21 3 Divisibilité Montrer que : 3( , , ) ( ) , | | ( )( )a b c c ab c a c b c . 1 22 3 Nombres premiers entre eux Soient n un entier supérieur ou égal à 1, 1, ..., na a des entiers relatifs

non nuls premiers entre eux deux à deux. Pour tout i de {1, ..., }n , on note :

1

n

i kk n

k i

A a

.

Montrer que 1, ..., nA A sont premiers entre eux dans leur ensemble.

1 23 3 Congruences Trouver tous les triplets d’entiers naturels ( , , )x y z tels que :

2 x y z , 1 [ ]xy z , 1 [ ]xz y et 1 [ ]yz x .

Les exercices du chapitre 10

1 24 3 Diviseurs de zéro de l’anneau Z/nZ Soit n un entier naturel non nul. Déterminer les diviseurs de zéro de l’anneau ( , , )n . 1 25 3 PGCD 1) Etablir que pour tout entier relatif n :

3(5 ) ( 2) ( 2) 38n n n n . 2) Déterminer les entiers naturels d tels que :

3(5 ) ( 2) 19n n n .

1 26 3 Système d’équations diophantiennes Résoudre dans le système d’équations d’inconnu x :

5 7 [11]7 11 [5]11 5 [7]

xxx

.

1 27 3 Système d’équations diophantiennes Résoudre dans le système d’équations d’inconnu x :

1 [6]3 [10]7 [15]

xxx

.

1 28 3 Système d’équations diophantiennes Déterminer le plus petit entier naturel x tel que :

6 [23]x et 2 213 [23 ]x .

1 29 3 Système d’équations diophantiennes Soient a et b deux entiers naturels non nuls. Théorie 1) Résoudre dans 2 le système d’équations d’inconnu ( , )x y :

x y ax y b

.

Application 2) Résoudre dans 2 le système d’équations d’inconnu ( , )x y :

a) 1022

x yx y

b)

880

x yx y

.

1 30 3 Equation fonctionnelle Démontrer qu’il n’existe pas d’application :f telle que :

, ( ( )) 1x f f x x .


10100

x yx y

.

1 32 3 Equation diophantienne Résoudre dans 2( ) l’équation d’inconnue ( , )x y :

( ) ( )x y x y x y .

1 33 3 PGCD Soit n un entier naturel. Montrer que le PGCD des entiers 2 4n et 3 3n ne peut être que 1, 2, 3 ou 6.

1 34 3 PGCD Montrer que : , (2 4) (3 3) | 6n n n . 1 35 3 Nombres premiers entre eux Montrer que : 2( , ) , 1 ( ) ( ) 1a b a b ab a b . 1 36 3 Divisibilité Montrer que : 2( , ) , 41 | 25 3 41 | 31 7x y x y x y . 1 37 3 PGCD Soient a un entier naturel et b un entier naturel non nul. 1) Montrer que si r est le reste de la division euclidienne de a par b, alors 2 1r est le reste de la division euclidienne de 2 1a par 2 1.b 2) Montrer que :

(2 1) (2 1) 2 1a b a b .


192 39 192 392520 3960 6480

x yx y

.

1 39 3 Divisibilité Soient a un entier naturel supérieur ou égal à 2, b et c deux entiers naturels non nuls premiers entre eux. Montrer que :

( 1)( 1) | ( 1)( 1)b c bca a a a . 1 40 3 Equation diophantienne Résoudre les équations d’inconnues x dans les ensembles indiqués. 1) 3 1x (dans 7 ).

2) 3 1x (dans 12 ).

3) 2 7 1 0x x (dans 9 ). 1 41 3 Système d’équations diophantiennes Résoudre dans 2( 9 ) puis sur 2( 8 ) le système d’équations d’in-connu ( , )x y :

7 5 25 4 7x yx y

.

1 42 3 Equation diophantienne Résoudre les équations d’inconnues x dans les ensembles indiqués. 1) 2 2 2 0x x (dans 5 ).

2) 2 2 2 0x x (dans 5 ).

3) 2 1 0x x (dans 5 ).

4) 22 3 2 0 [7]x x (dans ).

5) 2 1x (dans 18 ).

6) 3 23 2 0x x x (dans 24 ).

7) 2 4 3 0x x (dans 143 ). 1 43 3 Système d’équations diophantiennes Résoudre dans 2( 20 ) le système d’équations d’inconnu ( , )x y :

5 2 32 4 6x yx y

.


1 44 3 PGCD Soient m, n, a, b, c et d des entiers relatifs tels que 1ad bc . Montrer que :

( ) ( )am bn cm dn m n . 1 45 3 PGCD Montrer que : , (21 4) (14 3) 1n n n . 1 46 3 PPCM Montrer que :

, PPCM(1, 2, ..., 2 ) PPCM( 1, 2, ..., 2 )n n n n n .

1 47 3 PGCD Montrer que : 2 2 2 2( , ) , ( ) ( ) ( )a b a b ab a b . 1 48 3 PGCD et PPCM Montrer que : 2( , ) , ( ) ( )a b a b a b a b . 1 49 3 PGCD Montrer que : 2 2 2 2( , ) , ( ) ( )a b a ab b a b . 1 50 3 PGCD Montrer que :

2 2 2( , ) , 1 ( ) ( ) 3a b a b a ab b a b . On utilisera l’exercice 46.

1 51 3 Démonstrations supplémentaires de cours Soient n et p deux entiers naturels non nuls. Montrer que :

1 11 1 1

1

( , ..., ) , ( , ..., ) ,n pn p i j i j

i j i nj p

x x y y x y x y

.

1 52 3 PGCD Montrer que :

4( , , , ) , 1 ( ) ( ) ( )( )a b c d a b c d ac bd a d b c .

1 53 3 Démonstrations supplémentaires de cours Montrer que : ( , ) , ab a ba b .

1 54 3 Nombres premiers entre eux Soient a, b et c des entiers relatifs. Montrer que si a, b et c sont premiers entre eux deux à deux, alors les entiers ab bc ca et abc sont premiers entre eux. 1 55 3 PGCD Trouver tous les entiers naturels n tels que :

(2 8) (3 15) 6n n .


56105

x yx y

.


( ) ( ) 243x y x y .


(2 )(5 2 ) 16203( )

x y x yxy x y

.


12420

20

x yx y

y x

.


72x y x yx y

.


2

84( )

x yx y x y

.

1 62 3 Divisibilité Soient a et b deux entiers naturels non nuls tel que 1a b . Trouver les entiers naturels x non nuls tels que :

|a bx et |b xa et |x ab .

1 63 3 Egalité de Bézout 1) Vérifier que 429 et 700 sont premiers entre eux. 2) Déterminer tous les couples d’entiers relatifs ( , )u v tels que :

700 429 1u v . 3) Quel est l’inverse de 429 dans 700 ? 1 64 3 Egalité de Bézout Montrer que : 3, ( , , ) , 1914 1915 1916n a b c n a b c . 1 65 3 PGCD Montrer que : 1 1, (2 3 ) (2 3 ) 1n n n nn . 1 66 3 PGCD Pour tout entier naturel n non nul, on note :

2 3 5n n nnu .

Montrer que :

1 2, PGCD( , , ) 2n n nn u u u .

1 67 3 Equation fonctionnelle Trouver toutes les applications :f telles que :

, ( , )( , ) , ( , ) ( , )( , ) , ( , ) ( , )

a f a a aa b f a b f b aa b f a b f a a b

.


( 27)( 12)x y xy .


1 69 3 Divisibilité 1) Montrer que :

4 3 2, 12 | 4 5 2n n n n n . 2) Montrer que :

2 4 4( , ) , 30 | ( )m n mn m n . 3) Montrer que :

3 8 4 4 2, 3804 | ( )(5 3 )n nn n n .

1 70 3 Equation fonctionnelle Soit :f une application telle que : - f est strictement croissante ; - (2) 2f ;

- 2( , ) ( ) , 1 ( ) ( ) ( )m n m n f mn f m f n . Montrer que :

, ( )n f n n .

1 71 3 PGCD Soient a, b, c et n des entiers naturels non nuls tels que :

1a b et nab c . Montrer qu’il existe un couple ( , ) de 2( ) tel que :

na et nb .

1 72 3 Nombres premiers entre eux Montrer que : , ! ( ! 1) 1n n n . 1 73 3 PGCD Soient a et b deux entiers naturels non nuls tels que a soit impair et supérieur ou égal à 3. Montrer que :

(2 1) (2 1) 1a b . 1 74 3 Equation diophantienne Déterminer tous les couples ( , )a b de 2( ) tels que :

a b et ( ) ( ) 77a b a b .

1 75 3 Equation diophantienne Déterminer tous les couples ( , )a b d’entiers naturels tels que :

a b , 256a b et 16a b .

1 76 3 Equation diophantienne Résoudre dans 2 les équations suivantes d’inconnues ( , )x y :

1) 7 19 1x y 2) 7 19 9x y .


3675 5145 4410x y .


323 391 612x y .

1 79 3 Anneau Z/nZ Montrer que dans l’anneau 1700 , l’élément 429 est inversible et déterminer son inverse.

1 80 3 Nombres premiers entre eux Soit n un entier naturel non nul. On note :

3

1

n

nk

S k

.

1) Calculer pour tout entier naturel n non nul, 1n nS S .

2) Montrer que :

1 2, ( ) 1n n nn S S S .

1 81 3 Nombres premiers entre eux Pour tout entier naturel n non nul, on pose :

215 8 6na n n et 230 21 13nb n n .

1) Montrer que pour tout entier naturel n non nul : 2 | 5n n nb a a .

2) En déduire que pour tout entier naturel n non nul, les entiers na et

nb sont premiers entre eux.

1 82 3 PGCD Montrer que : ( , ) , 1 ( ) ( ) {1, 2}a b a b a b a b . 1 83 3 Nombres premiers entre eux Soient n et d deux entiers naturels non nuls. 1) Montrer que d divise n et 2n , alors d est égal à 1 ou à 2. 2) En déduire que parmi quatre entiers naturels non nuls consécutifs, il y en a toujours un qui est premier avec chacun des trois autres. 1 84 3 Nombres premiers entre eux Montrer que : , ( ! 1) (( 1) ! 1) 1n n n . On utilisera l’exercice 72. 1 85 3 Système d’équations diophantiennes Soit k un entier relatif. 1) Quels sont les restes possibles de la division de 2k par 7 ? 2) Déterminer les entiers relatifs x tels que 2 2 [7]x .

3) L’équation d’inconnue x : 23 7 2x x a-t-elle des solutions dans l’ensemble 7 ?

4) Dans 7 , quel est l’inverse de 3 ? Celui de 4 ?

5) Résoudre dans 2 le système d’équations d’inconnu ( , )x y : 2

2

8 3 [7]1 [7]

x xyx xy

.

1 86 3 Système d’équations diophantiennes Soit k un entier relatif. 1) Quels sont les restes possibles de la division de 2k par 11 ? 2) Déterminer les entiers relatifs x tels que 2 1 [11]x .

3) Déterminer les entiers relatifs x tels que 2 3 [11]x .

4) Dans l’anneau 11 , quel est l’inverse de 2 ? l’inverse de 3 ? l’in-

verse de 5 ? 5) Résoudre dans 2( 11 ) le système d’équations d’inconnu ( , )x y :

2 24 23

x yxy

.


Documents

Arithmétique dans PGCD et PPCM