# If $y = x \pmod {N_1}$ and $gcd(x, n) = 1$, then why is it that we know $gcd(y, N_1) = gcd(x, N_1) = 1$?

Let $n$ be a number that is odd, composite, and not a prime power. Thus, we can find $n_1$ and $n_2$ such that $n_1$ and $n_2$ are odd, coprime, and $n = n_1 n_2$. By the Chineese reminder theorem we can find $y \in \mathbb{Z}^*_N$ such that:

$$y = x \pmod {N_1}$$ $$y = 1 \pmod {N_2}$$

if that is true how come the following logic follow:

Since $y = x mod N_1$ and $gcd(x, n) = 1$, we know $gcd(y, N_1) = gcd(x, N_1) = 1$

in particular why is it that $gcd(y, N_1) = gcd(x, N_1)$ ? Intuitively it makes sense becuase they are the "equivalent" since they are in the same equivalence class but I can't prove why it holds.

For contradiction, assume $p\mid y,N_1$. But $y\equiv x\pmod{N_1}$ implies $y=N_1k+x$, so $p\mid x$, so $p\mid x,N_1$, so $p\mid x,N_1N_2$, so $p\mid x,n$, so $\gcd(x,n)\ge p$, contradiction.
For contradiction, assume $p\mid x,N_1$. But then $p\mid x,N_1N_2$, so $p\mid x,n$, so $\gcd(x,n)\ge p$, contradiction.
• @CharlieParker $\gcd(x,n)=1$, $n=N_1N_2$ implies $\gcd(x,N_1)=1$. Then $y\equiv x\pmod{N_1}$ implies $y=N_1k+x$, so $\gcd(y,N_1)=\gcd(N_1k+x,N_1)$. By Euclidean algorithm this equals $\gcd(x,N_1)$, which equals $1$. Commented Oct 21, 2017 at 13:15