MIT 18.02 Multivariable Calculus, Fall 2007 63 Online
OpenStudy (anonymous):

What is the complete solution of 36x= 8 (mod 116)? (the "=" means congruent to) @Mathematics

OpenStudy (anonymous):

What is the gcd (36,116)?

OpenStudy (anonymous):

2

OpenStudy (anonymous):

joe i need ur help

OpenStudy (anonymous):

so now, because 2 divides 8 as well, we should divide everything by 2, even the modulus

OpenStudy (anonymous):

so , 13x = 4 (mod 58)?

OpenStudy (anonymous):

isnt the gcd (35 116) =4?

OpenStudy (anonymous):

so:$36x\equiv 8\mod 116\iff 18x\equiv 4\mod58$ hmm...i think the gcd of 36 and 116 is really 4, because we can divide 36 and 58 by 2 again.

OpenStudy (anonymous):

i mean gcd(36 116)

OpenStudy (anonymous):

oh, ok

OpenStudy (anonymous):

yes, it is 4. so we could have divided everything by 4 from the begining, but we are still good.

OpenStudy (anonymous):

so we really want to solve:$9x\equiv 2 \mod 29$

OpenStudy (anonymous):

There are 2 ways we can go from here. try to find the inverse of 9 mod 29, or eyeball the solution.

OpenStudy (anonymous):

i'm not exactly sure how to find the inverse. :(

OpenStudy (anonymous):

sometimes a little tedious. this one seems like it might be. let me check something before i decide on which route to take.

OpenStudy (anonymous):

ok

OpenStudy (anonymous):

ugh, this is just a bad problem lol. i guess we will go through the formal way of finding inverses. you want the inverse of 9, so you look at powers of 9.

OpenStudy (anonymous):

you look for the power of 9 that is congruent to 1 mod 29

OpenStudy (anonymous):

so to start, we see that:$9^2=81\equiv 23,9^3=9\cdot9^2\equiv 9\cdot23\equiv4$$9^4=9\cdot9^3\equiv 9\cdot4\equiv 36\equiv 7$ so on and so forth. does this make sense?

OpenStudy (anonymous):

(by the way this is a horrible problem to teach this with lol)

OpenStudy (anonymous):

:) . Just one thing. How did u get the first 23?

OpenStudy (anonymous):

i had to manually calculate what 81 (mod 29) was. so i used the division algorithm:$81=2(29)+23\iff81\equiv 23\mod 29$

OpenStudy (anonymous):

ok

OpenStudy (anonymous):

So, basically, we will keep checking powers. and it wont be until:$9^{13}\equiv 13$$9^{14}=9\cdot 9^{13}\equiv 9\cdot 13\equiv 117\equiv 1\mod 29$ so now that we see $9\cdot 13\equiv 1\mod 29$ that means 13 is the inverse of 9 mod 29

OpenStudy (anonymous):

again, most of the time you dont have to go that high to find the inverse. this was a bad problem lol

OpenStudy (anonymous):

but anywhos, now that we have the inverse, we can solve the problem. multiply the equation by 13 on both sides, we obtain:$9x\equiv 2\mod 29\iff 13\cdot9x\equiv 13\cdot 2\mod 29$ $\iff 1\cdot x\equiv 26\mod 29\iff x\equiv 26\mod 29$so x = 26 mod 29 is a solution. However, it is not the only solution. Since the gcd(36,116)=4, there are a total of 4 solutions to this congruence. we still need the other 3.

OpenStudy (anonymous):

Will we get the other 3 by adding 29 to the solution we obtained. so another solution will be:$26+29=55$$55+29=84$$84+29=113$Now we have 4 incongruent solutions mod 116, and we are done.

OpenStudy (anonymous):

So, x=26 (mod 29) is a solution, but we also have to include the other three equations you just mentioned in the final answer as well to give a complete solution?

OpenStudy (anonymous):

yes. The original question was one looking at things modulo 116. We reduced the problem to look at everything modulo 29, and found one solution, but 116=4(29), so there is one solution in every set of 29 integers modulo 116. if you check, each one of those solutions is congruent to 26 mod 29.

OpenStudy (anonymous):

Ok. This is much clearer now. Thanks a ton!

OpenStudy (anonymous):

no problem :)