Thread: Solving linear system under Z_p

Hi all, I need help with solving a linear system in a finite field, Z_7 and Z_11.

The original given linear system is

2x + 4y - 2z = 1
2x + y + z = 3
5x - 3y + 7z = 0

Under positive representation for Z_7 and Z_11, I get the following linear systems respectively

2x + 4y + 5z = 1
2x + y + z = 3
5x + 4y = 0

and

2x + 4y + 9z = 1
2x + y + z = 3
5x + 8y +7z = 0

I did the usual gaussian elimination, keeping all the coefficients in Z_7 and Z_11 respectively, and I got
Z_7: x = 0, y = 0, z = 3, determinant = 6
Z_11: x = 9, y = 5, z = 2, determinant = 6

The solutions my teacher gave were
Z_7: x = 0, y = 0, z = 4, determinant = 6
Z_11: x = 10, y = 8, z = 1, determinant = 6

However, I substituted his solutions into the respective linear systems, and they don't seem to be correct.

For example, for Z_7, for the equation
2x+y+z = 3, I get 2(0) + (0) + (4) = 4 != 3

For Z_11, for the equation
2x+y+z = 3, I get 2(10) + (8) + (1) = 7 != 3

Where did I go wrong?

Thank you.

Regards,
Rayne

Originally Posted by wu_weidong

2x + 4y - 2z = 1
2x + y + z = 3
5x - 3y + 7z = 0

Well, let's see what happens if you don't do anything fancy and solve this by substitution. I'm going to do this little step by little step as I get screwed up when I skip steps. I'll do this for Z_7.

2x + 4y + 5z = 1
2x + y + z = 3
5x + 4y = 0

Solving the bottom equation we get:
5x + 4y = 0

5x + 4y + 3y = 0 + 3y

5x = 3y

In Z_7 the multiplicative inverse of 5 is 3, so:
3(5x) = 3(3y)

x = 2y

Put x = 2y into the remaining equations:
2(2y) + 4y + 5z = 1 ==> 4y + 4y + 5z = 1
2(2y) + y + z = 3 ==> 4y + y + z = 3

Which leads to
y + 5z = 1
5y + z = 3

I'm going to solve the bottom equation for z.
5y + z = 3

2y + 5y + z = 2y + 3

z = 2y + 3

Put this into the top equation:
y + 5(2y + 3) = 1

y + 3y + 1 = 1

4y + 1 = 1

4y + 1 + 6 = 1 + 6

4y = 0

Since Z_7 has no zero divisors, I get that y = 0.

z = 2(0) + 3 = 3

x = 2(0) = 0

So x = 0, y = 0, z = 3.

-Dan

Originally Posted by wu_weidong

2x + 4y - 2z = 1
2x + y + z = 3
5x - 3y + 7z = 0

I'll do it this time for Z_11 and by the method of adding and subtracting equations.
2x + 4y + 9z = 1
2x + y + z = 3
5x +8y + 7z = 0

I'll start by considering the top and middle equations:
2x + 4y + 9z = 1
2x + y + z = 3

We can subtract these to eliminate x. So:
3y + 8z = 9

Thus our system is:
2x + 4y + 9z = 1
(0)x + 3y + 8z = 9
5x +8y + 7z = 0

Now for the top and bottom equations:
2x + 4y + 9z = 1
5x +8y + 7z = 0 ==> 7(5x + 8y + 7z) = 7(0)

2x + 4y + 9z = 1
2x + y + 5z = 0

Now subtract:
3y + 4z = 1

Now our system is:
2x + 4y + 9z = 1
(0)x + 3y + 8z = 9
(0)x + 3y + 4z = 1

Now subtract the middle and bottom equations to eliminate y:
4z = 8

z = 2.

Our system is
2x + 4y + 9z = 1
(0)x + 3y + 8z = 9
(0)x + (0)y + z = 2

Now for back substitution:
z = 2

3y + 8(2) = 9

So
3y + 5 = 9

3y + 5 + 6 = 9 + 6

3y = 4

4(3y) = 4(4)

y = 5

So
2x + 4y + 9z = 1

2x + 4(5) + 9(2) = 1

2x + 9 + 7 = 1

2x + 5 = 1

2x + 5 + 6 = 1 + 6

2x = 7

6(2x) = 6(7)

x = 9

Thus
x = 9, y = 5, z = 2

(So I agree with both of your solutions.)

-Dan

Originally Posted by topsquark

(So I agree with both of your solutions.)

-Dan

Thank you. That's why I didn't understand my teacher's answers, and he insisted they were correct.

I think you can also use Cramer's rule here.

Because since Z_7 and Z_11 are finite fields the set of all solutions forms a proper vector space and hence the theorems from linear algebra will apply.