Thread: Solving Congruences

If you are to solve for x in the congruence
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.

Originally Posted by diddledabble

If you are to solve for x in the congruence
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 , adding the modulus until cancellation is probably the best way to solve . For this particular congruence, add the modulus once to 20 to get:

Since , you can 'divide' by 7 to get your solution.

_____________

For a more general case where , as long as , then we can always use the Euclidean algorithm to find one solution modulo and use it to find all solutions modulo m. Here's an example in this wiki entry: Linear congruence theorem

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

An equation of the form
(mod n)
has a solution if and only if .

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

Let and by assumption for some integer . Then by the Euclidean Algorith, there exist integers and such that
.

We now multiply through by k to get.



reduce mod n to see
(mod n).

There is your , namely, (mod n).

7x7=49=-1 (mod 50)

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

hence x=...

Helo, diddledabble!

Solve: .

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

This means: .

Solve for

Since is an integer, must be divisible by 7.
The first time this happens is

So we have: .

Therefore: .

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.

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

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

Given the congruence , if , then there are solutions exactly.

So for the congruence , we can see that there should be 5 solutions modulo 50.

___________

Reduce your congruence:

Quickly by inspection, by adding the modulus to 4, we get:

which is satisfied by all integers such that .

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