Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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$.

share|improve this answer

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$.
share|improve this answer

$\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).$

share|improve this answer
    
This is a very good observation. Thank you. I almost thought that it might be a key to solving my problem, but recently I discovered that my number C is a prime. Looks like I'm out of luck. –  Highstaker May 31 '13 at 12:15
    
@Highstaker If $\,c\,$ is prime then $\,\gcd(b,c) = 1\ $ or $\,c,\,$ so the possible values of $\,x\,$ are all values, or all multiplies of $\,c,\,$ resp. –  Key Ideas May 31 '13 at 12:27
    
Yes, that's what I meant. X can be anything up to C. I guess I'll have to take a different approach. –  Highstaker May 31 '13 at 12:35
    
@Highstaker What was your intended application? –  Key Ideas May 31 '13 at 12:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.