Question

Modular Arithmetic: Can someone help me understand how to solve problems?

Answer 1

So, I've got an exam tomorrow, and mostly I just can't figure out how to solve problems from scratch. Looking at problems people have helped me with on here, every step makes sense

Answer 2

But I can't figure out how to take the necessary steps to arrive at a solution. Whenever I'm doing practice exam problems I just find myself guessing and checking to see if it helps.

Answer 3

So like, here are 2 problems from practice exams that I couldn't get just by looking at:

87x = 57 mod105
140x=133mod 301

Answer 4

If you can talk me through the thought process of how I would figure out these problems without someone there to help me, that'd be awesome. Nothing is due tomorrow, so I have time to just ask questions.

Answer 5

I think a bit of guessing and checking is necessary to get a feel of the problem. But modular arithmetic is real easy - All you need to know well is the notation :
\[a\equiv b \pmod{n} \iff n|(a-b)\]

Answer 6

Guessing and checking is fine for problems with smaller numbers, but when I'm dealing with 2 and 3 digit numbers I really just don't know what steps to take.

Answer 7

Exactly! so lets solve this problem step by step \[87x \equiv 57 \pmod{105}\]

Answer 8

Alright, so I look at this, and there's not a super easy solution like dividing out by 87 or something.

Answer 9

dividing somethign throughout is a good idea.
but dividing 87 gives you rational number on right hand side : 57/87.

so lets divide the common factor of (87, 57)=3 through out instead

Answer 10

\[87x \equiv 57 \pmod{105}\]

dividing 3 throughout gives
\[\dfrac{87x}{\color{red}{3}} \equiv \dfrac{ 57}{\color{red}{3}} \pmod{\dfrac{105}{\color{red}{3}}}\]

which is same as

\[29x \equiv 19 \pmod{35}\]

Answer 11

Alright then, so 29x=19(mod105), which looks a bit simpler. There aren't any more common factors though.

Answer 12

Right mod 35 my bad.

Answer 13

Next divide 29 both sides, sicne gcd(35, 29) = 1 the modulus wont change :


\[29x \equiv 19 \pmod{35}\]

\[x \equiv \dfrac{19}{29} \pmod{35}\]

Answer 14

we're almost done

Answer 15

See if below makes sense
\[\dfrac{19}{\color{Red}{29}}\equiv \dfrac{19}{\color{red}{-6}} \equiv \dfrac{19\cdot 6}{-36} \equiv \dfrac{19\cdot 6}{-1}\equiv -19\cdot 6\]

Answer 16

so the solution is \[x\equiv -19\cdot 6 \equiv 26 \pmod{35}\]

Answer 17

Can you explain the intuition of how you're able to, umm, "adjust" just the denominator?

Answer 18

basically i want to see "1" on the denominator because i need an integer solution for x

Answer 19

for that, i thought of reducing \(29\) by replacing it with \(-6\) because \(29\equiv -6\pmod{35}\)

Answer 20

\[\dfrac{19}{\color{Red}{29}}\equiv \dfrac{19}{\color{red}{-6}}\]

Answer 21

Again \(29 \equiv -6 \pmod{35}\) because \(29-(-6)\) is divisible by \(35\)

Answer 22

Alright. I think that makes sense. And how did you think to do that?

Answer 23

What thought process did you use to arrive at that step?

Answer 24

we need to practice 2-3 problems before appreciating the method

Answer 25

lets solve a simple congruence maybe ?

Answer 26

Alright then, that might help.

Answer 27

solve this \[3x\equiv 1\pmod{17} \]

Answer 28

(using any method you know)

Answer 29

Alright, well I would look at this and see that 18 is divisible by 3

Answer 30

and 18 can be reached by adding 17 to 1

Answer 31

so 3x = 18 mod 17

Answer 32

And that's going to be true for when x= 6

Answer 33

Neat :) lets work the same using fractions directly :
\[3x \equiv 1 \pmod{17}\]

\[x\equiv \dfrac{1}{3}\]

but you want \(1\) in the denominator, and you jsut said that \(3\cdot 6\equiv 1 \) so multiply \(6\) top and bottom :
\[x\equiv \dfrac{1}{3}\equiv \dfrac{ 6}{3\cdot 6}\equiv 6\]

