# Chinese Rem. Thm.

• Mar 24th 2007, 01:51 PM
Ideasman
Chinese Rem. Thm.
1.) Utilizing the Chin. Rem. Thm., find 5 consec. pos. integers such that the following conditions hold: the first is div. by 2, the 2nd is div by 3, the 3rd is div by 5, the 4th is div. by 7 and the final (the 5th) is div. by 11.

2.) Now, prove for any pos. integer n, there will exist n consecutive pos. integers a_1, a_2, ..., a_n, such that p_i | a_i for each i, where the p_i illustrates the i-th prime.
• Mar 24th 2007, 07:24 PM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
1.) Utilizing the Chin. Rem. Thm., find 5 consec. pos. integers such that the following conditions hold: the first is div. by 2, the 2nd is div by 3, the 3rd is div by 5, the 4th is div. by 7 and the final (the 5th) is div. by 11.

Let x be the first positive integer.

Then,
x = 0 (mod 2)
x+1 = 0 (mod 3)
x+2 = 0 (mod 5)
x+3 = 0 (mod 7)
x+4 = 0 (mod 11)

Hence,
x = 0 (mod 2)
x = -1 (mod 3)
x = -2 (mod 5)
x = -3 (mod 7)
x = -4 (mod 11)

Write in normal form,
x = 0 (mod 2)
x = 2 (mod 3)
x = 3 (mod 5)
x = 4 (mod 7)
x = 7 (mod 11)

And the moduli are relatively prime to each other, that is exactly the form we need.
• Mar 24th 2007, 07:26 PM
ThePerfectHacker
Quote:

Originally Posted by Ideasman

2.) Now, prove for any pos. integer n, there will exist n consecutive pos. integers a_1, a_2, ..., a_n, such that p_i | a_i for each i, where the p_i illustrates the i-th prime.

Just generalize what I did.

And we end up with the following congruences,
x = 0 (mod p_1)
x = -1 (mod p_2)
....
x = -(n-1) (mod p_n)
Because these are prime numbers we have that,
gcd(p_i,p_j)=1
For 1<= i,j<=n
And hence by the Chinese Remainder Theorem there exists such an integer.
Q.E.D.
• Mar 24th 2007, 08:31 PM
Ideasman
Quote:

Originally Posted by ThePerfectHacker
Just generalize what I did.

And we end up with the following congruences,
x = 0 (mod p_1)
x = -1 (mod p_2)
....
x = -(n-1) (mod p_n)
Because these are prime numbers we have that,
gcd(p_i,p_j)=1
For 1<= i,j<=n
And hence by the Chinese Remainder Theorem there exists such an integer.
Q.E.D.

Why are you so smart? You're simply amazing

Thanks
• Mar 24th 2007, 08:32 PM
Jhevon
Quote:

Originally Posted by Ideasman
Why are you so smart? You're simply amazing

Thanks

i think it's these weird drugs he's taking
• Mar 25th 2007, 05:11 AM
ThePerfectHacker
Quote:

Why are you so smart? You're simply amazing
Because I came from Union of Soviet Socialist Republic.

Quote:

i think it's these weird drugs he's taking
What did Erdos use again?
• Mar 27th 2007, 12:22 AM
Ideasman
Quote:

Originally Posted by ThePerfectHacker
Let x be the first positive integer.

Then,
x = 0 (mod 2)
x+1 = 0 (mod 3)
x+2 = 0 (mod 5)
x+3 = 0 (mod 7)
x+4 = 0 (mod 11)

Hence,
x = 0 (mod 2)
x = -1 (mod 3)
x = -2 (mod 5)
x = -3 (mod 7)
x = -4 (mod 11)

Write in normal form,
x = 0 (mod 2)
x = 2 (mod 3)
x = 3 (mod 5)
x = 4 (mod 7)
x = 7 (mod 11)

And the moduli are relatively prime to each other, that is exactly the form we need.

Hi TPH,

I was following your work. Once you get to the "normal form" it is now that I have to use the Chinese Remainder Theorem right? This will give me the 5 consecutive pos integers?
• Mar 27th 2007, 09:43 AM
ThePerfectHacker
Quote:

Originally Posted by Ideasman
Hi TPH,

I was following your work. Once you get to the "normal form" it is now that I have to use the Chinese Remainder Theorem right? This will give me the 5 consecutive pos integers?

Yes, but be careful, x is the first among these integers.
• Mar 27th 2007, 06:48 PM
Ideasman
Quote:

Originally Posted by ThePerfectHacker
Yes, but be careful, x is the first among these integers.

Alright, I attempted doing the chinese rem. theorem but ran into difficulty. In my notes, I have:

x = a_1*M_1*y_1 + a_2*M_2*y_2 + ... a_k*M_k*y_k ; m_i = M/m_i and y_i satisfies M_i*y_i = 1 (mod m_i)

Ah this formula looks confusing and I think it's simpler than I am making it out to be. It would have been nice if my prof. at least gave us an example.
• Aug 2nd 2012, 10:45 AM
davidsmith
Re: Chinese Rem. Thm.
• Aug 3rd 2012, 01:37 AM
kraj8995
Re: Chinese Rem. Thm.
I like this concept.I have read something like it very long ago.