Thread: 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.

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.

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.

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

Originally Posted by Ideasman

Why are you so smart? You're simply amazing

Thanks

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

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?

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?

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.

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.

bright idea...

this drug addiction recovery site

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