PGCD et nombres premiers

Il y a plusieurs façons de procéder : on peut soit tester toutes les possibilités (16 au total) de nombres \(b\) pour que \(5b\equiv 1[16]\), ce qui va assez vite, soit utilise l'algorithme d'Euclide renversé tel que vu précédemment pour trouver les coefficients de Bézout. On peut aussi remarquer que \(16-3\times15 = 1\)

Un inverse de 5 modulo 16 est -3.

On multiplie les deux membres par -3 qui est un inverse de 5 module 16 :

\(−3 × 5x \equiv −3 × 7[16]\)

donc \(x\equiv -21\equiv 11[16]\)

Les solutions sont du type \(x=11+16k, k\in\mathbb Z\)