Étape 1
Soit $k$ un entier naturel non nul. On pose $a = 15k + 7$ et $b = 4k + 1$. Pour déterminer l'ensemble des diviseurs communs possibles à $a$ et $b$, cherchons une combinaison linéaire de ces deux nombres qui ne dépend pas de $k$.
Étape 2
On calcule la combinaison linéaire suivante : $$4a - 15b = 4(15k + 7) - 15(4k + 1)$$ $$4a - 15b = 60k + 28 - 60k - 15 = 13$$
Étape 3
Tout diviseur commun à $a$ et $b$ divise également toute combinaison linéaire de $a$ et $b$. Ainsi, tout diviseur commun à $a$ et $b$ divise $13$. Comme $13$ est un nombre premier, le plus grand commun diviseur de $a$ et $b$ est nécessairement égal à $1$ ou à $13$.
Étape 4
Les entiers $a$ et $b$ ne sont pas premiers entre eux si et seulement si leur plus grand commun diviseur est égal à $13$, ce qui signifie que $13$ divise à la fois $a$ et $b$.
Étape 5
D'après l'égalité $4a - 15b = 13$, si $13$ divise $b$, alors $13$ divise $4a = 15b + 13$. De plus, comme $13$ et $4$ sont premiers entre eux, d'après le théorème de Gauss, $13$ divise $a$. Par conséquent, $13$ divise $a$ et $b$ si et seulement si $13$ divise $b$.
Étape 6
La condition « $13$ divise $b$ » traduit la congruence suivante : $$4k + 1 \equiv 0 \pmod{13}$$ ce qui équivaut à $4k \equiv -1 \pmod{13}$, soit $4k \equiv 12 \pmod{13}$.
Étape 7
Cette congruence s'écrit aussi $4(k - 3) \equiv 0 \pmod{13}$, soit $13$ divise $4(k - 3)$. Comme $13$ et $4$ sont premiers entre eux, le théorème de Gauss implique que $13$ divise $k - 3$, d'où : $$k \equiv 3 \pmod{13}$$
Étape 8
Les entiers $k$ recherchés sont donc de la forme $k = 13m + 3$ où $m$ est un entier naturel. On cherche la plus petite valeur de $k$ strictement supérieure à $100$, ce qui conduit à l'inégalité : $$13m + 3 > 100$$ d'où $13m > 97$, soit $m > \frac{97}{13} \approx 7{,}46$.
Étape 9
Le plus petit entier $m$ convenant est $m = 8$. On en déduit la valeur finale de $k$ : $$k = 13 \times 8 + 3 = 107$$ Le plus petit entier $k > 100$ tel que $a$ et $b$ ne soient pas premiers entre eux est $107$.
Méthode clé
Éliminer le paramètre $k$ par combinaison linéaire pour déterminer les diviseurs communs possibles, puis résoudre la condition de divisibilité par congruence.
Piège à éviter
Tester les valeurs de $k$ une par une au lieu d'utiliser une combinaison linéaire éliminant $k$.
