What It Means to Solve a System Modulo \(p\)
When a linear system is considered modulo a prime \(p\), its variables and coefficients belong to the finite field \(\mathbb{F}_p\). The elements of this field can be represented by \(0,1,\dots,p-1\), and all addition, subtraction, and multiplication are reduced modulo \(p\). For example, in \(\mathbb{F}_5\), \(3+4=2\), since \(7\) and \(2\) have the same remainder modulo \(5\). Division by a nonzero field element means multiplication by its multiplicative inverse in \(\mathbb{F}_p\).
Consider a system with \(m\) equations and \(n\) unknowns. In matrix form it is \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(\mathbf{A}\in\mathbb{F}_p^{m\times n}\), \(\mathbf{x}\in\mathbb{F}_p^n\), and \(\mathbf{b}\in\mathbb{F}_p^m\). A solution is a column \(\mathbf{x}\) in \(\mathbb{F}_p^n\) for which every equation holds in the field. We row-reduce the augmented matrix \([\mathbf{A}\mid\mathbf{b}]\), performing every arithmetic operation modulo \(p\).
As in row reduction over other fields, the allowed operations are swapping rows, multiplying a row by a nonzero field element, and adding a multiple of one row to another. Each operation preserves the solutions: swapping equations does not change which \(\mathbf{x}\) satisfy all of them; multiplying an equation by a nonzero scalar gives an equivalent equation; and adding a multiple of one equation to another preserves equivalence because the original row can be recovered by subtracting that same multiple. Thus a row-reduced augmented matrix describes exactly the solutions of the original system.
Reading Consistency and All Solutions
In an echelon form, a row with zero entries in all coefficient columns but a nonzero augmented entry represents an equation \(0=c\), where \(c\ne0\) in \(\mathbb{F}_p\). This equation cannot hold, so the system is inconsistent. If there is no such row, the equations can be solved from the bottom pivot row upward. Variables in non-pivot columns may be assigned any values in \(\mathbb{F}_p\); after those choices, the pivot equations determine the pivot variables.
Proof. Suppose first that the reduced augmented matrix contains a row \([0\ \cdots\ 0\mid c]\) with \(c\ne0\). Its equation is \(0=c\), which is false in a field when \(c\ne0\). No \(\mathbf{x}\) can satisfy the reduced system, and row operations preserve the solution set, so the original system is inconsistent. Conversely, suppose there is no such row. Each nonzero row then has a pivot in a coefficient column. Choose any values for the free variables. Starting with the last nonzero row and proceeding upward, each pivot equation has one pivot variable whose value can be solved for: its coefficient is nonzero and therefore has an inverse in \(\mathbb{F}_p\). The resulting values satisfy each row, so the system is consistent. Every solution must use some values for its free variables, and its pivot variables must then satisfy the same pivot equations. Solving those equations upward forces exactly the values just described. Therefore the procedure produces every solution, and distinct assignments to the free variables give distinct solutions. \(\square\)
This also explains the number of solutions in a consistent system. If there are \(f\) free variables, then each can be assigned any of the \(p\) field elements, independently. There are \(p^f\) assignments, and the theorem shows that each assignment produces exactly one solution. Thus a consistent system has \(p^f\) solutions. In particular, it has a unique solution exactly when there are no free variables.
Worked Systems
Worked Example: A Unique Solution over \(\mathbb{F}_7\)
Solve the system \(2x+y=4\), \(x+3y=5\) over \(\mathbb{F}_7\). All entries and operations below are interpreted modulo \(7\).
Write the augmented matrix and swap its rows to put a \(1\) in the first pivot position. Then subtract twice the first row from the second:
The second pivot is \(2\). Its inverse in \(\mathbb{F}_7\) is \(4\), since \(2\cdot4=8=1\) in the field. Multiply the second row by \(4\), then subtract \(3\) times that row from the first:
There is a pivot in each variable column, so \(x=0\), \(y=4\) is the unique solution. Check: \(2(0)+4=4\), and \(0+3(4)=12=5\) modulo \(7\). Both original equations hold.
Worked Example: Multiple Solutions over \(\mathbb{F}_5\)
Solve the system \(x+2y+z=1\), \(2x+4y+2z=2\), \(x+y=3\) over \(\mathbb{F}_5\). The second equation is included in the row reduction rather than discarded in advance.
Subtract twice the first row from the second, then subtract the first row from the third. Since \(-1=4\) in \(\mathbb{F}_5\), the resulting matrix is:
Move the nonzero row above the zero row, then multiply it by \(4\), the inverse of \(4\) in \(\mathbb{F}_5\). Finally subtract twice the new second row from the first:
The equations are \(x+4z=0\) and \(y+z=3\). The variable \(z\) is free; set \(z=t\), where \(t\in\mathbb{F}_5\). Since \(-4=1\) modulo \(5\), the first equation gives \(x=t\). The second gives \(y=3-t\). Hence every solution is \((x,y,z)=(t,3-t,t)\) for \(t\in\mathbb{F}_5\). There are five solutions.
Check: Substituting this expression into the first left-hand side gives \(t+2(3-t)+t=6=1\) modulo \(5\). The second left-hand side is \(2t+4(3-t)+2t=12=2\) modulo \(5\). The third is \(t+(3-t)=3\). Each equation holds for every \(t\in\mathbb{F}_5\).
Worked Example: An Inconsistent System over \(\mathbb{F}_3\)
Determine whether \(x+y=1\), \(2x+2y=0\) has a solution over \(\mathbb{F}_3\). Subtract twice the first row from the second. Because \(0-2=-2=1\) modulo \(3\), the reduction gives:
The last row asserts \(0=1\) in \(\mathbb{F}_3\), which is impossible. Therefore the system is inconsistent. This row records the conflict directly: twice the first left-hand side is the second left-hand side, but twice its right-hand side is \(2\), not \(0\), in \(\mathbb{F}_3\).
Why the Field and the Arithmetic Matter
The procedure resembles ordinary row reduction, but its arithmetic is not real arithmetic. A nonzero element of \(\mathbb{F}_p\) can be used as a pivot because it has an inverse; a zero pivot cannot be inverted. For example, \(2\) is invertible modulo \(5\), with inverse \(3\), because \(2\cdot3=6=1\) modulo \(5\). Thus solving \(2x=1\) over \(\mathbb{F}_5\) gives \(x=3\), not a real-number expression \(x=\tfrac12\).
Common mistake: dividing by a field element as if it were a real number. From \(2x=1\) modulo \(5\), writing \(x=\tfrac12\) does not give an element in the chosen representatives \(0,1,2,3,4\), and treating it as an ordinary fraction obscures the field operation. The correct step is to multiply by the modular inverse: \(x=3\cdot1=3\) modulo \(5\). Check: \(2\cdot3=6=1\) modulo \(5\).
It is also important to reduce the augmented column along with the coefficient columns. A pivot in a coefficient column identifies a variable that can be solved for; a nonzero entry in the augmented column with no coefficient pivot signals inconsistency. When no such conflict occurs, free variables must range over \(\mathbb{F}_p\), not over the real numbers. A parameter such as \(t\) in the second example has exactly five possible values.
These solutions are useful whenever the unknowns themselves represent quantities with only finitely many possible values. The central practice is systematic: reduce modulo the prime at each step, inspect the augmented rows for a contradiction, and then state the solution set using field-valued free parameters. Substitution into the original equations completes the check.
Check Your Understanding
Use arithmetic in the stated field throughout, and substitute any proposed solutions into the original equations.
- Over \(\mathbb{F}_5\), solve \(x+2y=4\), \(3x+y=1\). Is the solution unique?
- Over \(\mathbb{F}_3\), solve \(x+y+z=2\), \(2x+2y+2z=1\). Is the system consistent?
- Over \(\mathbb{F}_7\), solve \(x+2y+z=3\), \(2x+4y+2z=6\). Express every solution using a free variable.
- Explain why a row \([0\ 0\ 0\mid 2]\) proves inconsistency over \(\mathbb{F}_5\).
- How many solutions does a consistent system over \(\mathbb{F}_3\) have if its reduced form has two free variables?
