Solving Modular Arithmetic Homework: ax = 1 (mod m)

[squaremeplz]

Homework Statement

Find x for

ax = 1 (mod m)

a) a = 15 , m = 31
b) a = 6, m = 93
c) a = 15, m = 20

if possible.


(The equal sign above is equivalence in modular arithmetic)

Homework Equations

The Attempt at a Solution

a) gcd(31,5) = gcd( 31 - 2*15, 15) = 1

thus (1)(31) + (-2)(15) = 1

and (-2) * 15 = 1 (mod 31)

i don't understand how I can find x since multiplying by -2 yields a number smaller than the modulus

b) gcd(93,6) = 3

no solution because gcd =/= 1

c) gcd(20,15) = 5

no solution


Could somebody please help me out with these problems. It's my first time doing modular arithmetic and the book has only two examples.

Thank you!

 

[jhicks]

i don't understand how I can find x since multiplying by -2 yields a number smaller than the modulus.

Is -30 (mod 31) not 1? Not too sure what you're asking.

 

[HallsofIvy]

Homework Statement

Find x for

ax = 1 (mod m)

a) a = 15 , m = 31
b) a = 6, m = 93
c) a = 15, m = 20

if possible.


(The equal sign above is equivalence in modular arithmetic)

Homework Equations

The Attempt at a Solution

a) gcd(31,5) = gcd( 31 - 2*15, 15) = 1

thus (1)(31) + (-2)(15) = 1

and (-2) * 15 = 1 (mod 31)

i don't understand how I can find x since multiplying by -2 yields a number smaller than the modulus.

2(15)= 30 is "smaller than the modulus" but -2(15)= -30= (-1)(31)+ 1 so -2(15) is equal to 1 mod 31. Strictly speaking, the "numbers" in modulo arithmetic are equivalence classes of integers having the same remainder when multiplied by the modulus- one of which is a non-negative number less than the modulus. 1, for example, is in the set also containing 31+1= 32, -31+1= -30, 2(31)+1= 63, etc. -2 is in the same set as 31- 2= 29.

b) gcd(93,6) = 3

no solution because gcd =/= 1

c) gcd(20,15) = 5

no solution


Could somebody please help me out with these problems. It's my first time doing modular arithmetic and the book has only two examples.

Thank you!

Both b and c are correct. If 6x= 1 (mod 93) then 6x= 93n+ 1 for some integer n or 6x- 93= 1. As you say, since both 6 and 93 have a factor of 3, 6x- 93= 3(2x- 31) has a factor of 3 no matter what x is and so cannot be equal to 1. Similarly, if 15x= 1 (mod 20), then 15x= 20n+ 1 or 15x- 20n= 1 for some integer n. Since 15 and 20 both have a factor of 5, 15x- 20n= 5(3x- 4n) is a multiple of 5 and cannot be equal to 1.