Primes of the form (a^n+b^n)/(a+b) and (a^n-b^n)/(a-b)

Primes of the form $(a^{n}+b^{n})/(a+b)\,$ and $(a^{n}-b^{n})/(a-b)\,$

There are many sequences in the OEIS dealing with primes of these forms. They are summarized below.

Consideration here is limited to integers a, b, n >= 0.

$F=(a^{n}+b^{n})/(a+b)\,$

Note that F is a Fermat number when a=2, b=-1 and n is a power of 2.

$M=(a^{n}-b^{n})/(a-b)\,$

Note that M is a Mersenne number when a=2 and b=1.

Thus, these forms may be considered generalized Mersenne and Fermat numbers.

Studies have been reported when b=1 for both the F and M forms. See Links below.

The sections labeled "Sequences Related to F" and "Sequences Related to M" contain tables indicating the OEIS sequence that list the values of n where F or M is prime (or a probable prime) for the specified values of a and b. These tables also include those entries that have few or no values of n and thus do not have an OEIS sequence.

The sections "Properties of F" and "Properties of M" lists some properties that can be shown using elementary algebra. The most interesting are those that show M and F can be prime only if n is prime. There is at least one exception: F can be prime when a,b are not coprime and n is a power of two. Also, there are several conjectures that provide an opportunity for those that want to provide proofs.

Sequences Related to F

Table 1. Values of n where $F=(a^{n}+b^{n})/(a+b),$ is prime

a	b=a-1	b=1	b=2	b=3	b=4	b=5
1	none	none	A000978	A007658	only n=3	A057171
2	A000978	A000978	none	A057469	none	A082387
3	A057469	A007658	A057469	none	A128066	A122853
4	A128066	only n=3	none	A128066	none	A128335
5	A128335	A057171	A082387	A122853	A128335	only n=2
6	A128336	A057172	none	none	none	A128336
7	A187805	A057173	A125955	A128067	A218373	A128337
8	A181141	none	none	A128068	none	A128338
9	A187819	A057175	A125956	none	A211409	A128339
10	A217095	A001562	none	A128069	none	none
11	A185239	A057177	A125957	A128070	A224501	A128340
12	A213216	A057178	none	none	none	A128341
13	A225097	A057179	A222265	A128071	A213176	A128342
14	A224984	A057180	none	A128072	none	A128343
15	A221637	A057181	A225191	none	A227049	none
16	A227170	A057182	none	A128073	none	A225397
17	A228573	A057183	A224507	A228225	A228558	A227046
18	A227171	A057184	none	none	none	A228130
19	A225818	A057185	A228922	A128075	A231329	A229612
20		A057186	none		none
21		A057187		none
22		A057188	none		none
23		A057189
24		A057190	none	none	none
25		A057191				none
26		A071380	none		none
27		none		none
28		A071381	none		none
29		n=7, ?
30		A071382	none	none	none	none
31		A126856
32		none	none		none
33		A185230		none
34		n=3, ?	none		none
35		A185240				none
36		A229145	none	none	none
37		5,7,2707, ...
38		A229524	none		none
39		A230036		none
40		A229663	none		none	none
41		17,691, ...
42		A231604	none	none	none
43		A231865
44		7,41233, ...	none		none
45		103,157,37159, ...		none		none
46		A235683	none		none
47		A236167
48		A236530	none	none	none
49		A237052
50		1153,26903,56597, ...	none		none	none

Sequences Related to M

Table 2. Values of n where $M=(a^{n}-b^{n})/(a-b),$ is prime

