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

%I #45 Sep 08 2022 08:46:06

%S 5,7,41,61,5,547,17,7,5,67,41,398581,5,7,21523361,103,5,2851,41,7,5,

%T 23535794707,17,61,5,7,41,523,5,6883,926510094425921,7,5,61,41,18427,

%U 5,7,17,33703,5,82064241848634269407,41,7,5,16921,76801,547,5,7,41,78719947,5,61,17,7,5,3187,41

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

%C 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.

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

%H <a href="/A235365/b235365.txt">Table of n, a(n) for n = 2..768</a>

%H Philip Franklin, <a href="http://www.jstor.org/stable/2298495">Problem 2927</a>, Amer. Math. Monthly, 30 (1923), p. 81.

%H Aaron Herschfeld, <a href="http://dx.doi.org/10.1090/S0002-9904-1936-06275-0">The equation 2^x - 3^y = d</a>, Bull. Amer. Math. Soc., 42 (1936), 231-234.

%H Hendrik Lenstra <a href="http://www.msri.org/publications/ln/msri/1998/mandm/lenstra/1/index.html">Harmonic Numbers</a>, MSRI, 1998.

%H J. J. O'Connor and E. F. Robertson, <a href="http://www-history.mcs.st-and.ac.uk/Biographies/Levi.html">Levi ben Gerson</a>, The MacTutor History of Mathematics archive, 2009.

%H Ivars Peterson, <a href="http://archive.is/iRXz">Medieval Harmony</a>, Math Trek, MAA, 2012.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Gersonides">Gersonides</a>

%F 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).

%F 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).

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

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

%o (Magma) [PrimeDivisors(3^n +1)[2]: n in [2..60] ] ; // _Vincenzo Librandi_, Mar 16 2019

%Y See A235366 for 3^n - 1.

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

%K nonn

%O 2,1

%A _Jonathan Sondow_, Jan 19 2014

%E Terms to a(132) in b-file from _Vincenzo Librandi_, Mar 16 2019

%E a(133)-a(658) in b-file from _Amiram Eldar_, Feb 05 2020

%E a(659)-a(768) in b-file from _Max Alekseyev_, Apr 27 2022