1. ## 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.

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

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

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

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

Thanks
i think it's these weird drugs he's taking

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

i think it's these weird drugs he's taking
What did Erdos use again?

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

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

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

11. ## Re: Chinese Rem. Thm.

I like this concept.I have read something like it very long ago.