a	b=a-1	b=1	b=2	b=3	b=4	b=5
1	none	none	A000043	A028491	only n=2	A004061
2	A000043	A000043	none	A057468	none	A082182
3	A057468	A028491	A057468	none	A059801	A121877
4	A059801	only n=2	none	A059801	none	A059802
5	A059802	A004061	A082182	A121877	A059802	none
6	A062572	A004062	none	none	none	A062572
7	A062573	A004063	A215487	A128024	A213073	A128344
8	A062574	only n=3	none	A128025	none	A128345
9	A059803	none	A173718	none	only n=2	A128346
10	A062576	A004023	none	A128026	none	none
11	A062577	A005808	A210506	A128027	A216181	A128347
12	A062578	A004064	none	none	none	A128348
13	A062579	A016054	A217320	A128028	A224691	A128349
14	A062580	A006032	none	A128029	none	A128350
15	A062581	A006033	A225955	none	A241921	none
16	A062582	only n=2	none	A128030	none	A128351
17	A062583	A006034	A225807	A128031	A230139	A128352
18	A188051	A133857	none	none	none	A128354
19	A062585	A006035	A229542	A128032	A228076	A128354
20	A062586	A127995	none	2,43, ...	none	none
21	A062587	A127996		none
22	A062588	A127997	none		none
23	A062589	A204940
24	A214658	A127998	none	none	none
25	A214655	none				none
26	A062592	A127999	none		none
27	A062593	only n=3		none
28	A062594	A128000	none		none
29	A062595	A181979
30	A062596	A098438	none	none	none	none
31	A062597	A128002
32	A062598	none	none		none
33	A062599	A209120		none
34	A062600	A185073	none		none
35	A062601	313,1297, ...				none
36	A215535	only n=2	none	none	none
37	A062603	A128003
38	A062604	A128004	none		none
39	A062605	A181987		none
40	A062606	A128005	none		none	none
41	A062607	A239637
42	A062608	2,1319, ...	none	none	none
43	A062609	A240765
44	A215632	5,31,167, ...	none		none
45	A062611	A242797		none		none
46	A062612	A243279	none		none
47	A062613	127,18013,39623, ...
48	58543, ...	A245237	none	none	none
49	A062615	none			only n=2
50	A062616	A245442	none		none	none
51	A062617			none
52	A062618		none		none
53	A062619	A173767
54	A062620		none	none	none
55	A062621					none
56	A062622		none		none
57	A062623			none
58	5,25633, ...		none		none
59	A062625
60	A062626		none	none	none	none
61	54517, ...
62	A062628		none		none
63	A062629			none
64	A062630	none	none		none
65	A062631					none
66	A062632		none	none	none
67	A062633
68	3,251, ...		none		none
69	A062635			none
70	A062636		none		none	none
71	A062637
72	A062638		none	none	none
73	A062639
74	A062640		none		none
75	A062641			none		none
76	A062642		none		none
77	A062643
78	A062644		none	none	none
79	A062645
80	A062646		none		none	none
81	A062647	none		none	none
82	A062648		none		none
83	331, ...
84	A062650		none	none	none
85	A062651					none
86	A062652		none		none
87	2,3,47, ...			none
88	A062654		none		none
89	A062655
90	A062656		none	none	none	none
91	A062657
92	A062658		none		none
93	A062659			none
94	A062660		none		none
95	A062661					none
96	A062662		none	none	none
97	A062663
98	n=7, ?		none		none
99	A062665			none
100	A062666	only n=2	none	only n=2	none	none

Properties of F

Some trivial properties of F:

1) If a=b=0 then F is undefined.

${\begin{aligned}F&=(0^{n}+0^{n})/(0+0)\\&=0/0\end{aligned}}\,$

2) F is a Fermat number ($2^{2^{j}}+1$) when a=2, b=-1 and n is a power of 2.

${\begin{aligned}F&=(a^{n}-b^{n})/(a-b)\\&=(2^{2^{j}}-1^{2^{j}})/(2-1)\\&=(2^{2^{j}}+1)/1\\&=2^{2^{j}}+1\end{aligned}}\,$

3) If n=0 then F is prime (F=2) only if a+b=1

${\begin{aligned}F&=(a^{0}+b^{0})/(a+b)\\&=2/(a+b)\end{aligned}}\,$

4) If n=1 then F=1

${\begin{aligned}F&=(a^{1}+b^{1})/(a+b)\\&=(a+b)/(a+b)\\&=1\end{aligned}}\,$

5) If b=a then F is prime only if n=2 and a is prime.

${\begin{aligned}F&=(a^{n}+a^{n})/(a+a)\\&=2a^{n}/2a\\&=a^{n-1}\end{aligned}}\,$

If n=0, F=1/a and cannot be prime.

If n=1, F=1 and thus not prime.

If n=2, F=a and is prime only if a is prime.