Answer 34

Essentially it is same as your method. Only the notation is different. I am using fractions and you're trying to avoid using fractions.

Answer 35

Okay, let me just reread what you said a couple times.

Answer 36

see if you can sovle below using fractions+guessing :
\[7x\equiv 3\pmod{27}\]

Answer 37

Alright, so 7x=3 mod 27
(3,7) = 1

so x = 3/7 (mod27)

28 = 1 mod 27

so

x = 12/28 mod 27
x= 12 mod 27?

Answer 38

Perfect! as you can see we don't need to justify each step like that. We can solve ANY congruence in one line if we allow to use fractions. lets do another probelm

Answer 39

Alright. I understand the method, but not really the intuition. The way our professor taught it was with this clock analogy, and I think I'm a bit stuck on that.

Answer 40

there are several ways to solve a congruence, what im showing you might be new to you so it will take more time to get use to compared to your professor method... :)

anyways the textbook method of solving these is to use "euclid division algorithm in reverse". familiar with it ?

Answer 41

Right, haven't looked at it in a couple days, 1 moment.

Answer 42

Alright, go ahead.

Answer 43

(by the way, thank you so much for all the help. You've been absolutely incredible)

Answer 44

lets solve the first problem usign euclid "gcd" algorithm in reverse \[87x \equiv 57 \pmod{105} \]

First rewrite the given congruence as a linear diophantine equation :
\[87x = 57 + 105y \]
which is same as
\[87x - 105y = 57\]

Answer 45

you must be knowing already a method to sovle linear diophantine equations ?

Answer 46

Umm Yeah, just a moment, let me refresh real quick

Answer 47

basically what we did is this :
translated an unknown prolem into a known problem which we know how to solve.

review the method of solving linear diophantine equations using euclid "gcd" algorithm and solve it

Answer 48

Oh I see

Answer 49

thats the only reason textbook uses euclid "gcd" algorithm to solve congruence.

otherwise there are almost always better/fast methods to solve a linear congruence

Answer 50

I like using fractions+guessing because it almost always worked superfast for me

Answer 51

Okay yeah, that makes a lot of sense.

Answer 52

Yeah, that last thing @ganeshie8 said is what I do, I write this down
\[87x = 57 + 105y \]

Then I just pray that they have a common factor, so I counted the digits of each of the numbers and they all end up being a multiple of 3, so I know it's divisible by 3.

Answer 53

right we can divide 3 both sides and the equation still remains same.
there is a criterian for solvability of a linear diophantine equation based on this observation :

\(ax+by=c\) is solvable only if \(\gcd(a,b) | c\)

Answer 54

Your method does seem a lot faster. Any tips for noticing simplifications?

In retrospect 19/29 seems simple, but I'm not sure if I would know to do that on the test. Not all of them are as simple as 3x = 1mod 17

Answer 55

I see what you mean... when the modulus is large, we can split the congruence into a set of simpler congruences and use chinese remainder theorem.. but one step at a time... all these methods take time to make sense of.

Answer 56

Alright. I think I have a much more solid understanding of the fundamentals now.

Answer 57

However euclid "gcd" algorithm works pretty nicely no matter what the size of modulus is.

Answer 58

So ultimately, I think I just need to try some random book problems and after a few problems hopefully knowing what to multiply by will be more intuitive.

Answer 59

solving \(191x\equiv 232\pmod{53232}\) looks scary using fractions+guessing.

but solving the linear diophantine equation \(191x -53232y = 232\) is not hard at all using euclid "gcd" algorithm in reverse

my suggestion is to always use euclid "gcd" algorithm in exams.
keep fractions+guessing to yourself :)

Answer 60

Alright. That's very true. Exams look pretty time restrictive, so I think I'll hold off on these types of problems until the end and see what time permits.

Thank you so much for all your help too. You've spent like the last hour explaining this to me, and it really has helped a lot.

Answer 61

Alright, I'll be trying out some bookwork, and I'll send you a message if I need any more help (as if you haven't helped me enough).

Again, thanks a ton for all the time you've invested here.

Answer 62

np :) just holler anytime you feel stuck.. i like these problems xD

Answer 63

Haha alright. Can't stress enough how amazing you are. Hope the rest of your day is as awesome as you are c: