Thread: Congruence Equations

I feel comfortable solving equations such as using Euclid's algorithm; however, I can't seem to see how I use this to solve congruence equations in the form:

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



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



and

?

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).

Originally Posted by terrorsquid

I feel comfortable solving equations such as using Euclid's algorithm; however, I can't seem to see how I use this to solve congruence equations in the form:

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



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



and

?

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...

(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...

(2)

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

Kind regards

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 etc. or?

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?

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

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

Also, would this work?

multiply by 19:









or







although they are the same as :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

Originally Posted by terrorsquid

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

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

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.

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

So, is there another solution to the original congruence equation or is 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:



I notice that

So multiplying both sides by 4, I get:



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

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.

Is the only answer to and how did you check for ALL answers? like chisigma alluded to.

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.

Originally Posted by Deveno

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? ? I understand I can't divide by three here, but is it unique in that same way as (factor of 3)

Thanks so much for your help by the way. Learning this in more depth than I had anticipated