How to efficiently compute $(\frac{x}{x_i})^{-1} \mod x_i$ for $i = 1, \ldots, n$?
Suppose $x = \prod_{i=1}^n x_i$ for co-prime integers $x_i$ and $x_j$ ($i \neq j$).
We want to compute $y_i=((\frac{x}{x_i})^{-1} \mod x_i)$ for $i=1,\ldots,n$.
The naive solution to this approach is computing $a_i = \frac{x}{x_i} = \prod_{j\neq i}^n x_j$ first. Then, apply $a^{-1}\mod x_i$.
Is it possible to compute $y_i$ via $\prod_{j\neq i}(x_j^{-1} \mod x_i) $??
When each $x_i$ is single-word size (say, within 64-bit). The latter approach allows us not to use multi-precision library :)
The bezout's Theorem gives an efficient method to compute inverse:
Let $a,b$ two numbers with $(a,b)=1$. Then exists $b^{-1}$ over $\mathbb{Z}_a$.
Bezout caims: $$\exists m,n\mbox{ such that } am+bn=1$$
Then if you take $\mod(a)$ you get:
$$bn\equiv 1 \mod(a)$$
Now the question is:
How to determine such n?
This comes from Euclidean algorithm:
$r_0=a=bq_0+r_2$
$r_1=b=r_2q_1+r_3$
$r_2=r_3q_1+r_4$ and so on ;)