Ask your own question, for FREE!
MIT 18.02 Multivariable Calculus, Fall 2007
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 :)

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!