# congruence modulo 5

• Sep 17th 2012, 11:38 AM
jojo7777777
congruence modulo 5
Determine the set of integer solutions of the system:
3x + y + 2z -t =1 (mod 5)
2x + y + 4z +3t +2w=1 (mod 5)
x - 2y +3t +w=3 (mod 5)
x -z -t +3w=1 (mod 5)
2x + 3y +3z - t -w=1(mod 5)
in which (mod 5) denotes congruence
modulo 5.
I would like to get some help in understanding the answer:"Treat the system as a system of equations
in which all calculations are done modulo 5. For example, adding the first row
to the second gives [0 2 1 2 2 2 ] "
Is there no "direct solution" for
finding x, y, z ,t,w?
• Sep 17th 2012, 03:21 PM
johnsomeone
Re: congruence modulo 5
Do everything the same as you would if dealing with real numbers - except for 2 things to be aware of:

1) You're free to reduce everything modulo 5. If you 4+3, you can replace it by 2. 1+4 = 0. Etc.
Technically, it's all happening in the equivalence classes of remainders mod 5, and so when you see "12=2 mod 5", it means $12+5\mathbb{Z} = 2+5\mathbb{Z}$. For shorthand, bearing that in mind, it's correct to write 12 = 2 mod 5. People often use a different symbol than =, like $\equiv$ or $\simeq$, to clarify that it's "equal modulo 5". The point, you can add, subtract, and multiply exactly as you would with integers, adding (or subtracting) any multiple of 5 to any value whenever you please.
2) When seeking to *divide* (say, to get a leading coeficent of 1 if you choose to solve this using matricies), the 5 becomes important - especially that 5 is a prime. Since 5 is a prime, division by non-zero numbers is possible, but will look a little weird.
First note that "non-zero" here is already a little weird. 10 = 0 modulo 5. 10 = 385 = -90125 = -840 = 0 mod 5.
For non-zero values, "dividing" means mulitplying by something to get 1. What do you mulitply 3 by to get 1 MODULO FIVE? The answer isn't the rational number 1/3, since modulo 5 only meaningful for integers. The answer is 2, because (2)(3) = 6 = 1 mod 5. Maybe an example makes this clearer:
Solve: 3x-3 = 4.
Solution: Add 3 to both sides: 23 = 7. Multiply both sides by (1/3) (meaning of "divide by 3"): (1/3)(3x) = (1/3)(7), so ((1/3)(3))x = 2 1/3, so (1)x = 2 1/3, so x = 2 1/3.
I strung out how the "divide by 3" part works so that you can compare with how do it modulo 5:
Now solve: 3x-3 = 4 mod 5.
Solution: Add 3 to both sides: 3x = 7 mod 5. We can make the numbers smaller (we don't have to, but we can, so I will), since 7 = 2 mod 5. Thus 3x = 2 mod 5.
Now want to divide by that 3 to solve for x. Which means we need to find "3 inverse mod 5" (written $3^{-1}$, or sometimes $3^*$, a number that when multiplied by 3 gives 1 modulo 5.
Again (2)(3) = 1 mod 5, so $3^{-1} = 3^* = 2 \mod 5$. Watch how multiplying both sides by 2 has the same effect as "dividing both sides by 3" did in the example above.
Multiply both sides by 2: (2)(3x) = (2)(2) mod 5, so ((3)(2))x = 4 mod 5, so (1)x = 4 mod 5, so x = 4 mod 5. Check for yourself that x = 4 mod 5 solves the original equation.

So do it the same, except "dividing by $n$" is instead done by "mulitplying by $n^*$". You can check the following yourself:
$0^* = undefined. 1^* = 1, 2^* = 3, 3^* = 2, 4^* = 4.$

Note that doing everything modulo n, where n is not a prime, is more difficult, because there will be non-zero (modulo n) numbers that don't have inverses.
Ex: Solve 2x = 1 mod 10 (i.e. find "2* mod 10"). There is no solution, so 2* is undefined mod 10. It gets complicated, because then some equations of the form 2x = a mod 10 won't have any solutions (2x = 3 mod 10), but others will (2x = 4 mod 10).
So the prime case is the simplest - and that's your case with this "mod 5" problem.
• Sep 19th 2012, 07:56 AM
jojo7777777
Re: congruence modulo 5
I'm grateful to you for your help.....however, I still have difficulty to solve the matrix according to the rules, I left with a matrix of the form:
1 2 4 -2 0 |2
0 1 -2 -4 -4 |1
0 0 1 3 0 | 0
0 0 0 0 0 |1
0 0 0 0 0 |-2
which is inconsistent, so where did I fail?
• Sep 19th 2012, 03:43 PM
johnsomeone
Re: congruence modulo 5
I can't look at that and check the steps you took. I can say that when I did it quickly, I also got "no solution - inconsistent equations" result. I didn't double check my work, but since you and I agree, I assume that's right.

Be aware that there's nothing "funny" going on here about the "mod 5" that's causing there to be no solutions. It's simply an inconsistent system of equations (geometrically, parallel lines and such - though the geometric interpretation is a bit strained when working mod 5). The same thing can happen when dealing with systems of equations over the real numbers.
Ex:
2x + y - z = 4
x - 3y + 2z = -1
4x - 5y + 3z = 1
Or, even more transparently:
Ex:
x - 2y = 3
x - 2y = 5
• Sep 20th 2012, 07:01 AM
jojo7777777
Re: congruence modulo 5
Thank you very much...!!!