L'algorithme d'Euclide permet de trouver une solution de l'équation.

Ici $\left(1; 1\right)$ est une solution évidente.

Soit $\left(x;y\right)$ une solution de (E) :

$8x - 5y=3\Leftrightarrow 8x - 5y=8\times 1 - 5\times 1\Leftrightarrow 8\left(x - 1\right)=5\left(y - 1\right)$

8 divise $5\left(y - 1\right)$ et est premier avec 5, donc d'après le théorème de Gauss, 8 divise $y - 1$.

Posons $y - 1=8k$ avec $k\in \mathbb{Z}$ alors $x - 1=5k$ donc :

$y=1+8k$ et $x=1+5k$

Réciproquement on vérifie que tout couple de la forme $\left( 1+5k, 1+8k \right)$ est solution de (E) :

$8\left(1+5k\right) - 5\left(1+8k\right)=3$

L'ensemble des solutions entières de (E) est donc:

$S=\left\{\left( 1+5k, 1+8k \right)\ ;\ k\in \mathbb{Z}\right\}$

Par hypothèse $8p+1=5q+4$ donc $8p - 5q=1$. $\left(p; q\right)$ est donc solution de (E)

D'après le a. on en déduit que :

$m=8p+1=8\left(1+5k\right)+1=40k+9$

donc $m\equiv 9\ \left(\text{mod.}40\right)$

Posons $N=2000+k$ avec $k\in \mathbb{N}$

$N\equiv 9\ \left(\text{mod.}40\right) \Leftrightarrow 2000+k\equiv 9\ \left(\text{mod.}40\right) \Leftrightarrow k\equiv 9 \ \left(\text{mod.}40\right)$

car 2000 est divisible par 40. Le plus petit entier positif $k$ possible est donc 9 et la plus petite valeur de $N$ est 2009

$2^{3}=8$ donc

$2^{3}\equiv 1\ \left(\text{mod.}7\right)$

donc pour tout entier naturel $k$ en élevant à la puissance $k$ :

$2^{3k}\equiv 1\ \left(\text{mod.}7\right)$

La division euclidienne de 2009 par 3 donne :

$2009=3\times 669+2$

Donc

$2^{2009}=2^{3\times 669+2}=\left(2^{3}\right)^{669}\times 2^{2}$

D'après la question pécédente:

$2^{2009}\equiv 1\times 2^{2}\equiv 4\ \left(\text{mod.}7\right)$

Le reste de la division euclidienne de $2^{2009}$ par 7 est donc 4.

$10^{3}=1000=142\times 7+6=142\times 7+7 - 1=143\times 7 - 1$

Donc $10^{3}\equiv - 1\ \left(\text{mod.}7\right)$

On déduit de la question précédente que

$a\times 10^{3}+b\equiv b - a\ \left(\text{mod.}7\right)$

Donc $a\times 10^{3}+b$ est divisible par 7 si et seulement si $b - a\equiv 0\ \left(\text{mod.}7\right)$

Comme $1\leqslant a\leqslant 9$ et $0\leqslant b\leqslant 9$ : $- 9\leqslant b - a\leqslant 8$.

Les seules solutions possibles sont donc : $b - a= - 7$; $b - a=0$; $b - a=7$, ce qui donne les nombres:

7000; 8001; 9002; 1001; 2002; 3003; 4004; 5005; 6006; 7007; 8008; 9009; 1008; 2009

Réciproquement, on vérifie que chacun de ces quatorze nombres est divisible par 7.