Results 1 to 13 of 13

Math Help - Congruence Equations

  1. #1
    Member
    Joined
    Jul 2011
    Posts
    196

    Congruence Equations

    I feel comfortable solving equations such as xa + yb = c using Euclid's algorithm; however, I can't seem to see how I use this to solve congruence equations in the form: ax \equiv c~ mod ~b

    What are the steps I need to take to solve something like (making this up):

    7x \equiv 12~mod~27

    Also, how would I find an integer m which is congruent to both

    45~mod~1042

    and

    53~mod~128?

    Also, I don't understand why there are no solutions if the modulo number is not prime (I was told that solving equations with non-prime modulo was out of the scope for my unit but I'm interested).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Congruence Equations

    Quote Originally Posted by terrorsquid View Post
    I feel comfortable solving equations such as xa + yb = c using Euclid's algorithm; however, I can't seem to see how I use this to solve congruence equations in the form: ax \equiv c~ mod ~b

    What are the steps I need to take to solve something like (making this up):

    7x \equiv 12~mod~27

    Also, how would I find an integer m which is congruent to both

    45~mod~1042

    and

    53~mod~128?

    Also, I don't understand why there are no solutions if the modulo number is not prime (I was told that solving equations with non-prime modulo was out of the scope for my unit but I'm interested).
    Let's start from the first question, that is solving the congruence equation...

    7\ x \equiv 12\ \text{mod}\ 27 (1)

    In the set of integers mod 27 the number 7 has as multiplicative inverse 4, so that from (1), multilying both terms by 4, we obtain...

    x \equiv 12 \cdot 4\ \text{mod}\ 27 \equiv 21\ \text{mod}\ 27 (2)

    Is that the only solution of (1)?... the question is open...

    Kind regards

    \chi \sigma
    Last edited by chisigma; October 14th 2011 at 12:56 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    I hadn't seen the multiplicative inverse method used before. I can see that you have found a number which when you take mod 27, you are left with one in order to isolate x on the LHS. So a method is to try and find a multiple of the x coefficient that is within one of a multiple of the modulus? Does that always work?

    Is that the only solution of (1)?... the question is open...
    By other solutions do you mean x\equiv -6~ mod~ 27 etc. or?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: Congruence Equations

    no, it doesn't always work. gcd(a,b) must be 1 for this method to work. that's why your first step, in solving

    ax = c (mod b)

    should be to compute the prime factors of a,b and c. b "controls" the equation, so you want to check gcd(a,b) and gcd(c,b) (in other words, how the integers mod b behave, depends on what kind of number b is).

    if a,b, and c share a common factor, say a = ka', b = kb', c = kc', then you can check the equation:

    a'x = c' (mod b') and here it may well be that gcd(a',b') = 1.

    to solve 2 equations simultaneously, one usually uses the chinese remainder theorem: Chinese remainder theorem - Wikipedia, the free encyclopedia

    to apply the theorem, it is important that the two moduli be co-prime. if they are not, your best bet is: Method of successive substitution - Wikipedia, the free encyclopedia

    sometimes modulo a non-prime n, you get an equation that is unsolvable. the reason is this:

    if n has a divisor, say d, then n = kd, where 1 < k,d < n.

    so k,d ≠ 0 (mod n). but kd IS 0 mod n. in this case, k and d are called "zero-divisors".

    zero-divisors cannot have inverses (they act like 0 in this respect). consider this:

    2x = 3 (mod 6). 2 is a zero-divisor, it has no inverse. watch what happens when we multiply by 3:

    3(2x) = 3(3) (mod 6)
    6x = 9 (mod 6)
    0x = 3 (mod 6)
    0 = 3 (mod 6) <---wow. that's never true.

    a number doesn't have to be a factor of n to be a zero-divisor, even a number with a common factor causes problems.

    let's try again with this equation:

    4x = 3 (mod 6) again, we multiply by 3:
    3(4x) = 3(3) (mod 6)
    12x = 9 (mod 6)
    0x = 3 (mod 6)
    0 = 3 (mod 6) <--uh oh.

    the problem here is that 4 and 6 share a common factor, 2. when we hit 4 with 3 (the "missing factor" of 6), we get 12, a multiple of 6. that makes the left side 0, but not the right side.

    and indeed 4(0) = 0, 4(1) = 4, 4(2) = 2, 4(3) = 0 <---bad!!!, 4(4) = 4, 4(5) = 2 (all mod 6).

    so we never get a solution for 4x = 3 (mod 6), there aren't any. this is because multiplying 4's, we don't get "all the possible numbers" (mod 6), just 0, 2 or 4.

    so if we have 4x = y (mod 6), and y isn't 0,2, or 4 (mod 6), there isn't going to BE a solution.

    which is one of the things that makes primes so special. primes don't have this problem. for example:

    4(0) = 0 (mod 7)
    4(1) = 4 (mod 7)
    4(2) = 1 (mod 7) <--- oh look! an inverse for 4!
    4(3) = 5 (mod 7)
    4(4) = 2 (mod 7)
    4(5) = 6 (mod 7)
    4(6) = 3 (mod 7)

    note that we get every possible number on the right in those equations. so

    4x = y (mod 7) is always solvable. in fact, the solution is 2y (mod 7).

    now, what chisigma was asking you, is: is the solution 7x = 12 (mod 27) unique (up to modulus). that is, is there only ONE possible solution if x is between 0 and 26?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    Thanks! this stuff is really interesting

    I haven't looked at the two links you gave me yet but I think I found another answer. I am still not 100% on what I am trying to do exactly but I was playing around with different things that you said and I got the following:

    I noticed that 7(12) \equiv 3~mod~27

    and I noticed that 3 was a common factor of 12, so I multiplied both sides by 12 to get:

    (7\times 12)x \equiv (12\times 12)~mod~ 27

    3x \equiv 9~mod~27

    x \equiv 3~mod~27
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    Also, would this work?

    multiply by 19:

    (19\times 7)x \equiv (19\times 12)~mod~27

    25x\equiv 12~mod~27

    -2x\equiv 12~mod~27

    x\equiv -6~mod~27

    or

    (23\times 7)x\equiv (23\times 12)~mod~27

    -x\equiv 6~mod~27

    x\equiv -6~mod~27

    although they are the same as x\equiv 21~mod~27 :S

    I am just going through multiples of 7 and 12 mod 27 to see if they can divide each other and get an integer - not really efficient if the modulus was large :S
    Last edited by terrorsquid; October 14th 2011 at 05:45 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: Congruence Equations

    Quote Originally Posted by terrorsquid View Post
    Thanks! this stuff is really interesting

    I haven't looked at the two links you gave me yet but I think I found another answer. I am still not 100% on what I am trying to do exactly but I was playing around with different things that you said and I got the following:

    I noticed that 7(12) \equiv 3~mod~27

    and I noticed that 3 was a common factor of 12, so I multiplied both sides by 12 to get:

    (7\times 12)x \equiv (12\times 12)~mod~ 27

    3x \equiv 9~mod~27

    x \equiv 3~mod~27
    your original equation was 7x = 12 mod 27, right? and you concluded that x = 21 (mod 27) was a solution, yes?

    let's check it in 3x = 9 mod 27:

    3(21) = 63 = 2(27) + 9 = 9 mod 27 <---so far, so good.

    21 = 3 mod 27 <---- BAD!! NO GOOD!!!!

    3 and 27 are not co-prime. you CANNOT "divide by 3" mod 27, it just doesn't work.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Congruence Equations

    The fact is that in algebra mod n the 'division by k' doesn't exists... it exists the 'multiplication by the multiplicative inverse of k mod n' if this quantity exists!...

    If n is prime, then any k from 0 to n-1 has a multiplicative inverse mod n... if n isn't prime, this is not necessarly true... for example 3 has no multiplicative inverse mod 27 and that is evident because don't exist a pair of integers p and q for which is 3*p=27*q+1...

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    So, is there another solution to the original congruence equation or is x\equiv 21~mod~27 the only one?

    To sum everything up, I now have some kind of method for getting one answer to these equations it seems, but I'm not sure about finding ALL solutions, e.g., say I have:

    4x\equiv 17~mod~31

    I notice that 4\times 8 = 32 \equiv 1~mod~31

    So multiplying both sides by 4, I get:

    x\equiv 12~mod~31

    But I can't think of any other way to check every possible solution other than going through y=1, 2,...30 and making sure that 4y and 31 are co-prime at each step.

    Also, I wasn't entirely sure what I was supposed to do if the gcd(a,b) was not 1? If a and b share a common factor, is there just no solutions?

    Sorry if I misunderstood something, I read your posts a few times
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: Congruence Equations

    suppose that a has an inverse mod n, and that:

    ax = ay (mod n). then

    (a^-1)ax = (a^-1)ay (mod n)

    (a^-1a)x = (a^-1a)y (mod n)

    1x = 1y (mod n)

    x = y (mod n).

    there's no "hard and fast rule" when gcd(a,b) is not 1...sometimes there's a solution, sometimes there isn't. some numbers c will be congruent to a multiple of a, and some won't. which numbers are, depends on which prime factors b has. the internal structure of the integers mod n, especially with respect to multiplication, can vary a lot. a number like 12, has a lot of divisors, which means a lot of congruences can't be solved. a number like 25 is "a bit better" because more numbers are co-prime to it.

    that's why primes are so special, we don't have to worry.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    Is the only answer to 7x\equiv 12~mod~27 = 21 and how did you check for ALL answers? like chisigma alluded to.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,390
    Thanks
    757

    Re: Congruence Equations

    depends on what you mean by "only". 48 works, too. 7 has an inverse (mod 27), this means we can "undo" or "reverse" multiplication by 7 (mod 27), in just "one way".

    but our results are only good mod 27, so any integer of the form 21 + 27k will work.

    post #10 is the justification for that. 7 and 27 are co-prime, so 7 has a multiplicative inverse. what this means, is that x<-->7x is a bijection in the integers mod 27. look:

    7(0) = 0
    7(1) = 7
    7(2) = 14
    7(3) = 21
    7(4) = 1 <--- unique product that =1 mod 27
    7(5) = 8
    7(6) = 15
    7(7) = 22
    7(8) = 2
    7(9) = 9
    7(10) = 16
    7(11) = 23
    7(12) = 3
    7(13) = 10
    7(14) = 17
    7(15) = 24
    7(16) = 4
    7(17) = 11
    7(18) = 18 <--- look! 7(18) = 18, but 7 isn't 1. why does this happen? gcd(18,27) = 9 > 1, you can't "cancel the 18's"
    7(19) = 25
    7(20) = 5
    7(21) = 12 <--unique solution!!!
    7(22) = 19
    7(23) = 26
    7(24) = 6
    7(25) = 13
    7(26) = 20

    now, look at that table carefully....convince yourself that each element of {0,1,2,...,26} occurs once and only once on the right.

    think of it this way: 7(k+1) = 7k+7, so each time we "go up 7", unless 7k+7 > 26, in which case, we use 7k+7-27 instead.

    now, if 7 and 27 had a common divisor, the cycles would "line up" at some point, and the values would start repeating.

    but 7 and 27 don't have any common factor, so we don't repeat, until we have gone through all 27 products.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Jul 2011
    Posts
    196

    Re: Congruence Equations

    Quote Originally Posted by Deveno View Post
    depends on what you mean by "only".
    I was trying to answer this:

    what chisigma was asking you, is: is the solution 7x = 12 (mod 27) unique (up to modulus). that is, is there only ONE possible solution if x is between 0 and 26?
    ...

    7(21) = 12 <--unique solution!!!
    It's unique because all three numbers have a common factor of 3 right?

    Is this similar to 7(12) = 3? 3x\equiv 9~mod~27 ? I understand I can't divide by three here, but is it unique in that same way as 12x\equiv 9~mod~27 (factor of 3)

    Thanks so much for your help by the way. Learning this in more depth than I had anticipated
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prime numbers and congruence equations.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 21st 2010, 11:54 PM
  2. [SOLVED] Euclids algorithm & congruence equations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 17th 2010, 10:10 PM
  3. congruence
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 30th 2010, 08:43 AM
  4. solving congruence equations
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 9th 2009, 02:17 PM
  5. Congruence Equations
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 15th 2006, 07:02 PM

Search Tags


/mathhelpforum @mathhelpforum