# Proof prime numbers can't have non-trivial roots?

$a^2 = 1\pmod{p}$ Could someone prove if $p$ is a prime number, $a$ can't be nontrivial?

-
That demands some kind of specification what "nontrivial" means for you. (But remember that in a field, polynomials cannot have more roots than their degree). – Henning Makholm Apr 24 '12 at 14:23

This is pretty standard:

$$a^2-1 \equiv 0 \mod p$$

means

$p| (a-1)(a+1)$.

Since $p$ is prime, we get either $p|a-1$ or $p|a+1$.

Thus

$a\equiv 1 \mod p$ or $a \equiv -1 \mod p$.

P.S. If you know what a primitive root is, you can try to prove the following generalization: If there is a primitive root mod $n$, then the equation $x^2=1 \mod n$ has only two solutions....

-
Let $n>2$. Then the congruence has exactly two solutions iff $n$ has a primitive root. – André Nicolas Apr 24 '12 at 15:25
Thanks. Couldn't a identical proof be applied to composite numbers too? Why is this unique to prime numbers? – user26649 Apr 24 '12 at 18:37
Because if $n | (x-1)(x+1)$ it doesn't follow that $n|x-1$ or $n|x+1$. This property for integers is equivalent to $n$ being prime. In rings this is the actual definition for prime elements. A simple example: $8 | (5-1)(5+1)$ but $8$ divides neither. We actually have $4|5-1$ and $2|5+1$ thus $4 \cdot 2 |(5-1)(5+1)$....for this reason modulo $8$ the equation $x^2=1$ has 4 solutions, for the non-trivial ones, $8|(x-1)(x+1)$ but it doesn't divide either. – N. S. Apr 24 '12 at 19:33
Thanks! One final thing- what would the 4 roots of your example be? – user26649 Apr 25 '12 at 2:53
modulo 8, any odd number is a root. Also, modulo 3*5*7 for example, Chinese reminder theorem tells you that there are 8 roots, namely all numbers which are $\pm 1$ mod 3 and $\pm 1$ mod 5 and $\pm 1$ mod 7. The non trivial ones come from different signs, for example $29$ is a non trivial solution, which is $-1 \mod 3$, $-1 \mod 5$ and $+1 \mod 7$. – N. S. Apr 25 '12 at 13:57

The solution given by N.S. is good. Here is a slightly more "high level" look on it: It is well-known that $\mathbb{Z}_p$ (integers modulo $p$ with addition and multiplication) is a field (all the axioms can be checked directly; to show that $a\ne 0$ is invertible use the fact that $gcd(a,p)=1$ and so $ax+py = 1$ for some integers $x,y$).

Now, it is known that if $p(x)$ is a polynomial of degree $n$ over any field, then $p(x)$ has at most $n$ roots; this is so because of $p(x)$ has root $a$ then $(x-a)$ divides $p(x)$ and we can proceed by induction.

Now $x^2-1$ is a polynomial of degree 2 over the field $\mathbb{Z}_p$ and so it has at most two roots. We know of the two trivial roots $1,-1$ (-1 being $p-1$) and so there are no other roots.

-