]> AND Private Git Repository - hdrcouchot.git/blob - talk/q4.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
la veille
[hdrcouchot.git] / talk / q4.tex
1 A la ligne~204, on prétend savoir calculer 
2 \og l'inverse de $x_i-x_{i+1}$ modulo $m$\fg{}. Comment faire ceci? Ce problème a-t-il toujours une solution?
3
4 Réponses:
5 Il s'agit d'appliquer l'algorithme d'Euclide étendu: on cherche $u$ (et $v$)
6 tels que $(x_i-x_{i+1}).u + m.v = 1$. Or ceci n'admet une solution que si 
7 $(x_i-x_{i+1})$ et $m$ sont premiers entre-eux. 
8 (Par exemple, impossible de trouver l'inverse de 
9 2 modulo 6).