Eliminate over finite fields and count solution fibers

Try

A three-input device adds and multiplies residues modulo a prime p. Its output is

A(x,y,z)=(x+y, 2y+z, x+3y+z).

We want the requested output (1,1,c). Before solving, add the first two output coordinates. Their sum is exactly the third, over every field. Therefore c must equal 2 modulo p. For p=2 that means c=0, not the integer representative 2 outside the displayed residue list. For p=3 or 5 it means c=2.

This is a consistency certificate. It does not yet construct every input or explain how many there are. Try y=0 and y=1 for each of the three primes and recover x,z from the first two equations. Distinct values of y produce distinct inputs even when some other coordinates coincide.

Predict

Fₚ, pronounced “the field with p elements,” consists of residues modulo a prime p, represented here by 0 through p−1. Arithmetic wraps around: in F₅, −1=4 and 3·2=1, so 2 is the multiplicative inverse of 3. Equality means congruence, not equality of the chosen ordinary integer representatives.

Predict whether a nonzero coefficient always has an inverse. Over Fₚ it does: if a is an integer from 1 through p−1, then gcd(a,p)=1. Bézout gives integers s,t satisfying sa+tp=1; reduction modulo p gives sa=1. That proof explains exactly where primality enters. Over residues modulo 4, the nonzero element 2 has no inverse: multiplying it by any residue gives 0 or 2.

Predict why a zero pivot candidate need not mean no solution. We may exchange rows or choose a later column. In the worked system, even in characteristic 2, the second equation has coefficient 1 on z, so it still supplies an independent pivot. A procedure that insists on dividing the displayed coefficient 2 would fail unnecessarily.

Experiment

Use the explorer with the fixed matrix below. Choose p=2,3 or 5 and change c. Before revealing a result, predict whether the request is consistent and how many solutions it should have. For a consistent request, check that every displayed triple satisfies all three equations modulo p. For an inconsistent request, identify the contradictory final row rather than describing an unsuccessful search as impossibility.

The same equations in different prime fields

Solve x+y=1, 2y+z=1 and x+3y+z=c, with every equality taken modulo p. A residue is an exact field element, not a rounded real number.

Prime p2357 Last balance c012 Reset

Changing p reduces the current c modulo the new prime. Predict which c makes the third equation the sum of the first two.

Consistent: exactly 3 distinct solution triples. Rank 2; nullity 1. The condition is c ≡ 2 modulo 3.

The image contains 9 of the 27 possible right-hand sides. Each right-hand side in the image has 3 preimages. This panel varies only right-hand sides (1,1,c).

Exact elimination trace

Each displayed row is [x coefficient, y coefficient, z coefficient | right-hand side]. All row operations are reversible in this prime field.

1. Start: all entries are residues modulo 3.

   [1, 1, 0 | 1]

   [0, 2, 1 | 1]

   [1, 0, 1 | 2]

2. Row 3 ← row 3 − 1 × row 1 (mod 3).

   [1, 1, 0 | 1]

   [0, 2, 1 | 1]

   [0, 2, 1 | 1]

3. Multiply row 2 by 2: 2 × 2 ≡ 1 (mod 3).

   [1, 1, 0 | 1]

   [0, 1, 2 | 2]

   [0, 2, 1 | 1]

4. Row 1 ← row 1 − 1 × row 2 (mod 3).

   [1, 0, 1 | 2]

   [0, 1, 2 | 2]

   [0, 2, 1 | 1]

5. Row 3 ← row 3 − 2 × row 2 (mod 3).

   [1, 0, 1 | 2]

   [0, 1, 2 | 2]

   [0, 0, 0 | 0]

All solution triples

Choose the parameter t=y. For t=0,…,2, use (1−t, t, 1−2t), reducing each coordinate modulo 3. The table lists every solution exactly once. For odd p the reduced matrix instead uses z as its nonpivot coordinate; z=1−2t is a bijective change of parameter because 2 has an inverse. For p=2, y itself is the nonpivot coordinate.

t	(x,y,z)
0	(1, 0, 1)
1	(0, 1, 2)
2	(2, 2, 0)

Try p=2: the coefficient 2 becomes zero, but the coefficient of z remains 1. Explain why the rank still equals two. These temporary controls do not record completion; justify the general counting rule in the written tasks.

Here is a separate written elimination, valid for all three primes. Use the augmented matrix and replace row 3 by row 3 minus row 1 minus row 2. This is two reversible row additions.

Row	Before: x,y,z coefficients	Right side	After
1	(1,1,0)	1	x+y=1
2	(0,2,1)	1	2y+z=1
3	(1,3,1)	c	0=c−2

If c≠2 in the field, the final equation is a contradiction. If c=2, set y=t freely. Then

(x,y,z)=(1−t,t,1−2t), with t∈Fₚ.

