Correction exercice I

1. Soient \(a\) et \(b\) deux entiers naturels non nuls et \(\mu \) leur \(PPMC\), démontrons que \(a\) \( \mathbb{Z}\) \( \cap \) \(b\)\( \mathbb{Z}\) = \(\mu \) \( \mathbb{Z}\)
Soit \(k\) un élément de \(a\) \( \mathbb{Z}\) \( \cap \) \(b\)\( \mathbb{Z}\)
Désignons par \(q\) et \(r\) le quotient et le reste de la division euclidienne de \(k\) et \(\mu \), on \(r = k\) \( - \mu q\)
\(k\) et \(\mu \) sont des multiples communs à \(a\) et \(b\) ; donc \(r \in \) \(a\) \( \mathbb{Z}\) \( \cap \) \(b\)\( \mathbb{Z}\)
De plus, \(\mu \)est le plus petit élément strictement positif de \(a\) \( \mathbb{Z}\) \( \cap \) \(b\)\( \mathbb{Z}\) et \(0 \le r \prec \mu \) ; donc \(r = 0\).
On en déduit que : \(k \in \mu \)
Donc \(a\) \( \mathbb{Z}\) \( \cap \) \(b\) \( \mathbb{Z}\) \( \subset \mu \) \( \mathbb{Z}\)
On a : \(\mu \) \( \mathbb{Z}\) \( \subset a\) \( \mathbb{Z}\) \( \cap b\) \( \mathbb{Z}\) et \(a\) \( \mathbb{Z}\) \( \cap \) \(b\) \( \mathbb{Z}\) \( \subset \mu \) \( \mathbb{Z}\) donc \(\mu \) \( \mathbb{Z}\) = \(a\) \( \mathbb{Z}\) \( \cap \) \(b\) \( \mathbb{Z}\)
2. Soient \(a\), \(b\) et \(k\) trois entiers naturels non nuls, démontrons que \(PPMC\left( {ka,kb} \right)\) \( = kPPMC\left( {a,b} \right)\)
En effet, posons \(\mu = PPMC\left( {a,b} \right)\) et \({\mu _1} = \) \(PPMC\left( {ka,kb} \right)\)
Il existe deux entiers naturels non nuls \(a’\) et \(b’\) tels que \(\mu = aa'\) et \(\mu = bb'\)
On a : \(k\mu = kaa'\) et \(k\mu = kbb'\); donc \(k\mu \ge {\mu _1}\)
Il existe deux entiers naturels non nuls \(a’ ;\) et \(b’’\) tels que \({\mu _1}\) \(= kaa'’\) et \({\mu _1}\) \(= kbb'’\)
On a : \(aa'' = bb''\); \(aa''\) est multiple commun à \(a\) et \(b\) donc \(aa'' \ge \mu \).
On en déduit que \({\mu _1} \ge k\mu \) donc \(PPMC\left( {ka,kb} \right) = \) \(kPPMC\left( {a,b} \right)\).
3. Pour tous entiers relatifs non nuls \(a\) et \(b\) et \(\delta \) leur PGCD. Demontrons que \(d\left( {a; b} \right) = \) \(d\left( \delta \right)\).
• Soit \(d\) un élément de \(d\left( \delta \right)\).
\(d\) divise \(\delta \) et \(\delta \) divise \(a\) et \(b\) ; donc \(d\) divise \(a\) et \(b\).
Tout diviseur de \(\delta \) divise \(a\) et \(b\) ; donc \(d\left( \delta \right) \subset d\left( {a;b} \right)\).
Soit \(d\) un élément de \(d\left( {a;b} \right)\)
Désignons par \(\mu \) le PPCM de \(d\) et \(\delta \) ; \(\delta \le \mu \).
\(a\) est un multiple de \(d\) et de \(\delta \), donc \(a\) est un multiple de \(\mu \). De même \(b\) est un multiple de \(\mu \).
\(\mu \) divise \(a\) et \(b\), donc \(\mu \le \delta \)
On a \(PPCD\left( {d;\delta } \right)\) \( = \delta \); donc \(d\) divise \(\delta \); c’est-à-dire \(d \in d\left( \delta \right)\)
On en déduit que : \(d\left( {a;b} \right) = d\left( \delta \right)\)
4. Soient \(a\) et \(b\) deux entiers naturels non nuls et \(\delta \) leur PGCD
Un entier relatifs \(m\) est un multiple de \(\delta \) démontrer qu’il existe deux entiers relatifs \(u\) et \(v\) tels que \(m = au + bv\).
En effet, soient \(u\) et \(v\) deux entiers relatifs. Si \(av\) et \(bv\) sont multiple de \(\delta \) alors \(au+bv\) est multiple de \(\delta \).
Considérons l’ensemble A des entiers naturels qui peuvent s’écrire sous la forme \(au+bv\) avec \(u \in \) \( \mathbb{Z}\) et \(v \in \) \( \mathbb{Z}\). On a : \(a = a \times 1 + \) \(a \times 0\) ; donc \(a \in A\)
A étant une partie non vide de \( \mathbb{N}\), elle admet donc un plus petit élément \(p\)
Il existe deux partie entiers relatifs \(u’\) et \(v’\) tels que \(p=au’+bv’\).
Donc \(r = a\left( {1 - qu'} \right)\) \( + b\left( { - qv'} \right)\); \(r\) est de la forme \(au+bv\).
\(r\) était non nul, il serait un element de A strictement inferieur aa \(p\). donc \(r=0\) et \(p\) divise \(a\).
De même, \(p\) divide \(b\) ; donc \(p\) divise \(\delta \). Or, \(p\) est multiple de \(\delta \) ; donc \(p = \delta \)
Soit \(m\) un multiple de \(\delta \).
Il existe un entier relatifs \(k\) tel que \(m = k\delta \Rightarrow \) \(m = a\left( {ku'} \right)\) \( + b\left( {kv'} \right)\)

