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 :)

Latest Questions cjsmith0608: When did slavery begin in Georgia? When the trustees founded the colony. When Georgia became independent with the U.
1 minute ago 0 Replies 0 Medals cjsmith0608: Why did the south support a lower tariff? To save American jobs To buy cheaper Br
4 minutes ago 0 Replies 0 Medals Shordysingle: Lemme spit dis right quick Gimme feedback:Lemme hear u talkin rekkless on mah bruhta imma put ur in da grave dis blikk got good aim I tell mah homies to sli
2 minutes ago 6 Replies 0 Medals cjsmith0608: Read the following excerpt from the Declaration of Independence. The history of the present King of Great Britain is a history of repeated injuries and usur
9 minutes ago 0 Replies 0 Medals briancarlos: 2. A vehicle travels 2345 m in 315 s toward the evening sun. What is its speed? (1) 3.
10 minutes ago 2 Replies 0 Medals natestratton04: What led to the shift of power away from Rome, the seat of the Catholic Church?
16 minutes ago 6 Replies 0 Medals cjsmith0608: Which group of people were at the top of the Southern caste system? freedmen weal
26 minutes ago 2 Replies 0 Medals cjsmith0608: Which of the following could be another word for freight? services goods ideas ba
35 minutes ago 1 Reply 1 Medal 88129386: why did the Aztcs make their home in a swampy area
12 minutes ago 4 Replies 1 Medal 88129386: hi what does hi m
13 minutes ago 1 Reply 0 Medals