|
%I #57 Jun 20 2021 02:49:05
%S 1,3,7,5,31,1,127,17,73,11,2047,13,8191,43,151,257,131071,19,524287,
%T 41,337,683,8388607,241,1082401,2731,262657,3277,536870911,331,
%U 2147483647,65537,599479,43691,8727391,4033,137438953471,174763,9588151,61681
%N Zsigmondy numbers for a = 2, b = 1: Zs(n, 2, 1) is the greatest divisor of 2^n - 1 (A000225) that is coprime to 2^m - 1 for all positive integers m < n.
%C By Zsigmondy's theorem, the n-th Zsigmondy number for bases a and b is not 1 except in the three cases (1) a = 2, b = 1, n = 1, (2) a = 2, b = 1, n = 6, (3) n = 2 and a + b is a power of 2.
%C Composite terms are the maximal overpseudoprimes to base 2 (see A141232) for which the multiplicative order of 2 mod a(n) equals n. - _Vladimir Shevelev_, Aug 26 2008
%C a(n) = 2^n - 1 if and only if either n = 1 or n is prime. - _Vladimir Shevelev_, Sep 30 2008
%C a(n) == 1 (mod n), 2^(a(n)-1) == 1 (mod a(n)), A002326((a(n)-1)/2) = n. - _Thomas Ordowski_, Oct 25 2017
%C If n is odd, then the prime factors of a(n) are congruent to {1,7} mod 8, that is, they have 2 has a quadratic residue, and are congruent to 1 mod 2n. If n is divisible by 8, then the prime factors of a(n) are congruent to 1 mod 16. - _Jianing Song_, Apr 13 2019
%C Named after the Austrian mathematician Karl Zsigmondy (1867-1925). - _Amiram Eldar_, Jun 20 2021
%H T. D. Noe, <a href="/A064078/b064078.txt">Table of n, a(n) for n=1..1000</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Zsigmondy's theorem">Zsigmondy's theorem</a>.
%H Karl Zsigmondy, <a href="http://dx.doi.org/10.1007/BF01692444">Zur Theorie der Potenzreste</a>, Monatshefte für Mathematik, Vol. 3 (1892), pp. 265-284.
%F Denominator of Sum_{d|n} d*moebius(n/d)/(2^d-1). - _Vladeta Jovovic_, Apr 02 2004
%F a(n) = A019320(n)/gcd(n, A019320(n)). - _T. D. Noe_, Apr 13 2010
%F a(n) = A019320(n)/(A019320(n) mod n) for n > 1. - _Thomas Ordowski_, Oct 24 2017
%e a(4) = 5 because 2^4 - 1 = 15 and its divisors being 1, 3, 5, 15, only 1 and 5 are coprime to 2^2 - 1 = 3 and 2^3 - 1 = 7, and 5 is the greater of these.
%e a(5) = 31 because 2^5 - 1 = 31 is prime.
%e a(6) = 1 because 2^6 - 1 = 63 and its divisors being 1, 3, 7, 9, 21, 63, only 1 is coprime to all of 3, 7, 15, 31.
%t Table[Cyclotomic[n, 2]/GCD[n, Cyclotomic[n, 2]], {n, 40}] (* _Alonso del Arte_, Mar 14 2013 *)
%o (PARI) a(n) = my(m = polcyclo(n, 2)); m/gcd(m,n); \\ _Michel Marcus_, Mar 07 2015
%Y Cf. A000225, A064079, A064080, A064081, A064082, A064083.
%Y Cf. A019320, A063982.
%K nonn
%O 1,2
%A _Jens Voß_, Sep 04 2001
%E More terms from _Vladeta Jovovic_, Apr 02 2004
%E Definition corrected by _Jerry Metzger_, Nov 04 2009
|
