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	A389264	A057186	none	A379986	none	none
21		A057187	A377856	none	A395460
22		A057188	none	A386383	none
23		A057189	A378115	1153, ...
24		A057190	none	none	none
25		A057191	A380253	A388142		none
26		A071380	none	A390912	none
27		none	A379988	none
28		A071381	none	A387390	none
29		A291906	A378953	A387392
30		A071382	none	none	none	none
31		A126856	A379429	A387473
32		none	none	A387474	none
33		A185230	A385244	none
34		A366680	none	A385851	none
35		A185240	A379987	A386914		none
36		A229145	none	none	none
37		A309409	257, ...	A388039
38		A229524	none	A388040	none
39		A230036	A379428	none
40		A229663	none	A389283	none	none
41		A309410	19, 61, ...	A389287
42		A231604	none	none	none
43		A231865	A381092	A389433
44		A309411	none	1847, ...	none
45		A309412	A380131	none		none
46		A235683	none	3, ...	none
47		A236167	A380132	A390751
48		A236530	none	none	none
49		A237052	A382866	5, 23, 109, ...
50		A309413	none	43, 109, 179, 239, ...	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	A375620	none	none
21	A062587	A127996	A375236	none	A386794	A392803
22	A062588	A127997	none	A381338	none	A396628
23	A062589	A204940	A375161	A382391	A390757	A391663
24	A214658	A127998	none	none	none	A392052
25	A214655	none	A377839	A384972	only n=2	none
26	A062592	A127999	none	A381093	none	A391924
27	A062593	only n=3	A377031	none	A391596	5, 53, ...
28	A062594	A128000	none	A384736	none	A392145
29	A062595	A181979	A376470	A384767	A386281	A394375
30	A062596	A098438	none	none	none	none
31	A062597	A128002	A377779	A385064	A386282	A395375
32	A062598	none	none	A384925	none	A395474
33	A062599	A209120	A377800	none	A389767	A394344
34	A062600	A185073	none	A385928	none	A395374
35	A062601	A348170	A377699	A385992	A389768	none
36	A215535	only n=2	none	none	none	A392800
37	A062603	A128003	A377814	A385518	2, 7, ...	A395417
38	A062604	A128004	none	A385684	none	A395534
39	A062605	A181987	2, 229, 631, ...	none	A391702	A389309
40	A062606	A128005	none	A385680	none	none
41	A062607	A239637	A377718	A389223	3, 5, 449, ...	A396460
42	A062608	A345402	none	none	none	2, 3, ...
43	A062609	A240765	A377180	A389222	A390770	3, 37, 67, ...
44	A215632	A294722	none	A387395	none	547, ...
45	A062611	A242797	A376329	none	A391053	none
46	A062612	A243279	none	A389266	none	3, ...
47	A062613	A267375	A380355	5, 373, ...	A392056	A395993
48	58543, ...	A245237	none	none	none	A396042
49	A062615	none	A381200	3, 19, 139, ...	only n=2	A396230
50	A062616	A245442	none	A389935	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	A215536			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	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{array}{rl}F& =(0^n+0^n)/(0+0)\\ & =0/0\end{array}$

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

$\begin{array}{rl}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{array}$

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

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

4) If n=1 then F=1

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

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

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

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{array}{rl}F& =(a^n+0^n)/(a+0)\\ & =a^n/a\\ & =a^{n-1}\end{array}$

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{array}{rl}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{array}$

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{array}{rl}F& =(a^n+b^n)/(a+b)\\ & =(a^{kj}+b^{kj})/(a+b)\\ & =(a^j+b^j)*f_k/(a+b)\end{array}$

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{array}{rl}F& =(a^n+b^n)/(a+b)\\ & =((cd{)}^n+(ce{)}^n)/(a+b)\\ & =c^n*(d^n+e^n)/(a+b)\end{array}$

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{array}{rl}M& =(a^n-b^n)/(a-b)\\ & =(2^n-1^n)/(2-1)\\ & =2^n-1\end{array}$

2) If b=a then M is undefined.

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

3) a and b are commutative.

$\begin{array}{rl}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{array}$

4) If n=0 then M is zero.

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

5) If n=1 then M=1

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

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

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

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{array}{rl}M& =(a^n-b^n)/(a-b)\\ & =(a-b)*f_n/(a-b)\\ & =f_n\end{array}$

$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{array}{rl}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{array}$

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{array}{rl}M& =(a^n-b^n)/(a-b)\\ & =(a^2-b^2)/(a-b)\\ & =(a-b)*(a+b)/(a-b)\\ & =(a+b)\end{array}$

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{array}{rl}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{array}$

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{array}{rl}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{array}$

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{array}{rl}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{array}$

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

This leaves n=2, and using I1:

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

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