Prime to Own Power minus 1 over Prime minus 1 being Prime

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z_{>1}$ be an integer greater than $1$.

Then $\dfrac {n^n - 1} {n - 1}$ is a prime for $n$ equal to:

$2, 3, 19, 31$

This sequence is A088790 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).


Proof



Note that if $4 p + 1$ is prime for prime $p$, then $\dfrac {p^p - 1} {p - 1}$ is divisible by $4 p + 1$:


Let $q = 4 p + 1$ be prime.

By First Supplement to Law of Quadratic Reciprocity:

$\paren {\dfrac {-1} q} = 1$

that is, there exists some integer $I$ such that $I^2 \equiv -1 \pmod q$.


Then:

\(\ds \paren {1 + I}^4\) \(=\) \(\ds \paren {1 + 2 I + I^2}^2\) Square of Sum
\(\ds \) \(\equiv\) \(\ds \paren {2 I}^2\) \(\ds \pmod q\) Congruence of Powers
\(\ds \) \(\equiv\) \(\ds -4\) \(\ds \pmod q\)

and thus:

\(\ds p^p\) \(\equiv\) \(\ds p^p \paren {1 + I}^{q - 1}\) \(\ds \pmod q\) Fermat's Little Theorem
\(\ds \) \(\equiv\) \(\ds p^p \paren {1 + I}^{4 p}\) \(\ds \pmod q\)
\(\ds \) \(\equiv\) \(\ds p^p \paren {-4}^p\) \(\ds \pmod q\)
\(\ds \) \(\equiv\) \(\ds \paren {-4 p}^p\) \(\ds \pmod q\)
\(\ds \) \(\equiv\) \(\ds 1^p\) \(\ds \pmod q\)
\(\ds \) \(\equiv\) \(\ds 1\) \(\ds \pmod q\)

Hence $q \divides \paren {p^p - 1}$.

Obviously $q > p - 1$.

Therefore $q \divides \dfrac {p^p - 1} {p - 1}$.


Sources