A problem I thought about during my walk

Today’s walk problem was a deceptively simple congruence: solve $a^2 \equiv 1 \pmod p$ for an odd prime $\mathrm{p.}$

$p$At first glance the equation looks almost trivial, but it turned out to reveal something fundamental about the nature of primes and why arithmetic mod $p$ feels so clean compared to arithmetic mod a composite number.

The first step is to rewrite the equation in a way that exposes its structure. Starting from $a^2 \equiv 1 \pmod p$, one can subtract 1 from both sides to get $a^2 - 1 \equiv 0 \pmod p$. This factors into $(a - 1)(a + 1) \equiv 0 \pmod p$, which says that the prime $p$ divides the product $(a - 1)(a + 1)$. Everything hinges on understanding what a prime does when it divides a product. If $p$ divides $ab$, then it must divide one of the two factors. Applying that fact here gives the entire solution. Either $p$ divides $a - 1$, in which case $a \equiv 1 \pmod p$, or it divides $a + 1$, in which case $a \equiv -1 \pmod p$. No other possibilities exist, so these two residues form the complete set of solutions.

The contrast with the composite case is striking. If the modulus were not prime, for example $n = 8$, then $(a - 1)(a + 1) \equiv 0 \pmod 8$ would not force either factor to vanish modulo 8. Taking $a = 3$ gives $2 \cdot 4 = 8 \equiv 0 \pmod 8$ even though neither $2$ nor $4$ is divisible by 8. In composite arithmetic, products can vanish without either factor doing so, and the clean factor by factor logic that worked for primes does not apply. This is why congruence problems modulo composite numbers often behave erratically, while modulo a prime they fall neatly into place.

The deeper significance of this small exercise was given to me by ChatGPT: it lies in the behavior of primes themselves. The fact that a prime dividing a product forces it to divide one of the factors is not just a convenient trick. It is the structural reason primes support a kind of arithmetic rigidity. This rigidity explains why cancellation works modulo a prime, why every nonzero residue mod $p$ has a multiplicative inverse, and why the integers modulo $p$ form a field. When working mod $p$, the algebra does not fray or tangle. Arguments stay linear, deductions feel sharper, and factorization behaves exactly as intuition expects.

A simple congruence like $a^2 \equiv 1 \pmod p$ is therefore more than an exercise. It is a window into the foundational property that gives primes their power: the inability to be hidden inside a product.