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.


1 Answer 1


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.

  • $\begingroup$ is there direct proof for this? Your proof is probably right but not intuitive at all to me. I feel the statement I wrote should be obvious so contradiction seems a bit too much. $\endgroup$ Commented Oct 8, 2015 at 20:57
  • $\begingroup$ @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$. $\endgroup$
    – user236182
    Commented Oct 21, 2017 at 13:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .