$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....
-
2Let $n>2$. Then the congruence has exactly two solutions **iff** $n$ has a primitive root. – 2012-04-24
-
0Thanks. Couldn't a identical proof be applied to composite numbers too? Why is this unique to prime numbers? – 2012-04-24
-
1Because 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. – 2012-04-24
-
0Thanks! One final thing- what would the 4 roots of your example be? – 2012-04-25
-
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.