If n>2, F has more than one factor of a and thus is not prime.

6) If a=0 or b=0 (but not both) then F is prime only if n=2 and a is prime.

${\begin{aligned}F&=(a^{n}+0^{n})/(a+0)\\&=a^{n}/a\\&=a^{n-1}\end{aligned}}\,$

Some nontrivial properties of F:

The cases where a,b=0, a=b and n<2 have been explored above.

And since a and b are commutative, there is no loss in generality in assuming that a>b>0 and n>1 in the properties below.

The following identities are referenced below.

(I1) If n>1 is odd:

$(a^{n}+b^{n})=(a+b)*f_{n}\,$, where $f_{n}=a^{n-1}-a^{n-2}b+a^{n-3}b^{2}-...+b^{n-1}\,$

Note that if n>1 then $f_{n}>=(a+b)$ and $f_{n}>1$.

(I2) If n>1 has an odd factor, then n=k*j with k odd and j a power of 2:

$(a^{n}+b^{n})=(a^{kj}+b^{kj})=(a^{j}+b^{j})*f_{k}\,$, where $f_{k}=a^{(k-1)j}-a^{(k-2)j}b^{j}+a^{(k-3)j}b^{2j}-...+b^{(k-1)j}\,$

Note that if n>1 then $f_{n}>=(a+b)$ and $f_{n}>1$.

7) If a>b>0 and n is odd and composite, F is not prime.

Since n is composite it can be written as n=k*m. Since n is odd, k and m must both be odd, otherwise n would be even. And since the smallest composite odd integer is 9, m>=3 and k>=3. Using the identity (I1) twice:

${\begin{aligned}F&=(a^{n}+b^{n})/(a+b)\\&=(a^{km}+b^{km})/(a+b)\\&=(a^{m}+b^{m})*f_{k}/(a+b)\\&=(a+b)*f_{m}*f_{k}/(a+b)\\&=f_{m}*f_{k}\end{aligned}}\,$

F has two integer factors greater than 1 and thus cannot be prime.

8) If a>b>0 and n is even but has an odd factor, F is not prime.

Since n is composite it can be written as n=k*j, where j is a power of 2 and k is odd. And since the smallest composite even integer with an odd factor is 6, k>=3 and j>=2. Using the identity (I2):

${\begin{aligned}F&=(a^{n}+b^{n})/(a+b)\\&=(a^{kj}+b^{kj})/(a+b)\\&=(a^{j}+b^{j})*f_{k}/(a+b)\end{aligned}}\,$

case 1) $(a+b)$ does not divide $(a^{j}+b^{j})$ when $j$ is a power of 2, so $(a^{j}+b^{j})>1$ is one factor of F.

If $(a+b)$ divides $f_{k}$, then $f_{k}/(a+b)>1$ is another factor of F. Thus F is not prime.

case 2)If $(a+b)$ does not divide $f_{k}$, then F is not an integer and thus not prime.

Either way F is not prime.

9) If a>b>0, a,b coprime and n is a power of 2, F is not prime.

When $n>1$ is a power of 2 and a,b coprime, $(a+b)$ does not divide $(a^{n}+b^{n})$, therefore F is not an integer.

Example: If a=2, b=3, n=2 then F = (2^2+3^2)/(2+3) = (4+9)/5 = 13/5

10) If F is prime, a>b>0 and a,b coprime, n must be an odd prime.

From 7) n cannot be odd and composite.

From 8) n cannot be even and composite.

From 9) n cannot be a power of 2.

Therefore n must be odd and prime.

11) If a>b>0 and a,b not coprime, F may be prime.

Let c=gcd(a,b), d=a/c, e=b/c then

${\begin{aligned}F&=(a^{n}+b^{n})/(a+b)\\&=((cd)^{n}+(ce)^{n})/(a+b)\\&=c^{n}*(d^{n}+e^{n})/(a+b)\end{aligned}}\,$

F is an integer if (a+b) divides $c^{n}$.

F is also an integer if $h=gcd((a^{n}+b^{n})/c^{n},a+b)!=1$. If so then $(a+b)=h*c^{n}$.

For F to be prime, (a+b) must cancel all but one of the factors in the numerator with the remaining factor being prime. There are three possibilities:

