\(x^3 = 1\) mod \(p\) => \((x+1)^p = x^p + 1\) mod \({p^3}\)

Let \(p\) be a prime. And let \(x\) be an integer such that \(x \neq 1 \pmod p\) but \(x^3 \equiv 1 \pmod p\). Show that \[(x+1)^ p \equiv x^p + 1 \pmod {p^3}.\]

Source: 小新老师

Proof 1 (Based on an idea from 申强老师) (参考微信公众号“申强奥数”)

First, given that \(p\) is a prime and has a non-trivial cubic root, we have \(3 | (p - 1)\), therefore \(p \equiv 1 \pmod 6\).

Consider \(f(t) = (t+1)^p - t^p - 1\). Let \(\omega\) be a root of \(t^2 + t + 1 = 0\), i.e. \(\omega \neq 1\) and \(\omega^3 = 1\). Since \((\omega+1) = -\omega^2\), we have \((\omega+1)^6 = 1\). Hence for \(p\equiv 1 \pmod 6\), we have \[ f(\omega) = (\omega+1)^p - \omega^p - 1 = 0. \] Also note that \[f'(\omega) = p(\omega+1)^{p-1} - p\omega^{p - 1} = 0.\] Therefore \((t^2 + t + 1)^2\) is a factor of \((t+1)^p - t^p - 1\).

Note that all coefficients of the polynomial \((t+1)^p - t^p - 1 = \sum_{i=1}^{p-1} {p \choose i} x^{p-i}\) are multiple of \(p\) since \(p\) is prime. Therefore \[ f(t) = (t+1)^p - t^p - 1 = p (t^2 + t + 1)^2 g(t) \] where \(g(t)\) is a monic polynomial of degree \(p-5\). It is worth noting that all coefficients of \(g(t)\) are also integers.

Finally, since \(x \neq 1 \pmod p\) but \(x^3 \equiv 1 \pmod p\), we have \(p | (x^2+x+1)\), therefore \[ p^3 | (x+1)^p - x^p - 1 \] which implies \((x+1)^ p \equiv x^p + 1 \pmod {p^3}\).

Proof 2 (Sketch only) By 小新老师

Proof 3 (Extended from the sketch above but without lifting)

First, given that \(p\) is a prime and has a non-trivial cubic root, we have \(3 | (p - 1)\), therefore \(p \equiv 1 \pmod 6\).

Let \(G\) be the multiplicative group of integers modulo \(p^3\). Since \(|G| = \phi(p^3) = p^2(p-1)\) where \(\phi\) is Euler’s totient function, Cauchy’s theorem states that \(G\) contains an element of order \(3\) , i.e. there exists non-trivial \(y\) such that \(y^3 \equiv 1 \pmod {p^3}\). Apparently we also have \((y^2)^3 \equiv 1 \pmod {p^3}\) and \(y^3 \equiv (y^2)^3 \equiv 1 \pmod {p}\).

From \(y \neq 1\) and \(y^3 \equiv 1 \pmod {p^3}\), we have \(y^2 + y \equiv -1 \pmod {p^3}\), hence \[(y+1)^3 = y^3 + 3y^2 + 3y + 1 \equiv -1 \pmod {p^3}. \tag{1}\] Since \(p \equiv 1 \pmod 6\), we further have \[(y+1)^p \equiv y^p + 1 \equiv y + 1 \pmod {p^3}. \tag{2}\]

From \(y^3 - x^3 = (y-x)(y^2 + x^2 + 1) \equiv 0 \pmod{p}\), we have either \(y \equiv x\) or \(y^2 \equiv x\). Either way, we proved that there exists a non-trivial cubic root of \(p^3\) that is equivalent to \(x\) modulo \(p\), where \(x\) is a non-trivial cubic root of \(p\) .

Let \(x\) be a non-trivial cubic root of \(p\) and let \(y\) be a non-trivial cubic root of \(p^3\) and \(y \equiv x \pmod p\). Note that \(x \neq 0 \pmod {p}\) and \(x \neq -1 \pmod {p}\), hence by the Lemma below:

Lemma \((x+p)^p - x^p \equiv p^2 \pmod {p^3}\) if \(p\) is prime and \(x\) is not a multiple of \(p\).

The proof is left to the reader.

Hint:

1. For every prime \(p\) and \(0 < i < p\), we have that \(p\) divides the binomial coefficient \({p \choose i}\).
2. Fermat’s little theorem.

we have \[(y+1)^p - (x+1)^p \equiv y^p - x^p \equiv p^2 \pmod {p^3}. \tag{3}\]

Finally combining Equation 2 and Equation 3, we obtain \[(x+1)^ p - x^p \equiv (y+1)^p - y^p \equiv 1 \pmod {p^3}, \tag{4}\] which implies \((x+1)^ p = x^p + 1 \pmod {p^3}\).