PGCD de deux expressions et fraction irréductible (Olympiade 1959)

1) \(d\) divise \(a - b\) et \(ka\)

\(d\) divise \(a\) et \(b\) : il existe deux entiers naturels \(a'\) et \(b'\) tels que \(a = d\,a'\) et \(b = d\,b'\). Comme \(a \geq b\), on a \(a' \geq b'\) et :

\[a - b = d\,a' - d\,b' = d(a' - b')\]

Donc \(d\) divise \(a - b\). De même, \(ka = d \times (k a')\), donc \(d\) divise \(ka\).

2) a) \(\mathrm{PGCD}(n\,;n + 1) = 1\)

Soit \(d\) un diviseur commun de \(n\) et \(n + 1\). D’après 1), \(d\) divise la différence :

\[(n + 1) - n = 1\]

Donc \(d = 1\). Le seul diviseur commun de \(n\) et \(n + 1\) est \(1\), donc \(\mathrm{PGCD}(n\,;n + 1) = 1\).

b) \(\mathrm{PGCD}(2n + 1\,;3n + 1) = 1\)

Soit \(d\) un diviseur commun de \(2n + 1\) et \(3n + 1\). D’après 1) :

• \(d\) divise \(3(2n + 1) = 6n + 3\) ;
• \(d\) divise \(2(3n + 1) = 6n + 2\).

Donc \(d\) divise la différence :

\[(6n + 3) - (6n + 2) = 1\]

D’où \(d = 1\), et \(\mathrm{PGCD}(2n + 1\,;3n + 1) = 1\).

Méthode : on multiplie chaque nombre par un coefficient bien choisi pour faire disparaître \(n\) dans la différence.

3) a) Calcul de \(3b - 2a\)

\[\begin{aligned} &3b - 2a \\ &= 3(14n + 3) - 2(21n + 4) \\ &= 42n + 9 - 42n - 8 \\ &= 1 \end{aligned}\]

b) \(\mathrm{PGCD}(a\,;b)\)

Soit \(d\) un diviseur commun de \(a\) et \(b\). Alors \(d\) divise \(3b\) et \(2a\), donc \(d\) divise \(3b - 2a = 1\). D’où \(d = 1\) et :

\[\mathrm{PGCD}(a\,;b) = 1\]

c) La fraction est irréductible

Le numérateur et le dénominateur n’ont aucun diviseur commun autre que \(1\) : on ne peut donc pas simplifier la fraction. Pour tout entier naturel \(n\), la fraction \(\dfrac{21n + 4}{14n + 3}\) est irréductible.

Exemple : pour \(n = 10\), la fraction \(\dfrac{214}{143}\) est irréductible.

Remarque : cette question est le premier problème posé aux Olympiades internationales de mathématiques, en 1959.