1) $(a+b)=c^{n}$ and $(d^{n}+e^{n})$ is prime.

2) $(a+b)=c^{n-1}*(d^{n}+e^{n})$ and $c$ is prime.

3) $(a+b)=h*c^{n}$ and $(d^{n}+e^{n})/h$ is prime, where $h=gcd((a^{n}+b^{n})/c^{n},a+b)!=1$.

Note also, that given 7) and 8) above, n must be a power of two.

Table 3. Examples of conditions when a,b not coprime where $F=(a^{n}+b^{n})/(a+b)$ is prime

a	b	n	c	a+b	d^n+e^n	h	F
6	2	2	2	8	10	2	5
6	3	2	3	9	5	1	5
15	3	2	3	18	26	2	13
18	14	4	2	32	8962	2	4481
88	40	2	8	128	146	2	73
270	242	8	2	512	156273767551462786	2	78136883775731393

12) Conjecture: If a,b are cubes, F is prime only when n=3.

13) Conjecture: If a=4 and b=1, F is prime only when n=3.

14) Conjecture: If a=29 and b=1, F is prime only when n=7.

15) Conjecture: If a=34 and b=1, F is prime only when n=3.

Properties of M

Some trivial properties of M:

1) M is a Mersenne number ($2^{n}-1$) when a=2 and b=1.

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(2^{n}-1^{n})/(2-1)\\&=2^{n}-1\end{aligned}}\,$

2) If b=a then M is undefined.

${\begin{aligned}M&=(a^{n}-a^{n})/(a-a)\\&=0/0\end{aligned}}\,$

3) a and b are commutative.

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(-1)(a^{n}-b^{n})/(-1)(a-b)\\&=(-a^{n}+b^{n})/(-a+b)\\&=(b^{n}-a^{n})/(b-a)\end{aligned}}\,$

4) If n=0 then M is zero.

${\begin{aligned}M&=(a^{0}-b^{0})/(a-b)\\&=(1-1)/(a-b)\\&=0/(a-b)\end{aligned}}\,$

5) If n=1 then M=1

${\begin{aligned}M&=(a^{1}-b^{1})/(a-b)\\&=(a-b)/(a-b)\\&=1\end{aligned}}\,$

6) If a=0 or b=0 (but not both) M is prime only if n=2 and a is prime.

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(a^{n}-0^{n})/(a-0)\\&=(a^{n})/(a)\\&=a^{n-1}\end{aligned}}\,$

If n=0, M=1/a and cannot be prime.

If n=1, M=1 and thus not prime.

If n=2, M=a and is prime only if a is prime.

If n>2, M has more than one factor of a and thus is not prime.

Some nontrivial properties of M:

The cases where a=0, b=0, a=b and n<2 have been explored above.

And since a and b are commutative from 3) above, there is no loss in generality in assuming that a>b>0 and n>1 in the properties below.

The following identities are referenced below.

(I1) $(a^{2}-b^{2})=(a-b)(a+b)\,$

(I2) If n>1:

$a^{n}-b^{n}=(a-b)*f_{n}\,$, where $f_{n}=a^{n-1}+a^{n-2}b+a^{n-3}b^{2}+...+b^{n-1}\,$

Note that if n>1 then $f_{n}>=(a+b)$, $f_{n}>(a-b)$ and $f_{n}>1$.

(I3) If n>1 is even:

$a^{n}-b^{n}=(a+b)*f_{n}\,$, where $f_{n}=a^{n-1}-a^{n-2}b+a^{n-3}b^{2}-...-b^{n-1}\,$

Note that if n>2 then $f_{n}>=(a+b)$, $f_{n}>(a-b)$ and $f_{n}>1$.

(I4) If n>1 is odd:

$(a^{n}+b^{n})=(a+b)*f_{n}\,$, where $f_{n}=a^{n-1}-a^{n-2}b+a^{n-3}b^{2}-...+b^{n-1}\,$

Note that if n>1 then $f_{n}>=(a+b)$, $f_{n}>(a-b)$ and $f_{n}>1$.

7) M is an integer. Using I2:

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(a-b)*f_{n}/(a-b)\\&=f_{n}\end{aligned}}\,$

