# Math Help - Silly question probably..

1. ## Silly question probably..

I have to solve a system using The Chinese Reminder Theorem.
It has two equations:
x= +-4 mod 31
x= +- 22 mod 53
I've got N = 1643 And a1N1K1 + a2N2K2 = +-5088+-8184.
I know how to find the first two solutions:
x1 = 5088 + 8184 (mod 1643)
x2 = 8184 - 5088 (mod 1643)

Thanks.

2. Could you please state the problem clearly?
It's a little confusing right now.

3. Originally Posted by bleesdan
Could you please state the problem clearly?
It's a little confusing right now.
The problem statement is quite clear. See here.

-Dan

4. Originally Posted by clarissa
I have to solve a system using The Chinese Reminder Theorem.
It has two equations:
x= +-4 mod 31
x= +- 22 mod 53
I've got N = 1643 And a1N1K1 + a2N2K2 = +-5088+-8184.
I know how to find the first two solutions:
x1 = 5088 + 8184 (mod 1643)
x2 = 8184 - 5088 (mod 1643)

Thanks.
Since the gcd of 31 and 53 is 1, there is only one solution (mod 1643). So there is no x3 and x4. In fact there cant be x1 and x2 too.

5. Originally Posted by clarissa
x= +-4 mod 31
x= +- 22 mod 53
.
This is how I like to solve CR problems. Say we want to solve $x\equiv 4 (\bmod 31) \mbox{ and }x\equiv 22(\bmod 53)$.

If $a$ is an integer then $x\equiv 4(\bmod 31)$ if and only if $x\equiv 4 + 31a(\bmod 31)$. Similarly if $b$ is an integer then $x\equiv 22(\bmod 53)$ if and only if $x\equiv 22 + 53b(\bmod 53)$. We will find $a,b$ such that $4+31a = 22+53b\implies 31a - 53b = 18$. By using Euclidean algorithm we find $a=216$ and $b=126$. Which means $x\equiv 22 + 53(126)(\bmod 53) \implies x \equiv 6700$. And $x\equiv 4+31(216)(\bmod 31)\implies x\equiv 6700(\bmod 31)$. Since $\gcd(31,53)=1$ it means $x\equiv 6700 (\bmod 31\cdot 53)\implies x\equiv 6700 (\bmod 1643)\implies x\equiv 128(\bmod 1643)$.

6. Now my question is this: The original problem statement has
$x \equiv \pm 4 \text{ (mod 31)}$

How can we even have this? The only number I can think of that can be equivalent to $\pm 4$ is 4 (mod 8).[/tex]

-Dan

7. Originally Posted by topsquark
Now my question is this: The original problem statement has
$x \equiv \pm 4 \text{ (mod 31)}$

How can we even have this? The only number I can think of that can be equivalent to $\pm 4$ is 4 (mod 8).[/tex]
I think the person was doing two seperate problems. One involving $+$ and one involving $-$.

8. Originally Posted by ThePerfectHacker
I think the person was doing two seperate problems. One involving $+$ and one involving $-$.
Heck, if I'd have thought of that, I could have answered the question.

-Dan