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

What is the gcd (36,116)?

2

joe i need ur help

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

so , 13x = 4 (mod 58)?

isnt the gcd (35 116) =4?

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.

i mean gcd(36 116)

oh, ok

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

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

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

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

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

ok

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.

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

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?

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

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

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\]

ok

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

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

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.

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.

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?

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.

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

no problem :)

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