Question

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

Answer 1

What is the gcd (36,116)?

Answer 2

2

Answer 3

joe i need ur help

Answer 4

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

Answer 5

so , 13x = 4 (mod 58)?

Answer 6

isnt the gcd (35 116) =4?

Answer 7

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.

Answer 8

i mean gcd(36 116)

Answer 9

oh, ok

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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

Answer 14

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

Answer 15

ok

Answer 16

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.

Answer 17

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

Answer 18

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?

Answer 19

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

Answer 20

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

Answer 21

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

Answer 22

ok

Answer 23

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

Answer 24

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

Answer 25

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.

Answer 26

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.

Answer 27

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?

Answer 28

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.

Answer 29

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

Answer 30

no problem :)