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

Solve modular equation

  • Thread starter duki
  • Start date
  • #1
264
0

Homework Statement



Find the integer y with both 0 < y < 144 and 35y = 42(mod 144)

Homework Equations





The Attempt at a Solution



Can someone help me get started on this one? I understand that I can reduce it to 5y = 6(mod 144), and then to 5y = 6 + 144... but I'm not sure what to do with that. I mean, can I just do 5y = 150 and then y = 30?
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179


Homework Statement



Find the integer y with both 0 < y < 144 and 35y = 42(mod 144)

Homework Equations





The Attempt at a Solution



Can someone help me get started on this one? I understand that I can reduce it to 5y = 6(mod 144), and then to 5y = 6 + 144... but I'm not sure what to do with that. I mean, can I just do 5y = 150 and then y = 30?
If you plug [tex]y = 30[/tex] into the original equation, is it true? If so, then you're done.

An interesting question to consider: if instead of 35, the original equation had 36, then your method would fail. Why? Does the equation have a solution in that case?

A more ambitious question: what is a necessary and condition upon k in order for

ky = 42 (mod 144)

to have a solution? Does the answer change if instead of 42 you use some other number between 0 and 143?
 
  • #3
264
0


I'm a little confused here. So if I plug my answer into the equation and it doesn't work, it means there are no solutions? And I don't know the answer to the second question
 
  • #4
264
0


I have another one here:

0 < x < 41
19x = 22(mod 41)

You're right, my previous method didn't work. What can I do?
 
  • #5
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179


I have another one here:

0 < x < 41
19x = 22(mod 41)

You're right, my previous method didn't work. What can I do?
Do you know this theorem:

ax = b (mod n)

has a solution if and only if gcd(a,n) divides b.

In this case, gcd(a,n) = 1 since 19 and 41 are relatively prime. So a solution does exist.

Any solution to this equation:

ax + kn = b, where k is any integer

is also a solution to

ax = b (mod n)

There is a well-known algorithm for finding integers x and k that satisfy

ax + kn = b

provided that a solution exists. Are you familiar with it?
 
  • #6
264
0


No. :(
 
Last edited:
  • #7
264
0


I'm still stuck on this... can anyone give me a hand?
 
  • #8
HallsofIvy
Science Advisor
Homework Helper
41,793
920


I have another one here:

0 < x < 41
19x = 22(mod 41)

You're right, my previous method didn't work. What can I do?
Saying 19x= 22 (mod 41) means that 19x= 22+ 41k for some integer k. That is the same as 19x- 41k= 22. 19 divides into 41 2 times with remainder 3 so 41= 2(19)+ 3 or 41- 2(19)= 3. 3 divides into 19 6 times with remainder 1: 19- 6(3)= 1 and then 19- 6(41- 2(19))= 3(19)- 6(41)= 1. Multiplying by 22, 66(19)- 132(41)= 22. Thus one answer is x= 66. That's not the answer you want because it is too big but you should be able find the correct answer.
 

Related Threads for: Solve modular equation

  • Last Post
Replies
3
Views
836
Replies
5
Views
15K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
23
Views
2K
  • Last Post
Replies
2
Views
2K
Top