PGCD et nombres premiers

Il s'agit ici d'une application immédiate du petit théorème de Fermat, puisque 31 est un nombre premier et que 31 et 5 sont premiers entre eux.

Multiplions la relation précédente par 28, cela nous donne une solution particulière de (E) :

\(28\times 5^{30} \equiv 28[31]\) et donc \(5\times 28\times 5^{29}\equiv 28[31]\)

Il nous faut à présent simplifier \(28\times 5^{29}\) en remarquant que \(29=9\times 3 + 2\) et \(5^3\equiv 1[31]\)

On a alors \(28\times 5^29 = 28\times (5^3)^9\times 5^2 \equiv 28\times 25[31]\) puisque \((5^3)^9\equiv 1^9[31]\)

Il reste à calculer \(700[31]\equiv 18[31]\) pour en déduire \(x_0=18\)

\(x\) solution de (E) si et seulement si \(5x\equiv 28[31]\) ou encore \(5x\equiv 5\times 18 [31]\)

Donc \((E) \Longleftrightarrow 5(x-18)\equiv 0[31] \Longleftrightarrow 5(x-18)=31k\) où \(k\in\mathbb Z\)

5 divise \(31k\) et 5 premier avec 31 donc \(5\) divise \(k\). On en conclut que \(x-18 = 31a\) où \(a\in \mathbb Z\)

Les solutions sont donc de la forme \(x=18+31k\) avec \(k\in \mathbb Z\)