Petit devoir PGCD et Bézout

Les détails des calculs sont attendus.

L'usage de la calculatrice est autorisé.

Durée : 30 minutes

Exercice 1 (3 points)

1. À l'aide de l'algorithme d'Euclide, déterminer \(PGCD(a,b)\) avec \(a=18480\) et \(b=9828\).

   Corrigé

   \(18480=1 \times 9828+8652\)

   \(9828=1 \times 8652+1176\)

   \(8652=7 \times 1176+420\)

   \(1176=2 \times 420+336\)

   \(420=1 \times 336+84\)

   \(336=4 \times 84+0\)

   D'après l'algorithme d'Euclide ci-dessus, le dernier reste non nul est \(84\) donc \(PGCD(18480,9828)=84\)

2. En déduire un diviseur de \(a\) et un diviseur de \(b\) qui sont premiers entre eux.

   Corrigé

   D'après ce qui précède \(\dfrac{18480}{84}=220\) et \(\dfrac{9828}{84}=117\) sont premiers entre eux.

Exercice 2 (4 points)

Montrer que \(313\) et \(231\) sont premiers entre eux, puis déterminer un couple d'entiers relatifs \((x;y)\) tels que:

\[231x-313y=1\]

Corrigé

\(313=1 \times231+82\)

\(231=2 \times 82+67\)

\(82=1 \times 67+15\)

\(67=4 \times 15+7\)

\(15=2 \times 7+1\)

\(7=7 \times 1+0\)

D'après l'algorithme d'Euclide ci-dessus, le dernier reste non nul est \(1\) donc \(PGCD(313,231)=1\)

On utilise ensuite la méthode de Lamé-Lucas:

restes	u	v	relation
313	1	0	\(313=1\times313+0\times 231\)
231	0	1	\(231=0\times313+1\times 231\)
82	1	-1	\(82=1\times313+(-1)\times 231\)
67	-2	3	\(67=(-2)\times313+3 \times 231\)
15	3	-4	\(15=3 \times 313+(-4) \times 231\)
7	-14	19	\(7=(-14) \times 313+19 \times 231\)
1	31	-42	\(1=31 \times 313+(-42) \times 231\)

Le couple \((-42;-31)\) est donc une solution de \(231x-313y=1\).

Exercice 3 (3 points)

Les propositions suivantes sont-elles vraies ou fausses ? Justifier.

1. S'il existe deux entiers relatifs \(u\) et \(v\) tels que \(au+bv=5\), alors \(PGCD(a,b)=5\).

   Corrigé

   On a \(9\times1+4\times(-1)=5\) et pourtant \(9\) et \(4\) sont premiers entre eux. FAUX

2. Si on a deux entiers naturels \(m\) et \(n\) tels que \(PGCD(m,n)=7\) et \(mn=588\) alors il existe deux entiers naturels \(m'\) et \(n'\) qui divisent respectivement \(m\) et \(n\) tels que \(m'n'=12\)

   Corrigé

   Si \(PGCD(m,n)=7\) alors \(m\) et \(n\) sont divisibles par 7 et il existe donc \(m'\) et \(n'\) tels que \(m=7m'\) et \(n=7n'\) d'où \(mn=588=7 \times 7 \times m'n'\) et \(m'n'=\dfrac{588}{49}=12\). VRAI

3. Si \(a^2\) et \(b^2\) sont premiers entre eux, alors \(a\) et \(b\) sont premiers entre eux.

   Corrigé

   D'après Bézout, si \(a^2\) et \(b^2\) sont premiers entre eux, alors il existe u et v des nombres relatifs tels que:

   \[a^2u+b^2v=1\]

   Or, on peut récrire : \(a(au)+b(bv)=1\), et donc, d'après Bézout, \(a\) et \(b\) sont premiers entre eux.