2 – \(PGCD\) et \(PPCM\)

cours pdf

I – Le plus grand commun diviseur de deux entiers.

1°) Diviseurs commun de deux entiers naturels.

Définition :

  1. Soit \(a\) un entier naturel. On note \(Div\)\(\mathbb{N}\)(\(a\) ) l’ensemble des diviseurs de l’entier naturel \(a\) dans \(\mathbb{N}\).
  2. Soit \(a\) et \(b\) deux entiers naturels. On appelle diviseurs communs aux deux entiers naturels \(a\) et \(b\), les entiers naturels qui divisent à la fois \(a\) et \(b\) ; on note cet ensemble \(Div\)\(\mathbb{N}\)(\(a\);\(b\)).

Exemple :
Les diviseurs de 12 dans \(\mathbb{N}\) sont : 1, 2, 3, 4, 6, 12 ; ainsi, \(Div\)\(\mathbb{N}\)(12)={1,2,3,6,12}.
Les diviseurs de 18 dans \(\mathbb{N}\) sont : 1, 2, 3, 6, 9, 18 et \(Div\)\(\mathbb{N}\)(18)={1,2,3,6,9,18}.
Les diviseurs communs de 12 et 18 dans \(\mathbb{N}\) sont : 1, 2, 3 et 6 et \(Div\)\(\mathbb{N}\)(12;18)={1,2,3,6}.

Remarque :
Réfléchir à ce que cela donne dans \(\mathbb{Z}\).

2°) Vers la notion de PGCD.

Soit \(a\) et \(b\) deux entiers naturels, dont l’un des deux au moins est non nul.
Les ensembles \(Div\)\(\mathbb{N}\)(a) et \(Div\)\(\mathbb{N}\)(b) ont au moins l’entier naturel 1 en commun, donc l’ensemble \(Div\)\(\mathbb{N}\)(a) \( \cap \) \(Div\)\(\mathbb{N}\)(b) est une partie de \(\mathbb{N}\) non vide et qui est majorée par \(\max \left( {a;b} \right)\) donc possède un plus grand élément, que l’on appelle le plus grand commun diviseur de \(a\) et \(b\) ; on le note \(PGCD\left( {a;b} \right)\).

Définition :
On appelle \(PGCD\) des deux entiers \(a\) et \(b\) avec l’un des deux au moins non nul le plus grand entier naturel qui divise simultanément les entiers \(a\) et \(b\). On note parfois \(a \wedge b\).

Exemple:
Dans l’exemple ci dessus, \(PGCD(12;18) = 6\).

Théorème :
Soit \(a\) un entier naturel (non nul). Les propriétés énoncées avec \(PGCD\) s’énoncent avec \(Div\)\(\mathbb{N}\).

  1. \(PGCD\)(\(a\);0)=\(a\) ,
  2. Si de plus \(\left. a \right|b\) alors \(PGCD\)(\(a\);\(b\))=\(a\).
  3. Si \(a\)=\(b\) alors \(PGCD\)(\(a\);\(b\))=\(PGCD\)(\(a\))

Démonstration :

  1. Soit \(a\) un entier naturel, on a \(Di{v_{\mathbb{N}}}\left( 0 \right) = \mathbb{N}\) et \(Di{v_{\mathbb{N}}}\left( a \right) \subset Di{v_{\mathbb{N}}}\left( 0 \right)\) or \(Di{v_{\mathbb{N}}}\left( a \right) \cap Di{v_{\mathbb{N}}}\left( 0 \right) = Di{v_{\mathbb{N}}}\left( a \right)\) d’où \(\max \left({Di{v_{\mathbb{N}}}\left( a \right) \cap Di{v_{\mathbb{N}}}\left( 0 \right)} \right) = \max \left( {Di{v_{\mathbb{N}}}\left( a \right)} \right) = a\)  ainsi \(PGCD\)(\(a\);0)=\(a\).
  2. Si \(\left. a \right|b\) alors \(Di{v_{\mathbb{N}}}\left( a \right) \subset Di{v_{\mathbb{N}}}\left( b \right)\) et donc \(Di{v_{\mathbb{N}}}\left( a \right) \cap Di{v_{\mathbb{N}}}\left( 0 \right) = Di{v_{\mathbb{N}}}\left( a \right)\); par suite \(\max \left( {Di{v_{\mathbb{N}}}\left( a \right) \cap Di{v_{\mathbb{N}}}\left( 0 \right)} \right) = \max \left( {Di{v_{\mathbb{N}}}\left( a \right)} \right) = a\), d’où  \(PGCD\)(\(a\);\(b\))=\(a\)

3°) Algorithme d’Euclide pour la recherche du PGCD.

Proposition :
Soit \(a\) et \(b\) deux entiers naturels avec \(b\) non nul. Si \(r\) désigne le reste dans la division euclidienne de \(a\) par \(b\) alors, les diviseurs communs de \(a\) et \(b\) sont les diviseurs communs de \(b\) et \(r\) c’est à dire \(Div\)\(\mathbb{N}\)(\(a\);\(b\)) = \(Div\)\(\mathbb{N}\)(\(b\);\(r\)).
Si \(r\)=0 alors, \(Div\)\(\mathbb{N}\)(\(a\);\(b\)) = \(Div\)\(\mathbb{N}\)(\(b\);\(r\)) = \(Div\)\(\mathbb{N}\)(\(b\)).

Démonstration :
Soit \(a\) et \(b\) deux entiers naturels avec \(b\) non nul ; en effectuant la division euclidienne de \(a\) par \(b\), notons \(r\) le reste. On a \(a = bq + r\) avec \(0 \le r < b\).

