Thread: Congruence

Hello everybody..can u help me with my problem in congruence. This is it...I've answered this one but I think it is wrong...I use euclidean algorithm 11=5(2)+1. Pls help me the true answer with this problem...thank you

*Find a multiple of 11 that leaves a remainder of 1 when divided by each of the integers 2, 3, 5, 7.

Originally Posted by manusform

Hello everybody..can u help me with my problem in congruence. This is it...I've answered this one but I think it is wrong...I use euclidean algorithm 11=5(2)+1. Pls help me the true answer with this problem...thank you

*Find a multiple of 11 that leaves a remainder of 1 when divided by each of the integers 2, 3, 5, 7.

]

You can do it by "gentle brute force": from the conditions the multiple, let's call it x, is odd and ends either in 1 or 6 ==> it ends in 1 (why?)
So you must concentrate on multiples of 11 ending in 1; there aren't that many: 11, 121, 231 341,...,1001, 1111, 1221, 1331, etc.
Since it must be 1 + 3k, for some integer k, this rules out 11, 121,1001, etc.

Of course, you could read carefully the proof of the Chinese Remainder Theorem and thus construct your number.

Tonio

Originally Posted by tonio

]

You can do it by "gentle brute force": from the conditions the multiple, let's call it x, is odd and ends either in 1 or 6 ==> it ends in 1 (why?)
So you must concentrate on multiples of 11 ending in 1; there aren't that many: 11, 121, 231 341,...,1001, 1111, 1221, 1331, etc.
Since it must be 1 + 3k, for some integer k, this rules out 11, 121,1001, etc.

Of course, you could read carefully the proof of the Chinese Remainder Theorem and thus construct your number.

Tonio

Maybe this is a better approach -

Let the number be 11k
Now 2|11k-1, 3|11k-1, 5|11k-1, 7|11k-1

Thus 2.3.5.7|11k-1
or 11k-1 = 210m
thus 11k - 210m = 1

We can solve this Diophantine equation using euclidean algo as (11,210) = 1.

Am I correct in my approach please?

Yes, that's excellent!

Originally Posted by HallsofIvy

Yes, that's excellent!

Yes - I realized I was correct after your detailed post. It helped me validate my equation.

General solution to the Diophantine equation is of the form

(210k-19)11 + (1-11k)210 =1 where k is any integer


So solution to the original question is (210k-19)11, where k is any integer
1st positive solution is when k=1, which gives 2101 like you said.

Thanks