Thread: Congruence Help!

I feel really silly not being able to figure this out -- the problems come from a proof an example of the Chinese Remainder Theorem. I have tried multiplying and adding and subtracting and such on scrap paper but the answers simply don't make sense to me. The answer won't help me so much as a description of the method, so really any advice is appreciated!!. Thanks in advance! Oh, and take == to meant congruent to...

1) A claim (book doesn't bother to explain why) states that all sol'ns of 7x == 1 (mod 31) satisfy x == 9 (mod 31)

2) Another says 5t + 1 == 2 (mod 6) can be solved for t to yield t == 5(mod 6)

3) The last one says 30u + 26 == 3(mod 7) can be solved for u to yield u == 6 (mod 7)

The first one -- WHY?! If 31 divide 7x-1, does that mean 31 divides x-9?!

The second one -- I don't even know what to do. Subtracting 1 from each side gets 5t == 1(mod 6). Using Euclidean Algo (or common sense), gcd(5,6)=1, and 1 = 1.6 - 1.5 so t=1 works. So 1 == 5 (mod 6). Does this mean that t == 5 (mod 6)?

The last one I start off by subtracting 26 to get 30u == -23 (mod 7). I believe you can subtract off multiples of 7 from 20, to get 2u == -23 (mod 7) . [Is the same allowed on the right?]. Since gcd(2,7)=1 which obv divides 23, We can use 1 = 1.7 - 3.2 --> -23 = -23.7 + 69.2 so u=69. So 2(69) == -23(mod 7). But then what is u congruent to mod 7?

AH!

Originally Posted by jsndacruz

I feel really silly not being able to figure this out -- the problems come from a proof an example of the Chinese Remainder Theorem. I have tried multiplying and adding and subtracting and such on scrap paper but the answers simply don't make sense to me. The answer won't help me so much as a description of the method, so really any advice is appreciated!!. Thanks in advance! Oh, and take == to meant congruent to...

1) A claim (book doesn't bother to explain why) states that all sol'ns of 7x == 1 (mod 31) satisfy x == 9 (mod 31)

2) Another says 5t + 1 == 2 (mod 6) can be solved for t to yield t == 5(mod 6)

3) The last one says 30u + 26 == 3(mod 7) can be solved for u to yield u == 6 (mod 7)

The first one -- WHY?! If 31 divide 7x-1, does that mean 31 divides x-9?!

The second one -- I don't even know what to do. Subtracting 1 from each side gets 5t == 1(mod 6). Using Euclidean Algo (or common sense), gcd(5,6)=1, and 1 = 1.6 - 1.5 so t=1 works. So 1 == 5 (mod 6). Does this mean that t == 5 (mod 6)?

The last one I start off by subtracting 26 to get 30u == -23 (mod 7). I believe you can subtract off multiples of 7 from 20, to get 2u == -23 (mod 7) . [Is the same allowed on the right?]. Since gcd(2,7)=1 which obv divides 23, We can use 1 = 1.7 - 3.2 --> -23 = -23.7 + 69.2 so u=69. So 2(69) == -23(mod 7). But then what is u congruent to mod 7?

AH!

1. 7x == 1 (mod 31) ==> 7x==63(mod 31) ==> x==9(mod 31)

2. 5t + 1 == 2 (mod 6) ==> 5t == 1 (mod 6) ==> 5t==25(mod 6) ==> t==5(mod 6)

3. Take a try...

Ahh I see.. I thought dividing was not allowed for congruences though -- unless you can divide all the way through including the modulus. Is this not true once you add the variable?

Originally Posted by jsndacruz

Ahh I see.. I thought dividing was not allowed for congruences though -- unless you can divide all the way through including the modulus. Is this not true once you add the variable?

Properly speaking the 'division' doesn't exist in modular algebra. It is possible however the product of a number a by the 'multiplicative inverse' [if exists...] of b , where . It is possible to demonstrate thet if is prime, then any number has multiplicative inverse. Let consider as example the first congruence...

(1)

Because 31 is prime, 7 has multiplicative inverse and is so that the solution of (1) is...

(2)

At this point You should be able to solve the other two problems alone!...

Kind regards

Thanks so much ChiSigma, that helps a lot. I can't believe I never knew about this forum! I just learned more thumbing through different discussions than I have in 3+ weeks of class.

Originally Posted by jsndacruz

Thanks so much ChiSigma, that helps a lot. I can't believe I never knew about this forum! I just learned more thumbing through different discussions than I have in 3+ weeks of class.

Welcome to Math Help Forum jsndacruz!