>>296
そこは d, e, φ と u, v の関係の説明がないところが不親切。
下のプログラム見て考えてくれ。

/* gcd(e,phi)=1 のとき、d*e≡1 (mod phi) なる d を返す */
int d(int e, int phi)
{
int u1=1, u2=e, u3=0, v1=0, v2=phi, v3=1, t1, t2, t3, q;
while (v2 > 0) {
q = u2/v2;
t1 = u1 - v1*q; t2 = u2 - v2*q; t3 = u3 - v3*q;
u1 = v1; u2 = v2; u3 = v3;
v1 = t1; v2 = t2; v3 = t3;
}
return u1;
}