Every such triple satisfies the system; conversely, every solution must have this form because its middle coordinate determines t and the first two equations determine the others. This proves completeness of the list, not just membership of some examples.

Field	Consistent c	Triples in increasing parameter order
F₂	0	(1,0,1); (0,1,1)
F₃	2	(1,0,1); (0,1,2); (2,2,0)
F₅	2	(1,0,1); (0,1,4); (4,2,2); (3,3,0); (2,4,3)

The rank is 2 over every one of these fields: the third row is the sum of the first two, and the first two rows are independent. Indeed, in a zero combination of them the x coordinate forces the first coefficient to vanish, and the z coordinate then forces the second. The kernel is the span of (−1,1,−2), whose middle coordinate is 1 even in characteristic 2.

Understand

Why does elimination preserve the solution set? Swapping rows has itself as inverse. Adding λ times a different row is undone by adding −λ times that same, unchanged row. Scaling a row by a nonzero field element is undone by its reciprocal. Perform these operations on the right-hand column too. Their inverses prove equivalence in both directions; retaining only one implication could add or remove solutions. Scaling by zero is never a legal equivalence operation.

Gaussian elimination searches the unprocessed portion for a nonzero entry, moves its row if needed, scales the pivot to 1, and clears the other entries in its column. Columns with no new pivot become free variables. Because the matrix is finite, the process stops. A row of zero coefficients with nonzero right side certifies inconsistency; otherwise solving the pivot equations in terms of free variables gives every solution. All arithmetic here is exact field arithmetic, so there is no numerical tolerance for an “almost zero” pivot.

The solution-count theorem is more general than the worked elimination. Let A map F_qⁿ to F_qᵐ linearly, where F_q is a field containing q elements and A has rank r. If b is attainable, choose one input x₀ with Ax₀=b. Then

Ax=b if and only if x=x₀+z for some z∈ker A.

For the forward direction, A(x−x₀)=b−b=0. For the reverse direction, A(x₀+z)=b+0. Addition of x₀ is injective because cancellation recovers z, and the forward direction proves surjectivity onto the fiber. A fiber is the set of all inputs giving one specified output. Thus every nonempty fiber is a translated copy of the kernel; it need not itself be a vector subspace, since it need not contain zero.

Rank-nullity over a field gives a kernel basis of n−r vectors. Each coordinate has q choices, and uniqueness of basis coordinates means no two different coordinate lists represent the same vector. Therefore each nonempty fiber has exactly q^(n−r) elements. An image basis has r vectors, giving qʳ attainable outputs. The full codomain has qᵐ elements, so exactly qᵐ−qʳ requests are inconsistent. These are three different counts: inputs above one output, attainable outputs, and all possible requested outputs. They satisfy qʳ·q^(n−r)=qⁿ because the nonempty fibers partition the input space.

For the worked 3×3 matrix the full image is the set of (u,v,u+v), which has p² elements, each with p inputs above it. Our experiment fixes u=v=1 and varies only c, so it examines just p requests, of which one is attainable. It does not enumerate the entire p³-element codomain. The count q⁰=1 is meaningful: a zero-dimensional vector space contains its zero vector, not no vectors.

The proof works for any finite field, including fields of prime-power size. It does not say that integers modulo every prime power form a field. For instance F₄ and Z/4Z have the same number of elements but different arithmetic. Over Z/4Z, the equation 2x=0 has solutions 0 and 2. Pretending to divide by 2 would discard one. Translation by a particular solution still describes fibers of an additive homomorphism, but the vector-space basis count is no longer justified over this ring.

Apply

Change the matrix to rows (1,1) and (1,−1), and request (u,v). Over an odd prime, addition and subtraction give x=(u+v)/2 and y=(u−v)/2, uniquely. Over F₂ the two equations coincide, so consistency requires u=v and there are two solutions. Explain why the earlier rank-2 result did not license assuming that every integer matrix has the same rank over every field.

For a fresh counting challenge, suppose a map F₅⁴→F₅³ has rank 2. There are 25 attainable outputs among 125 possible requests, and each attainable output has 25 inputs. Prove these numbers from basis coordinates, then check that 25·25=625 counts every input exactly once. If the input is chosen uniformly, the output is uniform on the image because all its fibers have the same size. A uniform request from the entire codomain is a different experiment: only one fifth of such requests are consistent.

Continue

A complete modular-system solution records the field, legal inverses, consistency conditions, all free parameters and the distinction between image and codomain. Exhaustive checking of a small example can catch arithmetic errors; reversibility and the fiber proof explain why the method works for arbitrary finite dimensions.

Review row operations and equivalent systems and rank-nullity for the general linear arguments. For the difference between finite fields and residue rings, return to finite-field structure. Counting bases and comparing spectra over different fields require these same field conventions.