$a^2 = 1\pmod{p}$ Could someone prove if $p$ is a prime number, $a$ can't be nontrivial?
Proof prime numbers can't have non-trivial roots?
-
1That demands some kind of specification what "nontrivial" means for you. (But remember that in a field, polynomials cannot have more roots than their degree). – 2012-04-24
2 Answers
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....
-
0modulo 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$. – 2012-04-25
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.