The OEIS is supported by the many generous donors to the OEIS Foundation.
%I #64 Aug 09 2022 10:58:52
%S 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,
%T 8,9,19,37,781,13,1093,17,9,5,73,25,311,7,5461,41,73,10,11,91,65,2801,
%U 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
%N 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.
%C 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.
%C All prime factors of T(n,k) are congruent to 1 modulo k.
%C 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.
%C 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.
%H Jeppe Stig Nielsen, <a href="/A323748/b323748.txt">Table of n, a(n) for n = 2..11326 (so 150 antidiagonals)</a>
%H Jianing Song, <a href="/A323748/a323748.pdf">Notes for A323748</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Zsigmondy's theorem">Zsigmondy's theorem</a>
%F 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.
%F 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.
%F T(n,k) = Phi_k(n)/A342255(n,k) for n >= 2, k != 2.
%e In the following list, "*" identifies a prime power.
%e Table begins
%e n\k | 1 2 3 4 5 6 7 8
%e 2 | 1 , 3*, 7*, 5*, 31*, 1 , 127*, 17*
%e 3 | 2*, 1 , 13*, 5*, 121*, 7*, 1093*, 41*
%e 4 | 3*, 5*, 7*, 17*, 341 , 13*, 5461 , 257*
%e 5 | 4*, 3*, 31*, 13*, 781 , 7*, 19531*, 313*
%e 6 | 5*, 7*, 43*, 37*, 311*, 31*, 55987*, 1297*
%e 7 | 6 , 1 , 19*, 25*, 2801*, 43*, 137257 , 1201*
%e 8 | 7*, 9*, 73*, 65 , 4681 , 19*, 42799 , 4097
%e 9 | 8*, 5*, 91 , 41*, 7381 , 73*, 597871 , 3281
%e 10 | 9*, 11*, 37*, 101*, 11111 , 91 , 1111111 , 10001
%e 11 | 10 , 3*, 133 , 61*, 3221*, 37*, 1948717 , 7321*
%e 12 | 11*, 13*, 157*, 145 , 22621*, 133 , 3257437 , 20737
%e The first few columns:
%e T(n,1) = n - 1;
%e T(n,2) = A000265(n+1);
%e T(n,3) = (n^2 + n + 1)/3 if n == 1 (mod 3), n^2 + n + 1 otherwise;
%e T(n,4) = (n^2 + 1)/2 if n == 1 (mod 2), n^2 + 1 otherwise;
%e 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;
%e T(n,6) = (n^2 - n + 1)/3 if n == 2 (mod 3), n^2 - n + 1 otherwise;
%e T(n,7) = (n^6 + n^5 + ... + 1)/7 if n == 1 (mod 7), n^6 + n^5 + ... + 1 otherwise;
%e T(n,8) = (n^4 + 1)/2 if n == 1 (mod 2), n^4 + 1 otherwise;
%e T(n,9) = (n^6 + n^3 + 1)/3 if n == 1 (mod 3), n^6 + n^3 + 1 otherwise;
%e 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;
%e T(n,11) = (n^10 + n^9 + ... + 1)/11 if n == 1 (mod 11), n^10 + n^9 + ... + 1 otherwise;
%e 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).
%t 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 *)
%t 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 *)
%o (PARI) T(n,k) = if(k==2, (n+1)>>valuation(n+1, 2), my(m = polcyclo(k, n)); m/gcd(m, k))
%Y Cf. A000265, A253240, A342255.
%Y Rows 1..6 are A064078, A064079, A064080, A064081, A064082 and A064083.
%K nonn,tabl
%O 2,2
%A _Jianing Song_, Jan 25 2019
%E Zs notation in Name changed by _Jeppe Stig Nielsen_, Oct 16 2020