[SOLVED] Find All Solutions of the Congruence

[wubie]

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.