Finding $a \pmod c$ if $a \pmod b$ is known

Question

Suppose that:

$Y \pmod B = 0$

$Y \pmod C = X$

I know $B$ and $C$. $Y$ is unknown, it might be an extremely large number, and it does not interest me.

The question is: Is it possible to find $X$, and if so, how?

Answer 1

In the case where $b$ aand $c$ are relatively prime, knowing $y\bmod b$ gives absolutely no information about $y\bmod c$. It could be any of $0,1,2, \dots,c-1$.

In the general case where $b$ and $c$ are not necessarily prime, let $d=\gcd(b,c)$. Knowing $y\bmod b$ tells us what $y\bmod d$ is. But $y\bmod c$ can take on any value compatible with the known value of $y\bmod d$. That is, if $y\bmod d=y_1$, then $y\bmod c$ can take on any of the values $y_1,y_1+d, y_1+2d, \dots,y_1+kd$, where $k=\frac{c}{d}-1$.

Answer 2

No; more information is needed. To see this, suppose that $B=2$ and $C=5$ and suppose that we know that $Y \bmod 2 = 0$ and we want to figure out $X = Y \bmod 5$. The possibilities for $X$ are not unique and depend on $Y$:

• Since $2$ is a factor of $10$, we could have $Y=10$, which yields $X=0$.
• Since $2$ is a factor of $12$, we could have $Y=12$, which yields $X=2$.
• Since $2$ is a factor of $14$, we could have $Y=14$, which yields $X=4$.
• Since $2$ is a factor of $16$, we could have $Y=16$, which yields $X=1$.
• Since $2$ is a factor of $18$, we could have $Y=18$, which yields $X=3$.

Answer 3

$\bigg\lbrace\begin{eqnarray}y\equiv 0\pmod b\\ y\equiv x\pmod c\end{eqnarray}\bigg\rbrace $ $\!\iff\! \bigg\lbrace\begin{eqnarray} y &=& j b,\ \ &{\rm some}\ \ j\in \Bbb Z\\ y &=& x\! +\! k c,\ \ &{\rm some}\ \ k\in \Bbb Z\end{eqnarray}\bigg\rbrace\!\iff\! x = jb\!-\!kc,\ \ {\rm some}\ \ j,k\in\Bbb Z$

Thus, by Bezout, the possible values of $\,x\,$ are precisely the multiples of $\,\gcd(b,c).$