A235365 Smallest odd prime factor of 3^n + 1, for n > 1.

5, 7, 41, 61, 5, 547, 17, 7, 5, 67, 41, 398581, 5, 7, 21523361, 103, 5, 2851, 41, 7, 5, 23535794707, 17, 61, 5, 7, 41, 523, 5, 6883, 926510094425921, 7, 5, 61, 41, 18427, 5, 7, 17, 33703, 5, 82064241848634269407, 41, 7, 5, 16921, 76801, 547, 5, 7, 41, 78719947, 5, 61, 17, 7, 5, 3187, 41

Offset: 2

Author

Jonathan Sondow, Jan 19 2014

Keywords

• nonn

Comments

Levi Ben Gerson (1288-1344) proved that 3^n + 1 = 2^m has no solution in integers if n > 1, by showing that 3^n + l has an odd prime factor. His proof uses remainders after division of powers of 3 by 8 and powers of 2 by 8; see the Lenstra and Peterson links. For an elegant short proof, see the Franklin link.

Examples

			3^2 + 1 = 10 = 2*5, so a(2) = 5.
		

References

• L. E. Dickson, History of the Theory of Numbers, Vol. II, Chelsea, NY 1992; see p. 731.

Links

• Table of n, a(n) for n = 2..768
• Philip Franklin, Problem 2927, Amer. Math. Monthly, 30 (1923), p. 81.
• Aaron Herschfeld, The equation 2^x - 3^y = d, Bull. Amer. Math. Soc., 42 (1936), 231-234.
• Hendrik Lenstra Harmonic Numbers, MSRI, 1998.
• J. J. O'Connor and E. F. Robertson, Levi ben Gerson, The MacTutor History of Mathematics archive, 2009.
• Ivars Peterson, Medieval Harmony, Math Trek, MAA, 2012.
• Wikipedia, Gersonides

Crossrefs

See A235366 for 3^n - 1.

Cf. also A003586 (products 2^m * 3^n), A006899, A061987, A108906.

Programs

Magma

[PrimeDivisors(3^n +1)[2]: n in [2..60] ] ; // Vincenzo Librandi, Mar 16 2019

Mathematica

Table[FactorInteger[3^n + 1][[2, 1]], {n, 2, 50}]

Formula

a(2+4n) = 5 as 3^(2+4n) + 1 = (3^2)*(3^4)^n + 1 = 9*81^n + 1 = 9*(80+1)^n + 1 == 9 + 1 == 0 (mod 5).

a(3+6n) = 7 as 3^(3+6n) + 1 = (3^3)*(3^6)^n + 1 = 27*729^n + 1 = 27*(728+1)^n + 1 == 27 + 1 == 0 (mod 7), but 27 * 729^n + 1 == 2*(-1)^n + 1 !== 0 (mod 5).

Extensions

Terms to a(132) in b-file from Vincenzo Librandi, Mar 16 2019

a(133)-a(658) in b-file from Amiram Eldar, Feb 05 2020

a(659)-a(768) in b-file from Max Alekseyev, Apr 27 2022