Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Find All Solutions of the Congruence

  1. Feb 4, 2004 #1
    [SOLVED] Find All Solutions of the Congruence


    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.
  2. jcsd
  3. Feb 4, 2004 #2


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook