3
$\begingroup$

I was reading Miller–Rabin primality test and there was a statement as:

$p$ is a prime iff $x^2 \cong 1\text{ mod }p \implies x \cong \pm 1\text{ mod }p$ for all $x$.

I was able to do it from left to right (a simple proof indeed), but I couldn't do the converse. I tried the following:

$x^2 \cong 1\text{ mod }p \implies (x-1)(x+1)\cong 0\text{ mod }p \implies p \text{ divides }(x-1)(x+1)$. But I wasn't able to proceed further. Any help would be great. Thanks...

$\endgroup$
19
  • 1
    $\begingroup$ Have you tried proving the contrapositive statement? $\endgroup$ Mar 7, 2020 at 11:57
  • 4
    $\begingroup$ Note that $\ p=25\ $ also satisfies $$x^2\equiv 1\mod p\implies x\equiv \pm 1 \mod p$$ Hence the statement is not true. $\endgroup$
    – Peter
    Mar 7, 2020 at 12:13
  • 3
    $\begingroup$ Miller Rabin only needs the direction from the left to the right. The test does not prove the primality. Every prime passes the test, but also some composite numbers. The result "composite" is always true, but the result "prime" might be false. $\endgroup$
    – Peter
    Mar 7, 2020 at 12:20
  • 1
    $\begingroup$ @Ankit Insisting that a statement is correct (because it is written on a website of a top university?) even after you've been given a simple counterexample is not the path to enlightenment. There are many errors on the web - even at reputable sites. Mathematical proof is not by authority. $\endgroup$ Mar 8, 2020 at 1:34
  • 1
    $\begingroup$ @BillDubuque The reason why we only need one direction is that Miller Rabin does not want to prove a number to be prime. It is only based on a condition that must be satisfied by every prime, but for every fixed set of bases we check infinite many composites pass it as well. $\endgroup$
    – Peter
    Mar 9, 2020 at 9:47

1 Answer 1

1
$\begingroup$

When $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is False

Assume that $p \not\in \{1,2,4,q^t,2q^t\}$ where $q$ is an odd prime and $t$ is a positive integer.

If $p$ is a power of $2$ greater than $4$, it is clear that $x=\frac{p}{2}-1$ shows the necessary since: $$\bigg(\frac{p}{2}-1\bigg)^2 \equiv \frac{p^2}{4}-p+1 \equiv 1 \pmod{p}$$

Let $p$ not be a power of $2$. Clearly, we have some odd prime $q \mid p$. Let $t$ be the highest power of $q$ dividing $p$, i.e. $q^t \mid \mid p$. Now, let $p=k \cdot q^t$.

Since $p \not\in \{1,2,4,q^t,2q^t\}$ , we must have $k>2$. Also, since $q$ is an odd prime and $t$ is a positive integer, $q^t>2$.

We will show that there exists $x$ such that $x^2 \equiv 1 \pmod{p}$ and $x \not\equiv \pm 1 \pmod{p}$. We allow: $$q^t \mid (x+1) \implies x=q^tn-1$$

Now, we need $k \mid (x-1)$. This is the same as $k \mid (q^tn-2)$. However, we know from the fact that $\gcd(k,q^t)=1$ that: $$q^tn \equiv 2 \pmod{k}$$ has a solution for $0<n<k$. Now, set $n$ such that this congruence is satisfied. It is clear that: $$k \cdot q^t \mid (x-1)(x+1) \implies x^2 \equiv 1 \pmod{p}$$

If $x \equiv 1 \pmod{p}$, we need $q^t \mid (x+1) \implies q^t \mid 2$ which is clearly false as $q^t>2$.

Similarly, if $x \equiv -1 \pmod{p}$, we need $k \mid (x-1) \implies k \mid 2$ which is again false as $k>2$.

This shows that $x \not\equiv \pm 1 \pmod{p}$. This proves that for these values of $p$, $x^2 \equiv 1 \pmod {p}$ does not imply $x \equiv \pm 1 \pmod{p}$.

When $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is True

Clearly, this is true for $p \in \{1,2,4\}$. We will show that it is true for $p=q^t$ and $p=2q^t$. Let $x^2 \equiv 1 \pmod{q^t}$. This shows that: $$q^t \mid (x-1)(x+1)$$ Since $q \nmid 2$, $q$ cannot divide both factors. This means that $q^t$ has to divide one of the factors completely. $$q^t \mid (x \pm 1) \implies x \equiv \pm 1 \pmod{q^t}$$

When $p=2q^t$, since $x^2 \equiv 1 \pmod{p}$, we will additionally have $x$ to be odd as $p$ is even. This gives an additional condition $x \equiv 1 \pmod{2}$ showing that $x \equiv \pm 1 \pmod{2q^t}$.

Summary

  • $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is True for $p \in \{1,2,4,q^t,2q^t\}$ where $q$ is an odd prime and $t$ is a positive integer.
  • $x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$ is False otherwise.

Counterexamples

The counterexamples are when for $p$ not prime: $$x^2 \equiv 1 \pmod{p} \implies x \equiv \pm1 \pmod{p}$$

From above, this is the set $\{1,4,q^a,2q^b\}$ where $q$ is an odd prime, $a$ and $b$ are positive integers, and $a>1$. Note that $2$ and $q$ are removed as they are prime.

$\endgroup$
5
  • $\begingroup$ To the user who gave the downvote, please do share your reason. $\endgroup$
    – Haran
    Mar 9, 2020 at 10:30
  • 1
    $\begingroup$ You've reinvented the wheel (cyclic group). More conceptually: $\,x^2\equiv 1\iff x\equiv \pm1\pmod{\!n}\,$ is true $\iff \Bbb Z_n^*$ is a cyclic group (i.e. a primitive root exists), as follows from basic group theory. There are many CRT examples here that show how to obtain nontrivial square roots of $1$ in the non-cyclic cases, e.g. here. $\endgroup$ Mar 9, 2020 at 15:58
  • $\begingroup$ @BillDubuque The user Peter had noticed the same when we were chatting. $\endgroup$
    – Haran
    Mar 9, 2020 at 17:13
  • 1
    $\begingroup$ These fundamental facts are proved in most elementary number theory and algebra textbooks. I see no mention of it anywhere on this page so I thought it would be worthwhile to emphasize it here. $\endgroup$ Mar 9, 2020 at 17:20
  • $\begingroup$ @Haran How do we chat on MSE? $\endgroup$ Mar 9, 2020 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .