Find All Solutions of the Congruence

[wubie]

[SOLVED] Find All Solutions of the Congruence

Hi,

I am having lots of trouble understand how to do the following question:

Find all solutions of

8x congruent to 6 mod 14.

I know that the GCD is 2. Therefore there should be two equivalence classes of solutions.

But what is the PROPER way to find them?

I know that they are [6] and [13]. But I only can seem to get [6]. That being said I don't think the process in which I get [6] is the right way to do it either.

How do I find [13]?

I have spend LONG hours looking over my notes, reading the text, trying to understand the theory behind congruence classes. But I still don't understand how I can find all the equivalence classes of solutions. I always just get one. Even though I know there is more than one.

What is the PROPER way to find all classes?

For example, I use the euclidean algor. to get GCD of 2. Then I do the following

2 = 8 - 1*6
2 = 8 - 1*(14 - 1*8)
2 = 8 - 1*14 + 1*8
2 = 2*8 - 1*14.

I then multiply


2 = 2*8 - 1*14

by 3 and get

6 = 6*8 - 6*14.

From the term 6*8 I get the equivalence class of [6].

First of all, am I proceeding in the correct way for finding the equivalence class of [6]?

Secondly, how do I find the equivalence class of [13]?

Any help is appreciated. Thankyou.

 

[HallsofIvy]

Here's how I would do that problem: "8x congruent to 6 mod 14" is the same as saying "8x divided by 14 has a remainder of 6" or "8x minus some multiple of 14 is 6" or "8x- 14n= 6" for some integer n.
Yes, the GCD of those number is 2 so I would divide the entire equation by 2: 4x- 7n= 3. One could notice immediately that "7- 4= 3" so x= -1, n= -1. Or, use Euclid's algorithm: 7 divided by 4 is 1 with remainder 3 which really says 7- 3= 4 again.

The general solution to the Diophantine equation 4x- 7n= 3 is
x= -1+ 7m and n= -1+ 4m (because 4x= -4+ 28m and -7n= 7- 28m so the m terms cancel). When m= 1, x= 6. When m= 2, x= 13. For larger m, we get values larger than 14 so the two "basic" solutions are 6 and 13. All solutions are in those two equivalence classes.

The only difference between what you did and what I did is that I divided the equation by that GCD at the start. The reason you are not getting [13] is that the problem is "really" mod 7 and 6 and 13 are the same mod 7.

 

[M98Ranger]

Hi there,

First of all, congratulations on solving the congruence and finding one of the equivalence classes [6]! You are definitely on the right track.

To find the other equivalence class [13], we can use the same process you used for finding [6], but with a slight modification. Instead of multiplying the equation 2 = 2*8 - 1*14 by 3, we can multiply it by 4 to get 8 = 4*8 - 2*14. Then, we can add this equation to the original congruence 8x congruent to 6 mod 14 to get:

8x + 8 = 6 + 4*8 - 2*14

Factor out the 8 on the left side and simplify on the right side to get:

8(x+1) = 8

Now, we can see that x = 0 is a solution, and since 8 is relatively prime to 14, we can add multiples of 14 to 0 and still get a solution. Therefore, the other equivalence class is [13], since 0 + 14 = 14 which is equivalent to 0 mod 14.

In summary, the two equivalence classes for this congruence are [6] and [13]. I hope this helps clarify the process for finding all solutions of a congruence. Keep up the good work!