# Congruence Equations

• Oct 14th 2011, 12:08 AM
terrorsquid
Congruence Equations
I feel comfortable solving equations such as $\displaystyle 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: $\displaystyle ax \equiv c~ mod ~b$

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

$\displaystyle 7x \equiv 12~mod~27$

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

$\displaystyle 45~mod~1042$

and

$\displaystyle 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).
• Oct 14th 2011, 12:30 AM
chisigma
Re: Congruence Equations
Quote:

Originally Posted by terrorsquid
I feel comfortable solving equations such as $\displaystyle 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: $\displaystyle ax \equiv c~ mod ~b$

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

$\displaystyle 7x \equiv 12~mod~27$

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

$\displaystyle 45~mod~1042$

and

$\displaystyle 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...

$\displaystyle 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...

$\displaystyle 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

$\displaystyle \chi$ $\displaystyle \sigma$
• Oct 14th 2011, 01:19 AM
terrorsquid
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?

Quote:

Is that the only solution of (1)?... the question is open...
By other solutions do you mean $\displaystyle x\equiv -6~ mod~ 27$ etc. or?
• Oct 14th 2011, 02:26 AM
Deveno
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?
• Oct 14th 2011, 05:15 AM
terrorsquid
Re: Congruence Equations
Thanks! this stuff is really interesting :D

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 $\displaystyle 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:

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

$\displaystyle 3x \equiv 9~mod~27$

$\displaystyle x \equiv 3~mod~27$
• Oct 14th 2011, 05:30 AM
terrorsquid
Re: Congruence Equations
Also, would this work?

multiply by 19:

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

$\displaystyle 25x\equiv 12~mod~27$

$\displaystyle -2x\equiv 12~mod~27$

$\displaystyle x\equiv -6~mod~27$

or

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

$\displaystyle -x\equiv 6~mod~27$

$\displaystyle x\equiv -6~mod~27$

although they are the same as $\displaystyle 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
• Oct 14th 2011, 06:33 AM
Deveno
Re: Congruence Equations
Quote:

Originally Posted by terrorsquid
Thanks! this stuff is really interesting :D

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 $\displaystyle 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:

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

$\displaystyle 3x \equiv 9~mod~27$

$\displaystyle 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.
• Oct 14th 2011, 07:07 AM
chisigma
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

$\displaystyle \chi$ $\displaystyle \sigma$
• Oct 14th 2011, 05:46 PM
terrorsquid
Re: Congruence Equations
So, is there another solution to the original congruence equation or is $\displaystyle 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:

$\displaystyle 4x\equiv 17~mod~31$

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

So multiplying both sides by 4, I get:

$\displaystyle 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 :D
• Oct 14th 2011, 11:00 PM
Deveno
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.
• Oct 15th 2011, 12:39 AM
terrorsquid
Re: Congruence Equations
Is the only answer to $\displaystyle 7x\equiv 12~mod~27 = 21$ and how did you check for ALL answers? like chisigma alluded to.
• Oct 15th 2011, 01:04 AM
Deveno
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.
• Oct 15th 2011, 01:54 AM
terrorsquid
Re: Congruence Equations
Quote:

Originally Posted by Deveno
depends on what you mean by "only".

I was trying to answer this:

Quote:

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

Quote:

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? $\displaystyle 3x\equiv 9~mod~27$ ? I understand I can't divide by three here, but is it unique in that same way as $\displaystyle 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 :D