A064078 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.

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 2047, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 8388607, 241, 1082401, 2731, 262657, 3277, 536870911, 331, 2147483647, 65537, 599479, 43691, 8727391, 4033, 137438953471, 174763, 9588151, 61681

Offset: 1

Author

Jens Voß, Sep 04 2001

Keywords

• nonn

Comments

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.

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

a(n) = 2^n - 1 if and only if either n = 1 or n is prime. - Vladimir Shevelev, Sep 30 2008

a(n) == 1 (mod n), 2^(a(n)-1) == 1 (mod a(n)), A002326((a(n)-1)/2) = n. - Thomas Ordowski, Oct 25 2017

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

Named after the Austrian mathematician Karl Zsigmondy (1867-1925). - Amiram Eldar, Jun 20 2021

Examples

			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.
a(5) = 31 because 2^5 - 1 = 31 is prime.
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.
		

Links

• T. D. Noe, Table of n, a(n) for n=1..1000
• Wikipedia, Zsigmondy's theorem.
• Karl Zsigmondy, Zur Theorie der Potenzreste, Monatshefte für Mathematik, Vol. 3 (1892), pp. 265-284.

Crossrefs

Cf. A000225, A064079, A064080, A064081, A064082, A064083.

Cf. A019320, A063982.

Programs

Mathematica

Table[Cyclotomic[n, 2]/GCD[n, Cyclotomic[n, 2]], {n, 40}] (* Alonso del Arte, Mar 14 2013 *)

PARI

a(n) = my(m = polcyclo(n, 2)); m/gcd(m,n); \\ Michel Marcus, Mar 07 2015

Formula

Denominator of Sum_{d|n} d*moebius(n/d)/(2^d-1). - Vladeta Jovovic, Apr 02 2004

a(n) = A019320(n)/gcd(n, A019320(n)). - T. D. Noe, Apr 13 2010

a(n) = A019320(n)/(A019320(n) mod n) for n > 1. - Thomas Ordowski, Oct 24 2017

Extensions

More terms from Vladeta Jovovic, Apr 02 2004

Definition corrected by Jerry Metzger, Nov 04 2009