Integers with Prime Values of Sigma Function

From ProofWiki
Jump to: navigation, search

Theorem

The sequence of integer whose $\sigma$ value is prime begins:

\(\displaystyle \sigma \left({2}\right)\) \(=\) \(\displaystyle 3\) $\quad$ $\quad$
\(\displaystyle \sigma \left({4}\right)\) \(=\) \(\displaystyle 7\) $\quad$ $\quad$
\(\displaystyle \sigma \left({9}\right)\) \(=\) \(\displaystyle 13\) $\quad$ $\quad$
\(\displaystyle \sigma \left({16}\right)\) \(=\) \(\displaystyle 31\) $\quad$ $\quad$
\(\displaystyle \sigma \left({25}\right)\) \(=\) \(\displaystyle 31\) $\quad$ $\quad$
\(\displaystyle \sigma \left({64}\right)\) \(=\) \(\displaystyle 127\) $\quad$ $\quad$
\(\displaystyle \sigma \left({289}\right)\) \(=\) \(\displaystyle 307\) $\quad$ $\quad$

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


Proof

Apart from $2$, all primes are odd.

From Sigma Function Odd iff Argument is Square or Twice Square, for $\sigma \left({n}\right)$ to be odd it needs to be of the form $m^2$ or $2 m^2$.

Suppose $n$ has two coprime divisors $p$ and $q$, each to power $k_p$ and $k_q$ respectively.

Then $\sigma \left({n}\right)$ will have $\sigma \left({p^{k_p} }\right)$ and $\sigma \left({q^{k_q} }\right)$ as divisors.

Hence $\sigma \left({n}\right)$ will not be prime.

So for $\sigma \left({2}\right)$ to be prime, $n$ can have only one prime factor.


This gives possible values for $n$ as:

powers of $2$, either odd or even

or:

even powers of a prime number.


These can be investigated in turn, using Sigma Function of Power of Prime:

$\sigma \left({p^k}\right) = \dfrac {p^{k+1} - 1} {p - 1}$

Note that as $\sigma \left({2^k}\right) = \dfrac {2^{k + 1} - 1} {2 - 1} = 2^{k + 1} - 1$ it is necessary for powers of $2$ merely to report the appropriate Mersenne prime.

Hence when $k + 1$ is not prime, $\sigma \left({2^k}\right)$ will not be prime and there is no need to test it.


Thus we test all $n$ such that:

$n = p^{2 k}$ for prime $p$
$n = 2^k$ where $k + 1$ is prime

and so:

\(\displaystyle \sigma \left({2}\right)\) \(=\) \(\displaystyle 2^2 - 1\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 3\) $\quad$ which is a Mersenne prime $\quad$
\(\displaystyle \sigma \left({4}\right)\) \(=\) \(\displaystyle \sigma \left({2^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 2^3 - 1\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 7\) $\quad$ which is a Mersenne prime $\quad$
\(\displaystyle \sigma \left({9}\right)\) \(=\) \(\displaystyle \sigma \left({3^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {3^3 - 1} {3 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {26} 2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 13\) $\quad$ which is prime $\quad$
\(\displaystyle \sigma \left({16}\right)\) \(=\) \(\displaystyle \sigma \left({2^4}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {2^5 - 1} {2 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 31\) $\quad$ which is prime $\quad$
\(\displaystyle \sigma \left({25}\right)\) \(=\) \(\displaystyle \sigma \left({5^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {5^3 - 1} {5 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {124} 4\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 31\) $\quad$ which is prime $\quad$
\(\displaystyle \sigma \left({49}\right)\) \(=\) \(\displaystyle \sigma \left({7^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {7^3 - 1} {7 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {342} 6\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 57 = 3 \times 19\) $\quad$ which is not prime $\quad$
\(\displaystyle \sigma \left({64}\right)\) \(=\) \(\displaystyle \sigma \left({2^6}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {2^7 - 1} {2 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 127\) $\quad$ which is a Mersenne prime $\quad$
\(\displaystyle \sigma \left({121}\right)\) \(=\) \(\displaystyle \sigma \left({11^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {11^3 - 1} {11 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {1330} {10}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 133 = 7 \times 19\) $\quad$ which is not prime $\quad$
\(\displaystyle \sigma \left({169}\right)\) \(=\) \(\displaystyle \sigma \left({13^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {13^3 - 1} {11 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {2196} {12}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 183 = 3 \times 61\) $\quad$ which is not prime $\quad$
\(\displaystyle \sigma \left({289}\right)\) \(=\) \(\displaystyle \sigma \left({17^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {17^3 - 1} {17 - 1}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {4912} {16}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle 307\) $\quad$ which is prime $\quad$

Hence the sequence as given.

$\blacksquare$


Sources

but beware a mistake in this sequence.