Plus petit commun multiple et plus grand commun diviseur de deux entiers relatifs

Exercice 3 — PGCD et PPCM

Déterminer $\text{pgcd}(391,299)$ par l'algorithme d'Euclide, puis en déduire $\text{ppcm}(391,299)$.

Exercice 4 — Identité de Bézout

En utilisant l'algorithme d'Euclide, déterminer un couple d'entiers $(u,v)$ tel que $253u+161v=\text{pgcd}(253,161)$.

Exercice 5 — Équation diophantienne

Résoudre dans $\mathbb{Z}^2$ l'équation $7x-4y=3$.

À l'entrée d'un port de pêche, deux balises lumineuses émettent chacune un éclat bref à intervalles réguliers : la balise A toutes les 56 secondes, la balise B toutes les 44 secondes. Un pêcheur chronomètre les éclats à partir d'un instant noté 0, en secondes.

1) Calcule \(\mathrm{PGCD}(56\,;44)\) par l'algorithme d'Euclide, puis déduis-en \(\mathrm{PPCM}(56\,;44)\).

2) On suppose d'abord que les deux balises émettent ensemble à l'instant 0. Justifie que les éclats simultanés suivants ont lieu aux instants multiples de 616, puis dis combien d'éclats simultanés le pêcheur observe pendant l'heure qui suit l'instant 0.

3) Après un réglage, la balise A émet aux instants 0, 56, 112, et ainsi de suite, tandis que la balise B émet son premier éclat à l'instant 12, puis toutes les 44 secondes. Démontre que les deux balises émettent ensemble si, et seulement si, il existe deux entiers naturels \(x\) et \(y\) tels que \(14x-11y=3\).

4) Vérifie que le couple \((1\,;1)\) est solution de l'équation \(14x-11y=3\), puis résous cette équation dans l'ensemble des couples d'entiers relatifs, à l'aide du théorème de Gauss.

5) Déduis-en l'instant du premier éclat simultané et celui du suivant. Interprète l'écart entre ces deux instants.

6) Si la balise B émettait son premier éclat à l'instant 10 au lieu de l'instant 12, les deux balises émettraient-elles ensemble un jour ? Justifie.

Dans tout l'exercice, \(a\) et \(b\) sont deux entiers naturels non nuls tels que \(a\leq b\). On note \(d\) leur PGCD et \(m\) leur PPCM. Comme \(d\) divise \(a\) et \(b\), il existe deux entiers naturels non nuls \(a'\) et \(b'\) tels que \(a=da'\) et \(b=db'\).

1) Démontre que \(a'\) et \(b'\) sont premiers entre eux, puis que \(m=da'b'\).

2) Détermine tous les couples \((a\,;b)\) tels que \(d=12\) et \(m=504\).

3) Parmi les couples trouvés, lequel vérifie de plus \(a+b=156\) ? Justifie qu'il est le seul.

4) On cherche maintenant les couples \((a\,;b)\) tels que \(m-5d=14\). Démontre que \(d\) divise 14 et donne les valeurs possibles de \(d\).

5) Pour chaque valeur possible de \(d\), calcule le produit \(a'b'\), puis détermine tous les couples \((a\,;b)\) tels que \(m-5d=14\).

Pour tout entier naturel \(n\), on pose \(a_n=7n+4\) et \(b_n=3n+1\), et on note \(d_n\) le PGCD de \(a_n\) et \(b_n\). On veut savoir pour quelles valeurs de \(n\) la fraction \(\dfrac{7n+4}{3n+1}\) est irréductible.

1) Calcule \(d_1\), \(d_2\) et \(d_3\) par l'algorithme d'Euclide.

2) Démontre que tout diviseur commun à \(a_n\) et \(b_n\) divise 5. Quelles sont les valeurs possibles de \(d_n\) ?

3) Résous dans l'ensemble des entiers relatifs l'équation \(3n\equiv 4\ [5]\).

4) Déduis-en la valeur de \(d_n\) selon l'entier naturel \(n\), puis les valeurs de \(n\) pour lesquelles la fraction est irréductible.

5) Écris sous forme irréductible la fraction obtenue pour \(n=2\,023\), en justifiant que la fraction trouvée ne peut plus être simplifiée.

On considère la suite \((u_n)\) définie pour tout entier naturel \(n\) par \(u_n=3^n+5^n\). On s'intéresse au PGCD et au PPCM de deux termes consécutifs \(u_n\) et \(u_{n+1}\).

1) Calcule \(u_0\), \(u_1\), \(u_2\) et \(u_3\), puis détermine \(\mathrm{PGCD}(u_1\,;u_2)\) et \(\mathrm{PGCD}(u_2\,;u_3)\) par l'algorithme d'Euclide. Quelle conjecture peux-tu faire ?

2) Démontre, à l'aide des congruences, que \(u_n\) est pair pour tout entier naturel \(n\).

3) Démontre que, pour tout entier naturel \(n\), \(u_{n+1}-3u_n=2\times 5^n\) et \(u_{n+1}-5u_n=-2\times 3^n\).

4) On note \(d\) le PGCD de \(u_n\) et \(u_{n+1}\). Justifie que \(3^n\) et \(5^n\) sont premiers entre eux, puis démontre, à l'aide du théorème de Bézout, que \(d\) divise 2. Conclus sur la valeur de \(d\).

5) Déduis-en l'expression de \(\mathrm{PPCM}(u_n\,;u_{n+1})\) en fonction de \(u_n\) et \(u_{n+1}\), puis calcule \(\mathrm{PPCM}(u_2\,;u_3)\).