Exercice : Divisibilité et division euclidienne dans ℤ

Étape 1

Soit $N = 10a + b$. On exprime la quantité $10(a + kb)$ en fonction de $N$ : $$10(a + kb) = 10a + 10kb = (10a + b) + (10k - 1)b = N + (10k - 1)b$$

Étape 2

Comme les entiers $10$ et $17$ sont premiers entre eux ($\text{PGCD}(10, 17) = 1$), le lemme de Gauss assure que $17$ divise $a + kb$ si et seulement si $17$ divise $10(a + kb)$.

Étape 3

Ainsi, $17$ divise $N$ si et seulement si $17$ divise $a + kb$ pour tout entier $b$, ce qui équivaut à exiger que $17$ divise $10k - 1$, soit : $$10k \equiv 1 \pmod{17}$$

Étape 4

On cherche donc un entier $k \in \{1, \dots, 16\}$ tel que $10k - 1$ soit un multiple de $17$. En examinant les multiples successifs de $17$ augmentés de $1$, on observe que : $$17 \times 7 + 1 = 119 + 1 = 120$$ Comme $120 = 10 \times 12$, la valeur cherchée est $k = 12$.