Sens (\(\Rightarrow \)) on montre que tout diviseur \(d\) de \(a\) et de \(b\) divise \(b\) et \(r\).

  • Sens \(\Rightarrow \).Si \(\left\{ {\begin{array}{*{20}{c}}{d\left| a \right.}\\{d\left| b \right.}\end{array} \Rightarrow \left\{ {\begin{array}{*{20}{c}}{d\left| a \right.}\\{d\left| b \right.}\\{d\left| {bq} \right.}\end{array}} \right.} \right. \Rightarrow \left\{ {\begin{array}{*{20}{c}}{d\left| b \right.}\\{d\left| {a – bq} \right.}\end{array}} \right.\) or \(r = a – bq\) donc \(\left\{ {\begin{array}{*{20}{c}}{d\left| b \right.}\\{d\left| r \right.}\end{array}} \right.\).

Sens (\( \Leftarrow \)) on montre que tout diviseur \(d\) de \(b\) et de \(r\) divise \(a\) et \(b\).

  • Sens \( \Leftarrow \) Si \(\left\{ {\begin{array}{*{20}{c}}{d\left| b \right.}\\{d\left| r \right.}\end{array}} \right.\)\(\Rightarrow \)\(\left\{ {\begin{array}{*{20}{c}}{d\left| b \right.}\\{d\left| {bq} \right.}\\{d\left| r \right.}\end{array}} \right. \Rightarrow \left\{ {\begin{array}{*{20}{c}}{d\left| {bq + r} \right.}\\{d\left| b \right.}\end{array}} \right. \Rightarrow \left\{ {\begin{array}{*{20}{c}}{d\left| a \right.}\\{d\left| b \right.}\end{array}} \right.\).

Cette proposition permet de justifier l’algorithme d’Euclide, à savoir, que lorsque \(b\) ne divise pas \(a\) le \(PGCD\) de \(a\) et \(b\) est le dernier reste non nul.

Lemme d’Euclide :

Soit \(\left( {a;b} \right) \in {\left( {\mathbb{N}*} \right)^2}\). Si des entiers \(q\) et \(r\) avec \(r\) \( \ne \) 0 sont tels que \(a=bq+r\) alors \(PGCD\)(\(a\);\(b\))=\(PGCD\)(\(b\);\(r\)).

En fait, Euclide n’utilisa pas cette méthode qui porte son nom mais celle des différences successives, en remarquant au préalable que si \(a\)\(\ge \)\(b\)  :\(Di{v_{\mathbb{N}}}\left( {a;b} \right) = Di{v_{\mathbb{N}}}\left( {b;a – b} \right)\).

Exemple important ; Rappelons le principe de l’algorithme d’Euclide, en calculant le \(PGCD\) de 1386 et 3267 (il faut savoir faire cela)

3267 = 1386*2 + 495
1386 495*2 + 396
495 396*1 + 99
396 99*4 + 0

D’où \(PGCD\)(1386;3267) = 99.
En effet, \(PGCD\)(3267;1386) = \(PGCD\)(1386;495)= \(PGCD\)(495;396)= \(PGCD\)(396;99)

Deux façons de procéder :

  • \(PGCD\)(396;99) = \(PGCD\)(99;0) = 99 (Proposition).
  • Ou \(r = 0\) \( \Rightarrow \) 99|396 donc \(PGCD\)(3267;1386) = 99 (dernier reste non nul)

Avec la TI 83, le \(PGCD\) de deux entiers est obtenu avec \(GCD\)(24,140).
Il faut ainsi savoir programmer un algorithme de calcul du \(PGCD\).

Corollaire (ROC).
Soit \(a\) et \(b\) deux entiers naturels dont l’un au moins des deux est non nul.
Un entier naturel est un diviseur commun de \(a\) et \(b\) si et seulement si il divise \(PGCD\)(\(a\);\(b\)).

Exemple :
Les diviseurs communs à 3267 et 1386 sont donc les diviseurs de leur \(PGCD\) qui est 99. Ainsi :
99=1*99
99=3*33
99=9*11.

Conclusion : les diviseurs communs de 3267 et 1386 sont donc 1, 3, 9, 11, 33, 99.

II – Entiers premiers entre eux et relation de Bézout.

1°) Entiers premiers entre eux.

Définition:
Deux entiers naturels sont dits premiers entre eux si et seulement si leur \(PGCD\) est égal à 1.

Exemple :
\(PGCD\)(8;3) = 1 donc 3 et 8 sont des nombres premiers entre eux. A ne pas confondre avec les nombres premiers, 8 n’est pas premier !

Théorème très important (ROC) (quotient de deux entiers par leur PGCD).
Soit \(a\) et \(b\) deux entiers relatifs non nuls. Si \(d\)=\(PGCD\)(\(a\);\(b\)) alors il existe deux entiers relatifs \(a’\) et \(b’\) premiers entre eux tels que \(a=da’\) et \(b=db’\).

Démonstration :
Comme \(d\)=\(PGCD\)(\(a\);\(b\))  alors \(d\) divise \(a\) et \(d\) divise \(b\), par définition de la divisibilité, il existe deux entiers relatifs \(a’\) et \(b’\) tels que : \(a = da’\) et \(b = db’\).
On a : \(d = PGCD\left( {a;b} \right) = PGCD\left( {da’;db’} \right) = dPGCD\left( {a’;b’} \right)\). Comme \(d \ge 1\) (car \(d \ne 0\)), l’équation \(d = dPGCD\left( {a’;b’} \right)\) équivaut à \(PGCD\left( {a’;b’} \right) = 1\).

Exemple : Déterminer deux nombres de produit et \(PGCD\) donnés.
Déterminer tous les couples (\(a\);\(b\)) d’entiers naturels non nuls tels que :\(\left\{ {\begin{array}{*{20}{c}}{ab = 1452}\\{PGCD\left( {a;b} \right) = 11}\end{array}} \right.\).

Comme \(PGCD\left( {a;b} \right) = 11\), il existe deux entiers naturels \(a’\) et \(b’\) premiers entre eux tels que :\(\left\{ {\begin{array}{*{20}{c}}{a = 11a’}\\{b = 11b’}\end{array}} \right.\). Le problème revient à trouver tous les couples d’entiers \((a’\);\(b’)\) tels que \(\left\{ {\begin{array}{*{20}{c}}{11 \times a’ \times 11 \times b’ = 1452}\\{PGCD\left( {(a’;(b’} \right) = 1}\end{array}} \right. \Leftrightarrow \left\{ {\begin{array}{*{20}{c}}{a’ \times b’ = 12}\\{PGCD\left( {a’;b’} \right) = 1}\end{array}} \right.\).

Or \(Di{v_{\mathbb{N}}}\left( {12} \right) = \left\{ {1;2;3;4;6;12} \right\}\) et les seuls couples d’entiers naturels premiers entre eux tels que \(a’b’\)=12 sont \(\left( {1;12} \right)\), \(\left( {3;4} \right)\), \(\left( {4;3} \right)\) et \(\left( {12;1} \right)\).

Avec \(\left\{ {\begin{array}{*{20}{c}}{a = 11a’}\\{b = 11b’}\end{array}} \right.\), on en déduit que \({S_{{Z^2}}} = \){\(\left( {11;132} \right)\), \(\left( {33;44} \right)\), \(\left( {44;33} \right)\), \(\left( {132;11} \right)\)

2°) Théorème de Bézout.

Théorème de Bézout :
Soit \(a\) et \(b\) deux entiers naturels non nuls. Les entiers \(a\) et \(b\) sont premiers entre eux si et seulement si, il existe deux entiers deux entiers relatifs \(u\) et \(v\) tels que \(au+bv\)=1.

Démonstration :
Sens (\( \Leftarrow \)) Supposons qu’il existe deux entiers relatifs \(u\) et \(v\) tels que \(au+bv\)=1
Soit \(d\)=\(PGCD\)(\(a\);\(b\)) alors \(\left. d \right|a\) et \(\left. d \right|b\) et donc pour tous entiers naturels \(u\) et \(v\) : \(\left. d \right|(au+bv)\)

Or  \(au+bv=1\) entraîne \(\left. d \right|1\) soit dans \(\mathbb{N}\) \(d=1\) et prouve que \(a\) et \(b\) sont premiers entre eux.
Sens (\(\Rightarrow \)). Supposons que \(a\) et \(b\) sont deux entiers naturels premiers entre eux et  montrons qu’il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = 1\).

Pour cela, considérons l’ensemble \(E = \left\{ {au + bv\left. {} \right|\left( {u;v} \right) \in {Z^2}} \right\}\)
Cet ensemble est non vide. En effet, en prenant \(\left( {u;v} \right) = \left( {1,0} \right)\), on a :\(a \times 1 + b \times 0 = a\) donc \(a \in E\). De plus, puisque \(a \in \(\mathbb{N}\)*\) alors \(E\) contient des entiers naturels non nuls et, parmi ceux-ci, il en existe un qui est le plus petit que l’on peut noter \(m\) obtenu pour \(\left( {u;v} \right) = \left( {{u_1};{v_1}} \right) \in {Z^2}\). Ainsi, \(m = a{u_1} + b{v_1}\).

Montrons que \(m\) divise \(a\) et \(b\).

Dans la division euclidienne de \(a\) par \(m\), il existe un unique couple \(\left( {q;r} \right) \in I{N^2}\) avec \(0 \le r < m\) tels que \(a = mq + r\).

Mais, \(m = a{u_1} + b{v_1}\) donc \(a = mq + r\) s’écrit :  \(a = \left( {a{u_1} + b{v_1}} \right) \times q + r\)
\(r = a – \left( {a{u_1} + b{v_1}} \right) \times q\)
\(r = a\left( {1 – {u_1}q} \right) + b\left( { – q{v_1}} \right)\).

En posant \(\left( {u;v} \right) = \left( {1 – {u_1}q; – q{v_1}} \right)\) comme \(q \in IN\), \(\left( {{u_1};{v_1}} \right) \in {Z^2}\) et que la somme et le produit d’entiers (relatifs) est un entier relatif alors \(\left( {u;v} \right) \in {Z^2}\) donc, il existe un couple d’entiers relatifs \(\left( {u;v} \right)\) tel que \(r = au + bv\) ce qui entraine que \(r \in E\).

Or, d’après la définition de la division euclidienne, \(0 \le r < m\) ainsi \(r\) est positif et on a vu qu’il était dans \(E\) mais \(m\) est aussi dans \(E\) et est le plus petit entier strictement positif de \(E\) donc \(r = 0\).

Puisque \(r\)=0 et que \(a = mq + r\) cela entraîne que \(a = mq\) et donc que \(m\) divise \(a\).

En effectuant la division euclidienne de \(b\) par \(m\), on montrerait de même que \(m\) divise \(b\).

Ainsi \(m\left| a \right.\) et \(m\left| b \right.\) avec comme hypothèse de départ \(PGCD\left( {a;b} \right) = 1\) donc \(m\left| 1 \right.\) et puisque \(m\) est un entier naturel strictement positif, cela implique \(m\)=1 et puisque \(m = a{u_1} + b{v_1}\) il vient \(1 = a{u_1} + b{v_1}\) et donc il existe deux entiers relatifs \({u_1}\)et \({v_1}\)tels que \(1 = a{u_1} + b{v_1}\).

Conclusion : Si \(a\) et \(b\) sont deux entiers naturels premiers entre eux alors il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = 1\).

3°) Une application du théorème de Bézout : comment trouver une relation de Bézout lorsque \(PGCD\)(\(a\),\(b\))=1 ?

Algorithme d’Euclide et « remonter » l’algorithme.
Prenons \(a\)=5 et \(b\)=3 ; on a bien \(PGCD\)(5 ;3)=1.
L’algorithme d’Euclide donne :

Etape 1 : 5=3*1+2       
Etape 2 : 3=2*1+1
Etape 3 : 2=1*2+0

Etape 2 : 1=3-2*1
Etape 1 : 2=5-3*1 d’où 1=3-(5-3*1)*1=3*2-5*1

Ce qui donne 5*(-1)+3*(2)=1.

4°) Propriétés du PGCD.

Théorème : Identité de Bézout.

Soit \(a\), \(b\) et \(d\) des entiers strictement positifs.

  1. Si \(d = PGCD\left( {a;b} \right)\) alors il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\).
  2. \(d = PGCD\left( {a;b} \right)\) si et seulement si \(d|a\), \(d|b\) et il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\).

Démonstration :

  1. Soit \(I\) l’ensemble des entiers naturels de la forme \(an+bm\) où \(n\) et \(m\) sont deux entiers relatifs. Nous allons démontrer que \(PGCD\)(\(a\);\(b\))\( \in \)\(I\).
    La première chose à dire est que \(I\) est non vide. En effet 0, \(a\) et \(b\) sont dans \(I\).
    Comme tout sous ensemble non vide de \(\mathbb{N}\), \(I\) admet un plus petit élément non nul. Appelons \(p\).
    Comme \(p\)\( \in \)\(I\), il existe deux entiers naturels \(u\) et \(v\) tels que \(p\) = \(au+bv\).
    Supposons que \(d|a\) et \(d|b\) et qu’il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = d\). Comme tout élément de \(I\), \(p\) est clairement divisible par les diviseurs communs à \(a\) et \(b\). Il l’est donc en particulier pour le plus grand d’entre eux qu’est leur \(PGCD\) \(d\).
    Ainsi \(d\) divise \(p\). Une conséquence de ceci est que \(d\)\( \le \)\(p\).
    Il reste à prouver qu’il s’agit d’une égalité. La dernière étape va consister à démontrer que \(p\) est un diviseur commun à \(a\) et \(b\).
    Effectuons la division euclidienne de \(a\) par \(p\). Il existe donc un couple d’entiers naturels (\(q\);\(r\)) tels que : \(a=pq+r\) avec 0\( \le \)\(r\)<\(p\).
    On peut alors écrire que : \(r = a – qp = a – q\left( {au + bv} \right) = a\left( {1 – qu} \right) + bv\).
    \(r\) est donc un élément de l’ensemble \(I\) qui est strictement plus petit que \(p\).
    Compte tenu de ce qu’est \(p\), \(r\) est donc nécessairement égal à 0.
    Le reste de la division euclidienne étant nul, \(p\) est donc un diviseur de \(a\).
    De la même façon, on montre que \(p\) est un diviseur de \(b\).
    En récapitulant, nous savons que \(p\) est un diviseur commun à \(a\) et \(b\) et aussi que \(p\) est supérieur ou égal à leur Plus Grand Commun Diviseur \(d\). Donc les entiers naturels \(p\) et \(d\) sont nécessairement égaux.
    Le \(PGCD\) de \(a\) et \(b\) est donc bien de la forme \(au+bv\).
  2. Sens \(\Leftarrow \) :
    Soit \(d’ = PGCD\left( {a;b} \right)\). Puisque \(d\) divise \(a\) et \(b\), on a \(d{\rm{ ‘}} = PGCD\left( {a;b} \right) = PGCD\left( {da’;db’} \right) = dPGCD\left( {a’;b’} \right)\) donc \(d|d’\). Mais \(d’\) divise \(a\) et \(b\) donc \(d’\) divise \(au+bv\) c’est-à-dire \(d\). d’où \(d\)=\(d’\).
    Sens \(\Rightarrow \) :
    Comme \(d = PGCD\left( {a;b} \right)\) alors, d’après le corollaire, \(d|a\) et \(d|b\) donc pour tous entiers relatifs \(u\) et \(v\), \(d|au\)  et \(d|av\) d’où \(d|(au+bv)\).
    Il existe \(u\) et \(v\) tels que \(au+bv\)=\(d\).

Corollaire (propriété multiplicative du PGCD) :
Soit \(a\) et \(b\) deux entiers naturels non nuls. Si \(d = PGCD\left( {a;b} \right)\) alors pour tout entier naturel \(c\) non nul \(dc = PGCD\left( {ac;bc} \right)\).

Démonstration :
\(\left\{ {\begin{array}{*{20}{c}}{d\left| a \right.}\\{d\left| b \right.}\end{array}} \right. \rightarrow \left\{ {\begin{array}{*{20}{c}}{d\left| {ac} \right.}\\{d\left| {bc} \right.}\end{array}} \right.\) ou c\(\in \)\(\mathbb{N}\)*.
Mais d’après le théorème précèdent, puisque \(d = PGCD\left( {a;b} \right)\) alors il existe deux entiers relatifs \(u\) et \(v\) tels que \(d = au + bv\) donc il existe deux entiers relatifs \(u\) et \(v\) tels que \(dc = a\left( {cu} \right) + b\left( {cv} \right)\). D’après la réciproque du théorème précèdent, \(dc = PGCD\left( {ac;bc} \right)\).

Remarque : Il n y a pas en général unicité des entiers \(u\) et \(v\).

Autre démonstration :
Soit \(d\) le \(PGCD\) de \(a\) et \(b\). Nous allons montrer que \(\(k\)d\) est le \(PGCD\) de \(ka\) et \(kb\)
La première chose à montrer est que \(kd\) est un diviseur commun de \(ka\) et \(kb\).
Preuve :
\(d\) divise \(a\) et \(b\) donc il existe \(m\) et \(n\) entiers tels que \(a\) = \(md\) et \(b\) = \(nd\). Donc \(ka\) = \(kmd\) (ce qui signifie que \(d\) divise \(ka\)) et \(kb\)=\(knd\) (ce qui signifie que \(v\) divise \(kb\)).
Il reste à montrer que n’importe lequel des diviseurs communs à \(ka\) et \(kb\) divise \(kd\).
Soit \(n\) un diviseur commun à \(ka\) et \(kb\).
Comme \(d\) est le \(PGCD\) de \(a\) et \(b\), il existe donc d’après Bézout deux entiers \(u\) et \(v\) tels que
\(au\) + \(bv\) = \(d\).
Multiplions cette égalité par \(k\). Il vient alors que :\(ka.u\) + \(kb.v\) = \(kd\).
\(n\) divisant \(ka\) et \(kb\), il divise donc la somme \(ka.u\) + \(kb.v\) c’est à dire \(kd\)
Conclusion : \(kd\) est le \(PGCD\) de \(ka\) et \(kb\).

Exemples :
3*5 +2*(-7)=1 d’où 3 et 2 sont premiers entre eux.
\(n\)*1 + (\(n\)+1)*-1=1 d’où deux entiers consécutifs \(n\) et \(n\)-1 sont premiers entre eux.
L’équation 4\(x\)+7\(y\)=1 admet-elle des solutions (\(x\);\(y\)) entières ? Comme 4 et 7 sont premiers entre eux, il existe deux entiers relatifs \(u\) et \(v\) tels que 4\(u\)+7\(v\)=1.

5°) Théorème de Gauss.

Théorème :
Soit \(a\), \(b\) et \(c\) trois entiers naturels non nuls. Si \(a|n\) et \(b|n\) et \(PGCD\)(\(a\);\(b\))=1 alors \(\left( {a\left| c \right.} \right)\).

Démonstration : (à partir de la relation de Bézout).
Puisque \(a\) et \(b\) sont premiers entre eux, d’après le théorème de Bézout, il existe deux entiers relatifs \(u\) et \(v\) tels que \(au + bv = 1\) donc, pour tout entier naturel \(c\) non nul, \(acu + bcv = c\).
par ailleurs, \(a\left| {acu} \right.\) car \(a\) divise tout multiple de lui-même,
\(a\left| {bc} \right.\) (par hypothèse) donc \(a\left| {bcv} \right.\)
donc \(a\) divise la somme \(acu + bcv\) qui est égale à \(c\) donc \(a\) divise \(c\).

Attention. La réciproque de ce théorème est fausse. \(a\) peut diviser \(bc\) sans diviser \(b\) et \(c\). en effet, \(6\left| {300} \right.\) or \(300 = 15 \times 20\) et pourtant 6 ne divise ni 15 ni 20.

Corollaire :
Soit \(a\), \(b\) et \(n\) trois entiers naturels. Si \(a|n\) et \(b|n\) et \(PGCD\)(\(a\);\(b\))=1 alors \(\left( {ab\left| n \right.} \right)\).

Démonstration :
si \(\left\{ {\begin{array}{*{20}{c}}{a\left| n \right.}\\{b\left| n \right.}\end{array}} \right.\) cela implique qu’il existe deux entiers naturels \(p\) et \(q\) tels que \(\left\{ {\begin{array}{*{20}{c}}{n = ap}\\{n = bq}\end{array}} \right. \leftrightarrow ap = bq\) ce qui signifie que \(b\left| {ap} \right.\) or \(PGCD\left( {a;b} \right) = 1\), d’après le théorème de Gauss \(b\left| p \right.\). il existe alors un entier naturel \(p’\) tel que \(p = bp’\) ce qui donne \(n = abp’\) d’où \(ab|n\).

Le lemme d’Euclide :
Soit \(a\) et \(b\) deux entiers relatifs et \(p\) un nombre premier.
Si \(p\) divise \(ab\) alors \(p\) divise \(a\) ou \(p\) divise \(b\).

Démonstration :
Soit \(a\) et \(b\) deux entiers relatifs.
• Si \(ab = 0\) alors l’un des deux entiers \(a\) ou \(b\) est nul et donc \(p\) divise cet entier donc \(p\) divise \(a\) ou \(p\) divise \(b\).
• Si \(ab \ne 0\) :
Si \(p\) divise \(a\) alors c’est fini.
Si \(p\) ne divise pas \(a\) comme \(p\) est premier et que \(p\) ne divise pas \(a\) d’après le théorème de Bézout, il existe un couple d’entiers relatifs \(u\) et \(v\) tels que \(au + pv = 1\). puis que \(b\) est non nul, en multipliant cette égalité par \(b\), il vient : \(\left( {ab} \right)u + p\left( {bv} \right) = b\). mais \(p\left| {ab} \right.\) donc \(p\left| {abu} \right.\) et \(p\left| p \right.\) donc \(p\left| {pbv} \right.\) donc \(p\left| {\left( {abu + pbv} \right)} \right.\) donc \(p\left| b \right.\).

Application : déterminer toutes les relations de Bézout entre les nombres premiers entre eux.
Réciproque indispensable.

6°) Résolution d’équations diophantiennes.

Définition :
Soit \(a\), \(b\) et \(c\) trois nombres entiers. Une équation de la forme \(ax+by=c\) où \(x\) et \(y\) sont des inconnues dans \(\mathbb{Z}\) est appelée équation diophantienne.
Résoudre une telle équation, c’est déterminer les couples d’entiers relatifs (\(x\);\(y\)) vérifiant cette équation.

Proposition :
l’équation \(ax + by = c\) ou \(\left( {a;b;c} \right) \in {\mathbb{Z}^3}\) avec \(\left( {a;b} \right) \ne \left( {0;0} \right)\) possede des solutions dans \(\mathbb{Z²}\) si et seulement si \(d = PGCD\left( {a;b} \right)\) divise \(c\).

Démonstration :
Supposons que \(\left( {{x_0};{y_0}} \right)\) est un couple de solutions dans \(\mathbb{Z}²\) de l’équation et soit \(d = PGCD\left( {a;b} \right)\). Comme \(d\left| a \right.\) et \(d\left| b \right.\) alors \(d\left| {a{x_0} + b{y_0}} \right.\) donc \(d\left| c \right.\).
Réciproquement, supposons que \(d|c\). Comme \(d|a\), \(d|b\) et \(d|c\), il existe un triplet d’entiers \(a’\), \(b’\) et \(c’\) tels que \(a = da’\), \(b = db’\) et \(c = dc’\) avec \(a’ \wedge b’ = 1\).
Puisque \(\left( {a;b} \right) \ne \left( {0;0} \right)\), cela entraine \(d\)\(\ne \)0 et l’équation s’ecrit \(a’x + b’y = c’\).
Comme \(a’ \wedge b’ = 1\), d’après le théorème de Bézout, il existe un couple (\(u\);\(v\)) tel que \(a’u + b’v = 1\).
En multipliant l’équation par \(c’\), il vient \(a’c’u + b’c’v = c’\). Le couple \(\left( {c’u;c’v} \right)\) est une solution particulière de l’équation \(ax + by = c\).
Une condition nécessaire et suffisante d’existence de solution est \(d|c\).

Théorème :
Si \(\left( {{x_0};{y_0}} \right)\) une solution particulière de l’équation \(ax + by = c\) ou \(\left( {a;b;c} \right) \in {\mathbb{Z}^3}\) avec \(\left( {a;b} \right) \ne \left( {0;0} \right)\) alors l’ensemble des solutions est l’ensemble des couples \(\left( {x;y} \right)\) ou \(x = {x_0} + \frac{b}{d}k\) et \(y = {y_0} + \frac{a}{d}k\) avec \(k\)\( \in \)\(\mathbb{Z}\).

Démonstration :
On suppose à présent que \(\left. d \right|c\) et soit \(\left( {{x_0};{y_0}} \right)\) une solution particulière de l’équation.
Soit \(\left( {x;y} \right)\) une solution quelconque de l’équation. On a alors \(\left\{ {\begin{array}{*{20}{c}}{a{x_0} + b{y_0} = c}\\{ax + by = c}\end{array}} \right.\). Il vient :
\(a\left( {x – {x_0}} \right) + b\left( {y – {y_0}} \right) = 0\) et comme \(d = PGCD\left( {a;b} \right)\), on a \(a’\left( {x – {x_0}} \right) = – b’\left( {y – {y_0}} \right) = 0\).
En conséquence \(a’\left| {b’\left( {y – {y_0}} \right)} \right.\) et comme \(a’ \wedge b’ = 1\), d’après le théorème de Gauss, . Il existe alors \(k\) dans \(\mathbb{Z}\) tel que \(y = {y_0} + ka’\).\(a’\left| {\left( {y – {y_0}} \right)} \right.\)
De la même façon, on a : \(b’\left| { – {x_0} + x} \right.\) et il existe \(k’\) tel que \(x = {x_0} + b’k’\).
De l’équation \(a’\left( {x – {x_0}} \right) + b’\left( {y – {y_0}} \right) = 0\) il vient que \(k\)=\(k’\).
Notons alors \(x = {x_0} + b’k\) et \(y = {y_0} + ka’\) avec \(k\)\( \in \)\(\mathbb{Z}\).
Réciproquement,
Soit \(k\)\( \in \)\(\mathbb{Z}\) on a : \(a\left( {{x_0} – b’k} \right) + b\left( {{y_0} + a’k} \right) = c + k\left( {a’b – ab’} \right)\). Or \(a = da’\)et\(b = db’\) ce qui entraîne \(a\left( {{x_0} – b’k} \right) + b\left( {{y_0} + a’k} \right) = c + k\left( {\frac{a}{d}b – a\frac{b}{d}} \right) = c\) car \(a{x_0} + b{y_0} = c\).

 

III- Plus petit commun multiple.

1°) Existence et définition du PPCM de deux entiers strictement positifs.

Soit \(a\) et \(b\) deux entiers naturels non nuls et notons respectivement a\(\mathbb{N}\)* et b\(\mathbb{N}\)* les ensembles des multiples strictement positifs de \(a\) et de \(b\).
Exemple : \(2{\mathbb{N}^ \bullet } = \left\{ {2;4;6;8; \cdots ;2n; \cdots } \right\}\) avec \(n \in {\mathbb{N}*}\).
L’ensemble \(a{\mathbb{N}^*} \cap b{\mathbb{N}^*}\) des multiples communs aux entiers \(a\) et \(b\) est une partie de \(\mathbb{N}\) (car constitué d’entiers), n’est pas vide car il contient l’élément \(ab\) (prendre \(n\)=1).
Parmi ces multiples, il en est un qui est le plus petit ; on l’appelle \(PPCM\) des entiers \(a\) et \(b\).

Définition :
Le plus petit multiple commun des entiers naturels non nuls \(a\) et \(b\) est appelé le \(PPCM\) de \(a\) et \(b\). On le note \(PPCM(a ;b)\).

Exemple : si \(a = 3\)et \(b = 5\), on a pour  :

\(3{\mathbb{N}^ \bullet } = \left\{ {3;6;9;12;15,18, \cdots ;3n; \cdots } \right\}\) et \(5{\mathbb{N}^ \bullet } = \left\{ {5;10;15;40; \cdots ;5n; \cdots } \right\}\) or le plus petit multiple commun entre 3 et 5 est 15 donc \(PPCM\left( {3;5} \right) = 15\).

Remarque : Cette définition est intéressante mais peu efficace.

Propriétés du PPCM.

Soit \(a\) et \(b\) deux entiers naturels non nuls.

  1. Si \(b\left| a \right.\) alors \(PPCM\left( {a;b} \right) = a\) ;
  2. \(PPCM\left( {1;a} \right) = a\) et \(PPCM\left( {a;a} \right) = a\) ;
  3. Comme pour le \(PGCD\), la notion de \(PPCM\) s’étend aux entiers relatifs non nuls en posant \(PPCM\left( {a;b} \right) = PPCM\left( {\left| a \right|;\left| b \right|} \right)\).

Exemple : \(PPCM\left( {4;6} \right) = 12\).

2°) Résultats fondamentaux.

Théorème :

Soit \(a\) et \(b\) deux entiers naturels non nuls, alors :

  1. \(PGCD\left( {a;b} \right) \times PPCM\left( {a;b} \right) = ab\),
  2. Tout multiple commun à \(a\) et \(b\) est un multiple du\(PPCM\left( {a;b} \right)\) ;
  3. Pour tout entier naturel \(k\) non nul : \(PPCM\left( {ka;kb} \right) = k \times PPCM\left( {a;b} \right)\) ; ceci est la propriété multiplicative du \(PPCM\).
  4. \(m = PPCM\left( {a;b} \right)\)si et seulement si \(m = aa’\)et \(m = bb’\) avec PGCD(\(a’\)  ;\(b’\) )=1.


Démonstration de 1.
Soit \(a\) et \(b\)  deux entiers naturels non nuls avec \(d = PGCD\left( {a;b} \right)\) ; il existe alors deux entiers naturels \(a’\) et \(b’\)premiers entre eux tels que \(\left\{ {\begin{array}{*{20}{c}}{a = da’}\\{b = db’}\end{array}} \right.\).

Soit \(m\) un multiple (non nul) commun de \(a\) et \(b\). Par définition de la divisibilité, il existe deux entiers naturels \(q\) et \(p\) non nuls (puisque \(a\) et \(b\) ne sont pas nuls) tels que \(\left\{ {\begin{array}{*{20}{c}}{m = ap}\\{m = bq}\end{array}} \right.\).

Ce dernier système équivaut à \(ap = bq\) mais \(\left\{ {\begin{array}{*{20}{c}}{a = da’}\\{b = db’}\end{array}} \right.\) donc \(da’p = db’q\)avec \(d \ne 0\) d’où \(a’p = b’q\). On en déduit que \(a’\left| {b’q} \right.\) et \(PGCD\left( {a’;b’} \right) = 1\) d’après le lemme de Gauss donc il existe \(k \in {\mathbb{N}^ * }\) tel que \(q = a’k\). Avec l’égalité \(a’p = b’q\), il vient \(a’p = b’a’k\) c’est-à-dire \(p = b’k\).

Or (\(m = ap\) et \(a = da’\))\(\Rightarrow \)\(m = pda’\) et \(p = b’k\) entraînent \(\exists k \in I{N^ * }\) :\(m = da’b’k\).

En prenant \(k = 1\)(qui est la plus petite valeur), il vient \(m = da’b’\). Puisque \(d \ne 0\), en multipliant cette dernière égalité par \(q\), il vient : \(md = da’db’\) c’est-à-dire \(md = ab\).

 

IV – Congruences.

1°) Définition et premières propriétés.

Définition :
Soit \(m\) un entier naturel non nul. Deux entiers relatifs \(a\) et \(b\) sont dits congrus modulo \(m\) si \(a\) et \(b\) ont même reste dans la division euclidienne par \(m\). On note \(a \equiv b{\rm{ }}\left[ m \right]\).

Proposition 1 (ROC).
Soit \(a\) et \(b\) deux entiers relatifs et \(m\) un entier naturel non nul.
\(a\) et \(b\) ont même reste dans la division euclidienne par \(m\) si et seulement si \(a\)-\(b\) est divisible par \(m\).

Démonstration (ROC).

Soit \(a\) et \(b\) deux entiers relatifs et \(m\) un entier naturel non nul.

  • Montrons l’implication (\(\Rightarrow \))

Dans la division euclidienne \(a\) et \(b\) par m, on a : \(\left\{ {\begin{array}{*{20}{c}}{a = m{q_1} + {r_1}}\\{0 \le {r_1} < m}\end{array}} \right.\) et \(\left\{ {\begin{array}{*{20}{c}}{b = m{q_2} + {r_2}}\\{0 \le {r_2} < m}\end{array}} \right.\).

Si \(a\) et \(b\) ont même reste \(r\), on a :\(a – b = m\left( {{q_1} – {q_2}} \right)\) et prouve que\(m\left| {\left( {a – b} \right)} \right.\).

Donc, si \(a\) et \(b\) ont même reste dans la division euclidienne par \(m\) alors \(m\) divise\(a – b\).

  • Montrons l’implication (\( \Leftarrow \))

Si \(a – b\) est divisible par m, il existe un entier relatif k tel que \(a – b = km\) soit encore \(a = b + km\). En divisant b par m, il existe un unique couple d’entiers \(\left( {q’;r’} \right)\) avec \(q’ \in Z\) et\(0 \le r’ < m\) tel que\(b = mq’ + r’\).

Il vient alors\(a = \left( {k + q’} \right)m + r’\)où\(0 \le r’ < m\). Ainsi r’ est le reste de la division euclidienne de a par m. On a bien que :

Si \(a – b\) est divisible par \(m\) alors  \(a\) et \(b\) ont même reste dans la division euclidienne par \(m\).

 Conclusion : les deux implications démontrent alors l’équivalence.

Remarque importante : \(a \equiv b{\rm{ }}\left[ m \right]\) équivaut à il existe un entier \(k\) tel que \(a = b + km\).

Proposition 2 :
Soit \(a\), \(b\), \(c\) trois entiers relatifs et \(m\) un entier naturel non nul.

  1. \(a \equiv a{\rm{ }}\left[ m \right]\) (réflexivité).
  2. Si \(a \equiv b{\rm{ }}\left[ m \right]\) alors \(b \equiv a{\rm{ }}\left[ m \right]\) (symétrie).
  3. Si \(a \equiv b{\rm{ }}\left[ m \right]\) et \(b \equiv c{\rm{ }}\left[ m \right]\) alors \(a \equiv c{\rm{ }}\left[ m \right]\) (transitivité).
  4. Si \(r\) est le reste de la division euclidienne de a par \(m\) alors \(a \equiv r{\rm{ }}\left[ m \right]\).

Remarque :
Avec 1., 2. et 3. on dit que la relation de congruence est une relation d’équivalence sur \(\mathbb{Z}\).
La réciproque de 4. est fausse ; \(r\) est le reste de la division euclidienne de \(a\) par \(m\) que si \(0 \le r < m\).

Démonstration.

Soit \(a\), \(b\) et \(c\) deux entiers relatifs et \(m\) un entier naturel non nul.

  • \(\left( {a \equiv a{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {{\rm{ }}\left( {a – a} \right)} \right.} \right) \Leftrightarrow \left( {m\left| {{\rm{ 0}}} \right.} \right)\) ce qui est vrai.
  • \(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {{\rm{ }}\left( {b – a} \right)} \right.} \right) \Leftrightarrow \left( {m\left| {{\rm{ – }}\left( {a – b} \right)} \right.} \right) \Leftrightarrow \left( {m\left| {\left( {a – b} \right)} \right.} \right)\)
  • \(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {{\rm{ }}\left( {b – a} \right)} \right.} \right)\) et \(\left( {b \equiv c{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {\left( {c – b} \right)} \right.} \right)\)

donc \(\left( {m\left| {\left( {b – a + c – b} \right)} \right.} \right) \Leftrightarrow \left( {m\left| {\left( {c – a} \right)} \right.} \right) \Leftrightarrow \left( {a \equiv c{\rm{ }}\left[ m \right]} \right)\)

2°) Opérations sur les congruences.

Théorème 1 (ROC) :

Soit \(a\), \(b\), \(c\), \(a’\)et \(b’\) cinq entiers relatifs et \(m\) un entier naturel non nul.

  1. Si \(a \equiv b{\rm{ }}\left[ m \right]\) et \(a’ \equiv b'{\rm{ }}\left[ m \right]\) alors \(a + a’ \equiv b + b'{\rm{ }}\left[ m \right]\).
  2. Si \(a \equiv b{\rm{ }}\left[ m \right]\) et \(a’ \equiv b'{\rm{ }}\left[ m \right]\) alors \(aa’ \equiv bb'{\rm{ }}\left[ m \right]\).
  3. Si \(a \equiv b{\rm{ }}\left[ m \right]\)et si n est un entier naturel non nul alors \({a^n} \equiv {b^n}{\rm{ }}\left[ m \right]\)
  4. Si \(\left( {\forall c \in {Z^*}} \right)\)\(ac \equiv bc{\rm{ }}\left[ m \right]\) et si \(PGCD\left( {c;m} \right) = 1\) alors \(a \equiv b{\rm{ }}\left[ m \right]\).
  5. Si \(ac \equiv bc{\rm{ }}\left[ {cm} \right]\) alors \(a \equiv b{\rm{ }}\left[ m \right]\).


Démonstration (ROC) :

Soit \(a\), \(b\), \(a’\), \(b’\) quatre entiers relatifs et soit \(m\) un entier naturel non nul.

  1. Si \(a \equiv b{\rm{ }}\left[ m \right]\) et si \(a’ \equiv b'{\rm{ }}\left[ m \right]\), d’après la proposition,
    \(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {{\rm{ }}\left( {b – a} \right)} \right.} \right)\) et \(\left( {a’ \equiv b'{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {{\rm{ }}\left( {b’ – a’} \right)} \right.} \right)\).
    Or, d’après chapitre 1, propriété 7 sur la relation de divisibilité, si \(m\) divise \(\left( {b – a} \right)\) et \(m\) divise \(\left( {b’ – a’} \right)\) alors \(m\) divise toute combinaison linéaire formée sur \(\left( {b – a} \right)\) et \(\left( {b’ – a’} \right)\) donc \(\left( {m\left| {{\rm{ }}\left( {b – a} \right) + \left( {b’ – a’} \right)} \right.} \right)\) c’est-à-dire \(\left( {m\left| {{\rm{ }}\left( {b + b’} \right) – \left( {a + a’} \right)} \right.} \right)\) ce qui signifie que \(a + a’ \equiv b + b'{\rm{ }}\left[ m \right]\).
  2. Supposons que \(a \equiv b{\rm{ }}\left[ m \right]\) et \(a’ \equiv b'{\rm{ }}\left[ m \right]\). On a \(aa’ – bb’ = a\left( {a’ – b’} \right) + ab’ – bb’ = a\left( {a’ – b’} \right) + b’\left( {a – b} \right)\).
    Or, toujours \(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {\left( {a – b} \right)} \right.} \right)\) et \(\left( {a’ \equiv b'{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {\left( {a’ – b’} \right)} \right.} \right)\).
    Or, si \(m\) divise \(\left( {a – b} \right)\) et \(m\) divise \(\left( {a’ – b’} \right)\) alors \(m\) divise toute combinaison linéaire formée sur \(\left( {a – b} \right)\) et \(\left( {a’ – b’} \right)\) donc \(m\left| {a\left( {a’ – b’} \right) + b’\left( {a – b} \right)} \right.\) donc \(\left. m \right|aa’ – bb’\) ce qui signifie que \(aa’ \equiv bb'{\rm{ }}\left[ m \right]\).
  3. Montrons par récurrence sur l’entier naturel \(n\) non nul que :
    si\(a \equiv b{\rm{ }}\left[ m \right]\)et si n est un entier naturel non nul alors \({a^n} \equiv {b^n}{\rm{ }}\left[ m \right]\)
    Montrons la propriété au rang \(n\)=1.
    On a \({a^1} \equiv a{\rm{ }}\left[ m \right]\) et \({b^1} \equiv b{\rm{ }}\left[ m \right]\) or par hypothèse \(a \equiv b{\rm{ }}\left[ m \right]\) donc \({a^1} \equiv {b^1}{\rm{ }}\left[ m \right]\) ce qui prouve la propriété au rang \(n\)=1.
    Supposons que la propriété \({a^n} \equiv {b^n}{\rm{ }}\left[ m \right]\) est vraie pour un rang n fixé dans \(I{N^*}\)et montrons qu’elle reste vraie au rang \(n\)+1.
    Par hypothèse de récurrence, \({a^n} \equiv {b^n}{\rm{ }}\left[ m \right]\) et par hypothèse \(a \equiv b{\rm{ }}\left[ m \right]\) donc d’après la propriété multiplicative de la relation de congruence (dans Z ; confère propriété 3.)
    On a \({a^n} \times a \equiv {b^n} \times b{\rm{ }}\left[ m \right]\) c’est-à-dire \({a^{n + 1}} \equiv {b^{n + 1}}{\rm{ }}\left[ m \right]\) ce qui prouve la propriété au rang \(n\)+1.
    D’après le principe de récurrence, la propriété est vraie pour tout entier naturel \(n\) non nul.
  4. Supposons que \(ac \equiv bc{\rm{ }}\left[ m \right]\) avec c entier relatif non nul et \(PGCD\left( {c;m} \right) = 1\).
    D’après la proposition 1, \(\left( {ac \equiv bc{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {c\left( {b – a} \right)} \right.} \right)\). De plus, \(PGCD\left( {c;m} \right) = 1\). D’après le lemme de Gauss, si \(\left( {m\left| {\left( {b – a} \right)} \right.} \right)\) et \(PGCD\left( {c;m} \right) = 1\) alors \(\left( {m\left| {\left( {b – a} \right)} \right.} \right)\) et donc d’après la proposition 1, \(a \equiv b{\rm{ }}\left[ m \right]\)
    La proposition réciproque :\(\forall \left( {a,b,c,m} \right) \in {Z^3} \times I{N^*}\), \(\left( {ac \equiv bc{\rm{ }}\left[ m \right]} \right) \Rightarrow \)\(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right)\)est-elle vraie ?
    Soit \(a\) et \(b\) deux entiers relatifs et \(m\) un entier naturel non nul.
    \(\left( {a \equiv b{\rm{ }}\left[ m \right]} \right) \Leftrightarrow \left( {m\left| {\left( {b – a} \right)} \right.} \right) \Leftrightarrow \left( {\forall c \in Z,m\left| {\left( {c\left( {b – a} \right)} \right)} \right.} \right) \Leftrightarrow \left( {\forall c \in Z,m\left| {cb – ca} \right.} \right) \Leftrightarrow \left( {ac \equiv bc{\rm{ }}\left[ m \right]} \right)\) Donc la réciproque de 4. est vraie même pour \(c \in \mathbb{Z}\) et ne demande pas que\(PGCD\left( {c;m} \right) = 1\).
  5. Dans le sens direct, on prendra soin de supposer \(c\) non nul.
    Réciproque.  Si \(a \equiv b{\rm{ }}\left[ m \right]\) alors
    \(\left( {\exists k \in Z,a = b + km} \right) \Rightarrow \left( {\forall c \in Z} \right)\left( {\exists k \in Z} \right)\left( {ac = bc + cmk} \right) \Leftrightarrow \left( {ac \equiv bc{\rm{ }}\left[ m \right]} \right)\).

 

3°) Quelques applications de la congruence.

  1. Utiliser les congruences pour déterminer des restes.

On va déterminer le reste dans la division par 7 de 247349. (A faire avec eux).

Méthode :

Pour déterminer le reste de la division de ab par m :

  • On commence par chercher le reste de a dans la division euclidienne par m.
  • On utilise la propriété 3. du théorème 1.

On a 247=7´35+2 donc \(247 \equiv 2{\rm{ }}\left[ 7 \right]\) ce qui entraîne\({247^{349}} \equiv {2^{349}}{\rm{ }}\left[ 7 \right]\).

  • Ensuite, on observe les restes dans la division de \({2^{349}}\) par 7 pour trouver une éventuelle périodicité ou une relation de la forme \({2^k} \equiv 1{\rm{ }}\left[ 7 \right]\) (ce n’est pas toujours possible !).

\({2^1} \equiv 1{\rm{ }}\left[ 7 \right]\), \({2^2} \equiv 4{\rm{ }}\left[ 7 \right]\), \({2^8} \equiv 1{\rm{ }}\left[ 7 \right]\) Comme la suite des restes est périodique de période 3, on effectue donc la division euclidienne de 349 par 3 ce qui donne 349=3´116+1 d’où \({2^{349}} \equiv {\left( {{2^3}} \right)^{116}} \times {2^1}{\rm{ }}\left[ 7 \right]\) soit \({2^{349}} \equiv 2{\rm{ }}\left[ 7 \right]\)

Le reste dans la division euclidienne de 247349 par 7 est 2.