Proof That [x ≡ ±1 mod p Where p Is Prime] ⟺ [x Is Its Own Inverse] (Assume x Is Positive)

If \(x ≡ 1 \bmod p\) or \(x ≡ -1 \bmod p\), then \(x^2 ≡ 1 \bmod p \), proving that \(x\) is its own inverse.

Conversely, if \(x\) is its own inverse modulo \(p\), then \(x^2 ≡ 1 \bmod p \), which means:

$$\begin{gather} p | x^2 - 1 \\ p|(x+1)(x-1)\end{gather}$$

According to this lemma, \(p\) should be able to divide \(x+1\) or \(x-1\), so \(x ≡ 1 \bmod p\) or \(x ≡ -1 \bmod p\).

Styles

(uses cookies)