Silly question probably..

**clarissa** · June 25th 2008, 11:55 AM

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)
but how about x3, x4?

Thanks.

**bleesdan** · June 26th 2008, 01:32 PM

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

**topsquark** · June 26th 2008, 05:52 PM

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

**Isomorphism** · June 26th 2008, 10:34 PM

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)
but how about x3, x4?

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.

**ThePerfectHacker** · June 27th 2008, 08:11 AM

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

**topsquark** · June 27th 2008, 08:50 AM

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

**ThePerfectHacker** · June 27th 2008, 08:53 AM

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

**topsquark** · June 27th 2008, 09:00 AM

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

Thread: Silly question probably..

LinkBack

Thread Tools

Display

Silly question probably..

Similar Math Help Forum Discussions

[SOLVED] Silly question...?!

Silly question

A perhaps silly question about > 0

A silly question

Silly question

Search Tags