Inverse of an integer computed with CRT

269 Views Asked by At

Suppose I have prime numbers $p_1...p_n$ and $x_0 = \prod_{i=1}^n p_i$. Using the Chinese Remainder Theorem, compute $$y=CRT_{p_i}({y_i})$$ for some $y_i \in \mathbb{Z}_{p_i}$. In the above equation $y$ is defined modulo $x_0$.

My question. Is always $y$ invertible in $\mathbb{Z}_{x_0}$ ?

My thinking. It is well known that CRT is an insomorphism from $\mathbb{Z}_{p_1} \times \cdots \times \mathbb{Z}_{p_n}$ to $\mathbb{Z}_{x_0} $. As the inverse of $y \pmod{p_i}$ exists in each $\mathbb{Z}_{p_i}$, the isomorphism keeps this property also in $\mathbb{Z}_{x_0}$. So $y$ has to be invertible $\pmod{x_0}$.