• Support PF! Buy your school textbooks, materials and every day products Here!

Modular arithmetic

  • #1
124
0

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 dont 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!
 
Last edited by a moderator:

Answers and Replies

  • #2
334
0
i dont 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.
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,793
922

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 dont 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.
 

Related Threads for: Modular arithmetic

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
23
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
23
Views
2K
Top