# Inverse modulaire d'un entier a pour la multiplication modulo n
proc invmod {a n} {
set n0 $n
set x0 0
set x1 1
if {$n == 1} {return 1}
while {$a > 1} {
set q [expr {$a / $n}]
set t $n
set n [expr {$a % $n}]
set a $t
set t $x0
set x0 [expr {$x1 - $q*$x0}]
set x1 $t
}
if {$x1 < 0} {incr x1 $n0}
return $x1
}