How to solve modulo / modular arithmetic ?

[XodoX]

Homework Statement

Find some x such that x\equiv8 mod (18)

Find the inverse of 12 modulo 41

Solve 2x=7 mod (13)

Homework Equations

Let a and be be integers, and let m be a positive integer. Then a \equiv b ( mod m) if and only if a mod m = b mod m

The Attempt at a Solution

I'm not sure how you do this. Can someone explain please? I know it's actually easy... but can't figure it out!

 

[SammyS]

a ≡ b (mod m) iff a - b = m·k, for some integer k.

 

[Unit]

To find the inverse of a number "a" modulo some number "p", you want an x such that ax ≡ 1 (mod p). Think of this as a + a + a + ... + a ≡ 1 (mod p).

Also, to solve 2x ≡ 7 (mod 13), you can find the inverse of 2 (mod 13), then multiply both sides by it.

 

[HallsofIvy]

Homework Statement

Find some x such that x\equiv8 mod (18)

That's barely a problem at all- one such x is "8"! (Others are 8+ 18= 26 and 8- 18= -10.)

Find the inverse of 12 modulo 41

You are seeking an integer, x, such that 12x= 1 (mod 41). That is the same as saying that 12x= 1+ 41y for some integer y. And that equation is the same as 12x- 41y= 1.

The standard way of solving such a Diophantine equation is to use the "division algorithm":
12 divides into 41 three times with remainder 5: 41- 3(12)= 5. 5 divides into 12 twice with remainder 2: 12- 2(5)= 2. 2 divides into 5 twice with remainder 1: 5- 2(2)= 1.

Replace (2) in the third equation with (12- 2(5)) from the second equation and we have 5- 2(12- 2(5))= 5(5)- 2(12)= 1. Replace (5) in that with 41- 3(12) from the first equation and we have 5(41- 3(12))- 2(12)= 5(41)- 17(12)= 1.
We can see immediately that one solution to 12x- 41y= 1 is x= -17, y= -41. It is also easy to see that x= -17+ 41k and y= -41+ 17k is a solution for any integer k. Can you find a k that gives the smallest positive x?

Solve 2x=7 mod (13)

This is the same as saying that 2x= 7+ 13y for some integer y. That is the same as 2x- 13y= 7.

Now do the same as above. 2 divides into 13 six times with remainder 1: 13- 2(6)= 1. Multiply that by 7: 13(7)- 2(42)= 7. That is, one solution is x= -42, y= -7. Again, x= -42+ 13k, y= -7+ 2k is a solution for any k. What is the smallest positive value for x?

Or, for this simple problem, you could just note the 2(7)= 14= 1 (mod 13) so the multiplicative inverse of 7 (mod 13) is 2. Then multiply 7 by that multiplicative inverse.

Homework Equations

The Attempt at a Solution

I'm not sure how you do this. Can someone explain please? I know it's actually easy... but can't figure it out!

Haven't you been given some instruction in this? You should at least try things even if you are not sure.

 

[XodoX]

Thanks for the detailed explanation. But I still don't know how the mod thing works. Mod is the rest or what? The definition from the book doesn't make sense to me.
I'm not getting it.

38=14 mod 12. How would I do that?


38−14=24, which is a multiple of*12. I understand that, but what's the point here? Always subtract the 2nd by the 1st and look if the remainder is a multiple of the mod?

 

[SammyS]

Another way to look at this is with the idea of remainder when doing division.

Notice that 38 and 14 both have a remainder of 2 when you divide them by 12.