Correction exercice II
Déterminons les entiers naturels \(a\) et \(b\) dans chacun des cas suivants :
a) \(\left\{ \begin{array}{l}a + b = 168\\PGCD\left( {a;b} \right) = 21\end{array} \right.\) ;
Soient \(a’\) et \(b’\) deux entiers non nul tel que \(a = a'd\) et \(b = b'd\) avec \(PGCD\left( {a';b'} \right) = 1\)
Posons \(PGCD\left( {a;b} \right) = \) \(21 = d\). Ainsi le systeme precedent deviant :
\(\left\{ \begin{array}{l}a'd + b'd = 168\\d = 21\end{array} \right.\) \( \Rightarrow \left\{ \begin{array}{l}a' + b' = 8\\d = 21\end{array} \right.\)
Puisque \(PGCD\left( {a';b'} \right) = 1\) alors \(\left( {a';b'} \right) \in \) \(\{ \left( {3;5} \right);\left( {5;3} \right);\) \(\left( {7;1} \right);\left( {1;7} \right)\} \)
Ainsi : \(\left\{ \begin{array}{l}a' = 5\\b' = 3\end{array} \right. \Rightarrow \) \(\left\{ \begin{array}{l}a = 105\\b = 63\end{array} \right. \Rightarrow \) \({S_1} = \left\{ {\left( {105;63} \right)} \right\}\)
\(\left\{ \begin{array}{l}a' = 3\\b' = 5\end{array} \right. \Rightarrow \) \(\left\{ \begin{array}{l}a = 63\\b = 105\end{array} \right. \Rightarrow \) \({S_2} = \left\{ {\left( {63;105} \right)} \right\}\)
\(\left\{ \begin{array}{l}a' = 7\\b' = 1\end{array} \right. \Rightarrow \) \(\left\{ \begin{array}{l}a = 147\\b = 21\end{array} \right. \Rightarrow \) \({S_3} = \left\{ {\left( {147;21} \right)} \right\}\)
\(\left\{ \begin{array}{l}a' = 1\\b' = 7\end{array} \right. \Rightarrow \) \(\left\{ \begin{array}{l}a = 21\\b = 147\end{array} \right. \Rightarrow \) \({S_4} = \left\{ {\left( {21;147} \right)} \right\}\)
\(S = \{ \left( {105;3} \right);\) \(\left( {63;105} \right);\) \(\left( {147;21} \right);\) \(\left( {21;147} \right)\} \)
b) \(\left\{ \begin{array}{l}m + 3\Delta = 276\\10 \prec \Delta \prec 30\end{array} \right.\) ;
Cherchons tout d’abord les diviseurs de 276
\(d\left( {276} \right) = \{ 1;2;\) \(3;4;6;12;23;\) \(46;69\} \)
Soient \(a\) et \(b\) deux entiers non nuls. Si \(\Delta \) et \(m\) désignent respectivement le PGCD et PPCM des entiers naturels \(a\) et \(b\), on a : \(a \times b = m \times \Delta \)
Ainsi il existe deux entiers \(a’\) et \(b’\) premiers entre eux \(PGCD\left( {a';b'} \right)\) \( = 1\) tel que : \(\left\{ \begin{array}{l}a = a'\Delta \\b = b'\Delta \end{array} \right. \Rightarrow \) \(ab = {\Delta ^2} \times a'b'\) \( \Rightarrow m = \Delta \times a'b'\)
Alors le système devient : \(\left\{ \begin{array}{l}\Delta \times a'b' + 3\Delta = 276\\0 \prec \Delta \prec 30\end{array} \right.\) \( \Rightarrow \) \(\left\{ \begin{array}{l}a'b' + 3 = \frac{{276}}{\Delta }\\0 \prec \Delta \prec 30\end{array} \right.\)
Or \(0 \prec \Delta \prec 30 \Leftrightarrow \) \(\Delta \in \left\{ {12;23} \right\}\) car l’ensemble des diviseurs de 276 comprises entre 0 et 30 sont : 12 et 23
1er cas \(\Delta = 12\) \( \Rightarrow a'b' = 20\)
Puisque \(PGCD\left( {a';b'} \right) = 1\) alors \(\left( {a';b'} \right) \in \{ \left( {4;5} \right)\) \(;\left( {5;4} \right);\left( {20;1} \right);\) \(\left( {1,20} \right)\} \)
\(\left\{ \begin{array}{l}a = 12a'\\b = 12b'\end{array} \right.\)
\(S’ = \{ \left( {48;60} \right);\) \(\left( {60;48} \right);\left( {240;12} \right);\) \(\left( {12,240} \right)\} \)
2er cas \(\Delta = 23\) \( \Rightarrow a'b' = 9\)
\(S'' = \{ \left( {207;23} \right);\) \(\left( {23;207} \right)\} \)
\(S = S' \cap S''\)
c) \(\left\{ \begin{array}{l}{a^2} - {b^2} = 405\\3m = a \bullet b\end{array} \right.\).
\(S = \{ \left( {69;66} \right)\) \(;\left( {7;6} \right)\} \)

Correction exercice III
En utilisant le tableau d’Algorithme, déterminons le PGCD des entiers \(a\) et \(b\) dans chacun des cas suivants :
a) \(\left\{ \begin{array}{l}a = 1455\\b = 335\end{array} \right.\) ;

Ici le dernier reste non nul est 5. D’où PGCD( 1455 ; 335 ) = 5
b) \(\left\{ \begin{array}{l}a = 46\\b = 43\end{array} \right.\).

Ici le dernier reste non nul est 1. D’où PGCD (1455 ; 335) = 1
c) \(\left\{ \begin{array}{l}a = 304939\\b = 151097\end{array} \right.\).

Ici le dernier reste non nul est 0. D’où PGCD (304939 ; 151097) = 61.

Correction exercice IV
Déterminons le PGCD des nombres suivants et en déduire leurs PPCM
a) \(\left\{ \begin{array}{l}a = 168\\b = 96\end{array} \right.\) ;
\(PGCD\left( {168;96} \right)\) \( = 24\)
\(PPCM\left( {168;96} \right) = \) \(\frac{{168 \times 96}}{{PGCD\left( {168;96} \right)}}\) \( = \frac{{168 \times 96}}{{24}}\) \( = 672\)
b) \(\left\{ \begin{array}{l}a = 385\\b = 324\end{array} \right.\)
\(PGCD\left( {385;324} \right)\) \( = 1\)
\(PPCM\left( {385;324} \right) = \) \(\frac{{385 \times 324}}{1}\) \( = 124740\)