Primes as differences of powers

Many prime numbers can be expressed as the difference of two powers.

Numbers $n$ such that $k^{n}-(k-1)^{n}$ is prime

We will now consider prime numbers of the form $k^{n}-(k-1)^{n}$. Of course the most famous such prime numbers are the Mersenne primes, which correspond to $k=2$.

Theorem KN1. Given integers $k$ and $n$ both greater than 1, a necessary but not sufficient condition for $k^{n}-(k-1)^{n}$ to be a prime number is for $n$ to also be prime. In other words, if $n$ is composite, then so is $k^{n}-(k-1)^{n}$.

Proof. If $n$ is composite, then it can be expressed as $n=ab$, where $a$ and $b$ are both integers greater than 1. A basic property of exponentiation is that $x^{ab}=(x^{a})^{b}=(x^{b})^{a}$. Therefore we can rewrite $k^{n}-(k-1)^{n}$ as $(k^{a})^{b}-((k-1)^{a})^{b}$ and obtain a divisor of $k^{n}-(k-1)^{n}$ thus: ${\frac {(k^{a})^{b}-((k-1)^{a})^{b}}{k^{a}-(k-1)^{a}}}$ (at least one other non-trivial divisor may be obtained by this principle, unless $n$ is the square of a prime). Clearly $1<k^{n-a}-(k-1)^{n-a}<k^{n}-(k-1)^{n}$, demonstrating that $k^{n}-(k-1)^{n}$ has divisors apart from 1 and itself and is therefore a composite number. ENDOFPROOFMARK

As a corollary to this, if $k^{n}-(k-1)^{n}$ is prime, then not only are all $k^{mn}-(k-1)^{mn}$ for $m>1$ composite, they are all divisible by $k^{n}-(k-1)^{n}$. For example, all numbers of the form $3^{2n}-2^{2n}$ (with $n>0$) are divisible by 5.

In the following table, we generally only list exponents less than 1000, since greater exponents, although corresponding to strong pseudoprimes, have not always been confirmed prime. As a consequence of the theorem above, the numbers in the exponents column should all be prime as well as the numbers in the primes column.

$k$	Exponents	A-number	Primes	A-number
2	2, 3, 5, 7, ...	A000043	3, 7, 31, 127, ...
3	2, 3, 5, 17, 29, 31, 53, 59, 101, 277, 647, ...	A057468	5, 19, 211, 129009091, ...	A058765
4	2, 3, 7, 17, 59, 283, 311, 383, 499, 521, 541, 599, ...	A059801	7, 37, 14197, 17050729021, ...	A129736
5	3, 43, 59, 191, 223, 349, 563, 709, 743, ...	A059802	61, 1136791005963704961126617632861, ...	A147667
6	2, 5, 11, 13, 23, 61, 83, 421, ...	A062572
7	2, 3, 7, 29, 41, 67, ...	A062573
8	7, 11, 17, 29, 31, 79, 113, 131, 139, ...	A062574
10	2, 3, 7, 11, 19, 29, 401, 709, ...	A062576	19, 271, 5217031, ...	A199819
11	3, 5, 19, 311, 317, ...	A062577
12	2, 3, 7, 89, 101, 293, ...	A062578
13	17, 31, 41, 47, 109, 163, 643, ...	A062579
19	2, ...	A062585
21		A062587
22		A062588
23		A062589
26		A062592
27		A062593
28		A062594
29		A062595
30		A062596
31		A062597
32		A062598
41	7, 11, 13, 67, ...	A062607
42	2, 3, 5, 47, 67, 103, ...	A062608
43	3, 13, 43, 211, ...	A062609
45	2, 5, 151, 223, 313, ...	A062611
46	3, ...	A062612
47	5, 17, 67, 73, 691, ...	A062613
49	2, 3, 7, 379, ...	A062615
52	2, 29, 109, 179, ...	A062618
53	3, 19, 29, 37, ...	A062619
54	2, 479, ...	A062620
55	2, 5, 7, 701, ...	A062621
56	3, 17, 293, ...	A062622
57	2, 19, 769, 773, ...	A062623
59	3, 7, ...	A062625
60	4663, 8839, 14779, ...	A062626
62	17, 23, 421, ...	A062628
63	3, 59, ...	A062629
64	2, 3, 11, 31, 349, 379, ...	A062630
65	5, 31, ...	A062631
67	3, 5, 43, ...	A062633
69	2, 17, ...	A062635
70	2, 11, ...	A062636
80	7, 277, ...	A062646
81		A062647
82	2, 3, 13, 787, 797, 857, ...	A062648
83
84	2, 41, 67, ...	A062650
85	179, 479, ...	A062651
86	5, 11, 103, 227, ...	A062652
87
88	5, 7, 19, 241, 607, ...	A062654
89		A062655
99		A062665

See also

• Base-independent classifications of prime numbers