A323748 Square array read by ascending antidiagonals: the n-th row lists the Zsigmondy numbers for a = n, b = 1, that is, T(n,k) = Zs(k, n, 1) is the greatest divisor of n^k - 1 that is coprime to n^m - 1 for all positive integers m < k, with n >= 2, k >= 1.

1, 2, 3, 3, 1, 7, 4, 5, 13, 5, 5, 3, 7, 5, 31, 6, 7, 31, 17, 121, 1, 7, 1, 43, 13, 341, 7, 127, 8, 9, 19, 37, 781, 13, 1093, 17, 9, 5, 73, 25, 311, 7, 5461, 41, 73, 10, 11, 91, 65, 2801, 31, 19531, 257, 757, 11, 11, 3, 37, 41, 4681, 43, 55987, 313, 1387, 61, 2047, 12, 13, 133, 101, 7381, 19, 137257, 1297, 15751, 41, 88573, 13

Offset: 2

Author

Jianing Song, Jan 25 2019

Keywords

• nonn
• tabl

Comments

By Zsigmondy's theorem, T(n,k) = 1 if and only if n = 2 and k = 1 or 6, or n + 1 is a power of 2 and k = 2.

All prime factors of T(n,k) are congruent to 1 modulo k.

If T(n,k) = p^e where p is prime, then p is a unique-period prime in base n. By the property above, k must be a divisor of p - 1.

There are many squares of primes in the third, fourth or sixth column (e.g., T(7,4) = 25 = 5^2, T(22,3) = T(23,6) = 169 = 13^2, T(41,4) = 841 = 29^2, etc.). Conjecturally all other prime powers with exponent >= 2 in the table excluding the first two columns are T(3,5) = 121 = 11^2, T(18,3) = T(19,6) = 343 = 7^3 and T(239,4) = 28561 = 13^4.

Examples

			In the following list, "*" identifies a prime power.
Table begins
   n\k |  1    2     3     4       5     6         7       8
   2   |  1 ,  3*,   7*,   5*,    31*,   1 ,     127*,    17*
   3   |  2*,  1 ,  13*,   5*,   121*,   7*,    1093*,    41*
   4   |  3*,  5*,   7*,  17*,   341 ,  13*,    5461 ,   257*
   5   |  4*,  3*,  31*,  13*,   781 ,   7*,   19531*,   313*
   6   |  5*,  7*,  43*,  37*,   311*,  31*,   55987*,  1297*
   7   |  6 ,  1 ,  19*,  25*,  2801*,  43*,  137257 ,  1201*
   8   |  7*,  9*,  73*,  65 ,  4681 ,  19*,   42799 ,  4097
   9   |  8*,  5*,  91 ,  41*,  7381 ,  73*,  597871 ,  3281
  10   |  9*, 11*,  37*, 101*, 11111 ,  91 , 1111111 , 10001
  11   | 10 ,  3*, 133 ,  61*,  3221*,  37*, 1948717 ,  7321*
  12   | 11*, 13*, 157*, 145 , 22621*, 133 , 3257437 , 20737
The first few columns:
  T(n,1) = n - 1;
  T(n,2) = A000265(n+1);
  T(n,3) = (n^2 + n + 1)/3 if n == 1 (mod 3), n^2 + n + 1 otherwise;
  T(n,4) = (n^2 + 1)/2 if n == 1 (mod 2), n^2 + 1 otherwise;
  T(n,5) = (n^4 + n^3 + n^2 + n + 1)/5 if n == 1 (mod 5), n^4 + n^3 + n^2 + n + 1 otherwise;
  T(n,6) = (n^2 - n + 1)/3 if n == 2 (mod 3), n^2 - n + 1 otherwise;
  T(n,7) = (n^6 + n^5 + ... + 1)/7 if n == 1 (mod 7), n^6 + n^5 + ... + 1 otherwise;
  T(n,8) = (n^4 + 1)/2 if n == 1 (mod 2), n^4 + 1 otherwise;
  T(n,9) = (n^6 + n^3 + 1)/3 if n == 1 (mod 3), n^6 + n^3 + 1 otherwise;
  T(n,10) = (n^4 - n^3 + n^2 - n + 1)/5 if n == 4 (mod 5), n^4 - n^3 + n^2 - n + 1 otherwise;
  T(n,11) = (n^10 + n^9 + ... + 1)/11 if n == 1 (mod 11), n^10 + n^9 + ... + 1 otherwise;
  T(n,12) = n^4 - n^2 + 1 (12 is not of the form p^e*d for any prime p, exponent e >= 1 and d dividing p-1).
		

Links

• Jeppe Stig Nielsen, Table of n, a(n) for n = 2..11326 (so 150 antidiagonals)
• Jianing Song, Notes for A323748
• Wikipedia, Zsigmondy's theorem

Crossrefs

Cf. A000265, A253240, A342255.

Rows 1..6 are A064078, A064079, A064080, A064081, A064082 and A064083.

Programs

Mathematica

Table[Function[n, SelectFirst[Reverse@ Divisors[n^k - 1], Function[m, AllTrue[n^Range[k - 1] - 1, GCD[#, m] == 1 &]]]][j - k + 2], {j, 12}, {k, j}] // Flatten (* or *)
Table[Function[n, If[k == 2, #/2^IntegerExponent[#, 2] &[n + 1], #/GCD[#, k] &@ Cyclotomic[k, n]]][j - k + 1], {j, 2, 13}, {k, j - 1}] // Flatten (* Michael De Vlieger, Feb 02 2019 *)

PARI

T(n,k) = if(k==2, (n+1)>>valuation(n+1, 2), my(m = polcyclo(k, n)); m/gcd(m, k))

Formula

T(n,k) = A000265(n+1) if k = 2, otherwise T(n,k) = Phi_k(n)/gcd(Phi_k(n), k) = A253240(k,n)/gcd(A253240(k,n), k) where Phi_k is the k-th cyclotomic polynomial.

T(n,k) = A000265(n+1) if k = 2, Phi_k(n)/p if k = p^e*ord(n,p) != 2 for some prime p and exponent e >= 1, Phi_k(n) otherwise, where ord(n,p) is the multiplicative order of n modulo p.

T(n,k) = Phi_k(n)/A342255(n,k) for n >= 2, k != 2.

Extensions

Zs notation in Name changed by Jeppe Stig Nielsen, Oct 16 2020