How to solve 2 = 7x (mod 177)?

Question

How do I solve 2 = 7x (mod 177).
I've used some online calculator on the internet, and apparently the answer is 92.
I have no idea how to do this, can anyone tell me how you can solve this one, step by step?

And, why wouldn't 2 = 7x (mod 200) give any solution?

Answer 1

x = 177n - 25 for all integers n, therefore infinite solutions.
However, the smallest positive value of x is 152.
(7 * 152 = 1064 = 177*6 + 2)

since x = 177n - 25
7x = 7*177n - 175
= 7*177n - 177 + 2
= 177*(7n-1) + 2
≡ 2 (mod 177)

Pascal has given a very good detailed explanation. note that his method explains that while
2 ≡ 7x (mod 200) → x ≡ 86 (mod 200)
2 ≡ 7x (mod 203) e.g. has no solutions.


The method is equivalent to the method of continued fractions.
7/177 =
= 1 / (177/7)
= 1 / (25 + 2/7)
= 1 / (25 + 1 / (7/2) )
= 1 / (25 + 1 / (3 + 1/2) )
There are three partial convergents (n=3).
They are: 25, 1/(25+1/3), and the total number.
we compute the next to the last convergent. That is, we ignore the last term 1/2.

= 1 / (25 + 1 / (3) )
= 1 / (76/3)
= 3/76 = y/x; or y=3, x=76

This is the solution to 7x - 177y = (-1)^(n-1) = (-1)^2 = 1
or 7*76 ≡ 1 (mod 177)
then 7*76*2 ≡ 2 (mod 177)
7*152 ≡ 2 (mod 177)

In the case of 2 = 7x (mod 200)
7/200
= 1 / (200/7)
= 1 / (28 + 4/7)
= 1 / (28 + 1/(7/4) )
= 1 / (28 + 1 / (1 + 3/4) )
= 1 / (28 + 1 / (1 + 1 / (1 + 1/3) ) )
The partial convergents are
1/28, 1(28+1), 1/(28+1/(1+1)), and the whole number. n=4
The next to the last is:
1/(28+1/(1+1)) = 1/(28+1/2) = 1/(57/2) = 2/57
So, 57*7 - 2*200 = (-1)^(4-1) , or
57*7 - 2*200 = -1
57*7 ≡ -1 (mod 200)
(-2)*57*7 ≡ (-1)*(-2) (mod 200)
(-114)*7 ≡ 2 (mod 200)
x = -114 or (-114 + 200 = 86)

Answer 2

The other posters have given you some good methods that work with a little insight, but there is in fact a method that works on all equations of this form and can be turned into an algorithm. I describe it here.

If this were an ordinary equation (rather than a congruence relation), you would start by multiplying both sides by 1/7, which is the multiplicative inverse of 7 in R. You can do something similar here: 7 also has a multiplicative inverse in Z/177Z, so if you find that multiplicative inverse, and multiply both sides by it, you will be able to find the value of x.

To find the multiplicative inverse, note that if x and y are coprime, then by Bezout's identity, there exist integers a and b such that ax+by=1, which means that a is the multiplicative inverse of x mod y (can you see why?). To find these numbers, we employ the extended Euclidean algorithm. We assume that we can find numbers a' and b' such that:

a'(y%x)+b'x=1 (where y%x is the least residue of y mod x - i.e. the remainder after dividing y by x)

Then we set:

a=b' - a'*floor(y/x)
b=a'

This means that:

ax+by = b'*x - a'*floor (y/x)*x + a'y
= b'*x - a'*floor (y/x)*x + a'*(floor (y/x)*x + x%y)
=a'(x%y) + b'x = 1

So we transform one instance of Bezout's identity into another instance involving smaller numbers. Since the numbers are coprime, repeatedly applying this trick will eventually leave us with x=1, and then the identity will have the obvious solution a=1, b=0, which we can use to solve all the previous identities. Let us use this on x=7, y=177. Then:

y_1 = 177, x_1=7, y%x = 2, floor (y/x)=25
y_2 = 7, x_2 = 2 y%x=1, floor (y/x) = 3
y_3 = 2, x_3 = 1

a_3=1, b_3=0
a_2=-3, b_2=1
a_1=1-(-3)*25=76, b_1=-3

so 76*7 - 3*177 = 1, which means that 76 is the multiplicative inverse of 7 mod 177.

With this in hand, we do some multiplication:

7x≡2 mod 177
76*7x ≡ 76*2 mod 177
x ≡ 152 mod 177

And there's your answer. Perfectly simple, the only remotely complicated part is finding the multiplicative inverse, and in this case the calculations needed were not too bad.

With your other problem, 2≡7x mod 200, we may use the same method (and thus show that contrary to your assertion, that equation also has solutions):

y_1=200, x_1=7, y%x=4, floor (y/x)=28
y_2=7, x_2=4, y%x=3, floor (y/x)=1
y_3=4, x_3=3, y%x=1, floor (y/x)=1
y_4=3, x_4=1

a_4=1, b_4=0
a_3=-1, b_3=1
a_2=1-(-1)*1=2, b_2=-1
a_1=-1-2*28=-57, b=2

So -57*7+2*200=1, and -57 is a multiplicative inverse of 7 mod 200. So:

7x≡2 mod 200
-57*x≡-57*2 mod 200
x≡-114 mod 200
Or choosing the least residue to represent the equivalence class:
x≡86 mod 200

And note that if x≡86 mod 200, then indeed 7x≡2.

Note that one of the assumptions we have made using this method is that 7 actually has a multiplicative inverse, which occurs if and only if it is coprime to the modulus. However, suppose we have a congruence relation of the form a≡bx mod c where b is not coprime to c. Then write this relation as an equation:

a=bx+kc

Now, let z=GCF (b, c). If z does not divide a, then we cannot possibly have a solution, because z divides the right hand side, but not the left. If z does divide a, then you may divide by it to obtain:

a/z = b/z x + k c/z

Which may be written as:

a/z ≡ b/z x mod c/z

Since b/z is now coprime to c/z, the equation has solutions mod c/z, which may be found in the manner previously described.

Answer 3

This means 7x divided by 177 gives a remainder of 2. In other words,
7x = 177n + 2 for some n.
→ x = (177n + 2) / 7

So 177n + 2 must be a multiple of 7. Now,
177n + 2 = 2n + 2 (mod 7) = 0 (mod 7)
→ 2n = 5 (mod 7)
→ n = 6 (mod 7) because 2*6=12 = 5(mod 7).

So the smallest solution is given by n=6...
→ x = (177*6 + 2) / 7 = 152.

Your answer 92 is incorrect... 92*7 = 644 = 113(mod 117)

Answer 4

That's the type of problem that you learn to solve in number therory classes. It involves finding common divisors of the coefficients and that type of thing. I'd have to review in order to solve it. Get an elementary number theory book to learn how to solve it.