1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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