# Thread: Solving Congruences

1. ## Solving Congruences

If you are to solve for x in the congruence $7x=20(mod50)$
What is the easier way to do it without using a calculator or any other type of electronic device. I know you can add 7 to 20 until the number is divisible by 7 and then divide by 7 to reduce it to a solution but that takes a while. I need to figure out how to get it done in just a minute or two. Thanks.

2. Originally Posted by diddledabble
If you are to solve for x in the congruence $7x=20(mod50)$
What is the easier way to do it without using a calculator or any other type of electronic device. I know you can add 7 to 20 until the number is divisible by 7 and then divide by 7 to reduce it to a solution but that takes a while. I need to figure out how to get it done in just a minute or two. Thanks.
You mean 50 (the modulus).

For small moduli and $(a,m) = 1$, adding the modulus until cancellation is probably the best way to solve $ax \equiv b \ (\text{mod } m)$. For this particular congruence, add the modulus once to 20 to get: $7x \equiv 70 \ (\text{mod } 50)$

Since $(7, 50) = 1$, you can 'divide' by 7 to get your solution.

_____________

For a more general case where $(a,m) \neq 1$, as long as $(a,m) \mid b$, then we can always use the Euclidean algorithm to find one solution modulo $\tfrac{m}{(a,m)}$ and use it to find all solutions modulo m. Here's an example in this wiki entry: Linear congruence theorem

3. ## @dibbledabble

Well, I guess I have an easier method to solve this congruence equation.

7x=20(mod50)

The equation simply means that 7x, a multiple of 7, is 20 more than a multiple of 50 [By modulo logic]

If we list down numbers which are 20 more than a multiple of 50, we get
70, 120, 170, 220, 270, 320, 370, 420, and so on... From this which it is quite evident that 70, 420, 770, 1120... etc are multiples of 7 which are 20 more than multiples of 50.

So, the smallest positive number is 70. 7x = 70 which means x = 10.
In fact, 350n - 280 would be the general form for the number 7x.
So, the general solution of x would be 50n - 40 where n can range from 1,2,3,.. and so on.

Hope it helped,
MAX

4. ## General theory

An equation of the form
$ax\equiv b$ (mod n)
has a solution if and only if $gcd(a,n)|b$.

Here is how you do it in general when these requirements are met.

Let $d=gcd(a,n)$ and by assumption $d|b \Rightarrow b=dk$ for some integer $k$. Then by the Euclidean Algorith, there exist integers $s$ and $t$ such that
$as+nt=d$.

We now multiply through by k to get.

$ask+ntk=dk=b$

reduce mod n to see
$a(sk)\equiv b$ (mod n).

There is your $x$, namely, $x=sk$ (mod n).

5. 7x7=49=-1 (mod 50)

so -x=140 (mod 50)=-10 (mod 50)

hence x=...

6. Helo, diddledabble!

Solve: . $7x \:\equiv\:20\text{ (mod 50)}$
Your "brute force" method is tedious, but it is commendable.
It shows that you understand the congruence statement.
Here is a primitive method . . .

We have: . $7x \:\equiv\:20 \text{ (mod 50)}$

This means: . $7x - 20 \:=\:50a\;\text{ for some integer }a.$

Solve for $x\!:\quad x \:=\:\frac{50a+20}{7} \quad\Rightarrow\quad x \:=\:7a + 2 + \frac{a+6}{7}$

Since $x$ is an integer, $a+6$ must be divisible by 7.
The first time this happens is $a = 1.$

So we have: . $x \;=\;7(1) + 2 + \frac{1+6}{7}\;=\;10$

Therefore: . $x \:\equiv\:10\text{ (mod 50)}$

7. ## @dibbledabble

Hi,

I think the solution offered by Soroban is the closest to the perfect procedure for your question. I guess mine was a bit too illustrative.

8. So using Soroban's method and a different congruence 35x=20(mod50) I get x=2(mod50) right?

9. ## Yes

If you haven't checked already, values of 'x' such as 52 and 102 satisfy the equation as, in 52 * 35 = 1820
= 1800 + 20
= 36*50 + 20
Similarly, 102*35 = 3570
= 3550 +20
= 71*50 + 50

MAX

10. Given the congruence $ax \equiv b \ (\text{mod } m)$, if $(a,m) \mid b$, then there are $(a,m)$ solutions exactly.

So for the congruence $35x \equiv 20 \ (\text{mod } 50)$, we can see that there should be 5 solutions modulo 50.

___________

Reduce your congruence: $5 \cdot 7x \equiv 5 \cdot 4 \equiv (\text{mod } 50) \ \Rightarrow \ 7x \equiv 4 (\text{mod } \tfrac{50}{(5, 50)}) \ \Leftrightarrow \ 7x \equiv 4 \ (\text{ mod} 10)$

Quickly by inspection, by adding the modulus to 4, we get: $7x \equiv 14 \ (\text{mod } 10)$

which is satisfied by all integers such that $x \equiv 2 \ (\text{mod } 10) \ \ (\star)$.

Returning to our original congruence, all 5 solutions are least residues that satisfy $(\star)$. Therefore, modulo 50: 2, 12, 22, 32, 42 are all solutions.