# Silly question probably..

• Jun 25th 2008, 11:55 AM
clarissa
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.
• Jun 26th 2008, 01:32 PM
bleesdan
Could you please state the problem clearly?
It's a little confusing right now.
• Jun 26th 2008, 05:52 PM
topsquark
Quote:

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
• Jun 26th 2008, 10:34 PM
Isomorphism
Quote:

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.
• Jun 27th 2008, 08:11 AM
ThePerfectHacker
Quote:

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)$.
• Jun 27th 2008, 08:50 AM
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]

-Dan
• Jun 27th 2008, 08:53 AM
ThePerfectHacker
Quote:

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 $-$.
• Jun 27th 2008, 09:00 AM
topsquark
Quote:

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