$f_{n}$ is always an integer, thus M is always an integer.

8) If n>2 is composite, M is not prime.

Since n is composite, let n=k*m. Using I2 twice:

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(a^{km}-b^{km})/(a-b)\\&=(a^{m}-b^{m})*f_{k}/(a-b)\\&=(a-b)*f_{m}*f_{k}/(a-b)\\&=f_{m}*f_{k}\end{aligned}}\,$

Thus M consists of two integer factors greater than 1 and thus not prime.

9) If n=2, M is prime only if (a+b) is prime.

Using I1:

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(a^{2}-b^{2})/(a-b)\\&=(a-b)*(a+b)/(a-b)\\&=(a+b)\end{aligned}}\,$

10) If n>2 and has no odd factor, M is not prime.

If there is no odd factor, n must be a power of two and can be written $n=2^{j}$ where j>1. Using I1 repeatedly:

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(a^{2^{j}}-b^{2^{j}})/(a-b)\\&=(a^{2^{j-1}}-b^{2^{j-1}})*(a^{2^{j-1}}+b^{2^{j-1}})/(a-b)\end{aligned}}\,$

This can be repeated on the first term until (a-b) is reached, cancelling the denominator. There are j other factors greater than one and thus M is not prime.

11) M can be prime only if n is prime.

From 8) n cannot be composite and greater than 2.

From 10) n cannot be a power of 2 greater than 2.

From 9) n can be 2, but 2 is prime.

Thus n must be prime.

12) Conjecture: If a,b are not coprime, M is not prime.

13) If a,b are both squares, M can be prime only if n=2 and (a+b) is prime.

If n>2 is even then let n=2m, using I1 and I2:

${\begin{aligned}M&=(a^{2m}-b^{2m})/(a-b)\\&=(a^{m}-b^{m})*(a^{m}+b^{m})/(a-b)\\&=(a-b)*f_{n}*(a^{m}+b^{m})/(a-b)\\&=f_{n}*(a^{m}+b^{m})\end{aligned}}\,$

Thus M consists of two integer factors greater than 1 and thus not prime.

If n>2 is odd. Let $c={\sqrt {a}}$ and $d={\sqrt {b}}$. Since a and b are squares, c and d are integers. Using I1, I2, I4 and I1 again:

${\begin{aligned}M&=(a^{n}-b^{n})/(a-b)\\&=(c^{2n}-d^{2n})/(a-b)\\&=(c^{n}-d^{n})*(c^{n}+d^{n})/(a-b)\\&=(c-d)*f_{n1}*(c^{n}+d^{n})/(a-b)\\&=(c-d)*f_{n1}*(c+d)*f_{n2}/(a-b)\\&=(c-d)*(c+d)*f_{n1}*f_{n2}/(a-b)\\&=(c^{2}-d^{2})*f_{n1}*f_{n2}/(a-b)\\&=(a-b)*f_{n1}*f_{n2}/(a-b)\\&=f_{n1}*f_{n2}\end{aligned}}\,$

Thus M consists of two integer factors greater than 1 and thus not prime.

This leaves n=2, and using I1:

${\begin{aligned}M&=(a^{2}-b^{2})/(a-b)\\&=(a-b)*(a+b)/(a-b)\\&=(a+b)\end{aligned}}\,$

Thus if a,b are squares, M is prime only if n=2 an (a+b) is prime.

14) Conjecture: If a=j^2, b=k^2, j>k, M is prime only when n=2.

15) Conjecture: If a=j^3, b=k^3, j>k, M is prime only when n=3.

16) Conjecture: If a=j^p, b=k^p, j>k, where p is any prime, M is prime only when n=p.

17) Conjecture: If a=j^m, b=k^m, j>k, where m is not a power of a prime, M is not prime.

Links

• J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.

• H. Dubner, Generalized Repunit Primes, Mathematics of Computation, Volume 61, Number 204, October 1993, pages 927-930.

• H H. Dubner and T. Granlund, Primes of the Form (b^n+1)/(b+1), J. Integer Sequences, 3 (2000), #P00.2.7.

• H H. Lifchitz, Mersenne and Fermat primes field

• H Eric Weisstein's World of Mathematics, Repunit