1
$\begingroup$

If $p$ is a prime and $a^2 ≡ 1$(mod $p$), prove that $a ≡ ± 1 $(mod $p$)

  • We are currently studying modular arithmetic and congruence and I came across this proof on my study set that I'm really not sure how to approach. We have gone over equivalence relations in mod arithmetic, equivalence classes (complete set of residues), and have gone through several mod arithmetic examples w/o variables. Looking through my notes and book I'm still not sure how to proceed with this problem, any help is appreciated.
$\endgroup$
  • 1
    $\begingroup$ This is based on the prime property. If $p$ divides $ab$, then $p$ divides at least one of $a$ or $b$. $\endgroup$ – Anurag A Feb 20 '16 at 21:00
  • 1
    $\begingroup$ It's trivial a,d has nothing to do with modular arithmetic: in a field, a polynomial of degree $n$ has at most $n$ roots, and $\pm 1$ are roots of $x^2-1$. $\endgroup$ – Bernard Feb 20 '16 at 21:02
3
$\begingroup$

This is actually a very classical result. The only square roots of $1$ modulo a prime are $+1$ and $-1$. The proof is easy, and I'll give you the beginning. Suppose that $a^2 \equiv 1 \mod p$ where $p$ is an odd prime (for the case $p = 2$, it's trivial). $$a^2 - 1 \equiv 0 \mod p$$ $$(a - 1)(a+1) \equiv 0 \mod p$$

Thus, $p | (a-1)$ or $p | (a+1)$, but not both because $\text{gcd}(a - 1, a + 1)$ is always at most $2$.
Take the needed cases.

$\textbf{Edit}$
And yes, as someone mentioned in the comments, you can always use the fact that an $n$-degree polynomial has at most $n$ roots in a field, assuming you're allowed to use theorems from Abstract Algebra.

$\endgroup$
1
$\begingroup$
  1. If $D$ is an integral domain, then $a^{2} =1$ has exactly two solutions: $a^{2} =1 \iff a^{2} - 1 = 0 \iff (a+1)(a-1) = 0$ and since $D$ does not have zero divisors, we have $a = \pm 1$ as the only possible solutions. In relation to your problem, $D = \mathbb{Z}_{p}$ is known to be an integral domain.

  2. Also, the hypothesis implies that $a \in G = \mathbb{Z}_{p-1}$ - a cyclic group and so if $a^{2} = 1 = b^{2}$ and $a$ and $b$ are non-identity elements, then $G$ would have two distinct subgroups of the same order, which is not possible in a cyclic group.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.