A381319 Order of linear recurrence with constant coefficients of solutions of k satisfying k^(n-1) == 1 (mod n^2) for a given n.

2, 3, 2, 5, 2, 7, 2, 3, 2, 11, 2, 13, 2, 5, 2, 17, 2, 19, 2, 5, 2, 23, 2, 5, 2, 3, 4, 29, 2, 31, 2, 5, 2, 5, 2, 37, 2, 5, 2, 41, 2, 43, 2, 9, 2, 47, 2, 7, 2, 5, 4, 53, 2, 5, 2, 5, 2, 59, 2, 61, 2, 5, 2, 17, 6, 67, 2, 5, 4, 71, 2, 73, 2, 5, 4, 5, 2, 79, 2, 3, 2, 83, 2, 17, 2, 5, 2, 89

Offset: 2

Author

Mike Sheppard, Feb 20 2025

Keywords

• nonn

Comments

For a given n, the solutions for k have the linear recurrence with constant coefficients k(m) = k(m-1) + k(m-(a(n)-1)) - k(m-a(n)), with order a(n). If a(n)=2 then the term k(m-1) appears twice and is k(m) = 2*k(m-1) - k(m-2).

Also, k(m) - k(m-(a(n)-1)) = n^2 = k(m-1) - k(m-a(n)), so all have nonhomogeneous linear recurrence of k(m) = k(m-(a(n)-1)) + n^2. Equivalently, k(m) = k(m-A063994(n)) + n^2, with order A063994(n). Thus, k(m) ~ (n^2 / A063994(n)) * m = (n^2 / (a(n)-1)) * m.

Examples

			For n=5 the congruence equation k^4 ==1 mod (5^2) has solutions of k (A056021) which satisfy k(m) = k(m-1) + k(m-4) - k(m-5), the order being 5, a(5)=5.
For n=9, k^8==1 mod (9^2) has solutions of k with recurrence k(m) = k(m-1) + k(m-2) - k(m-3), order 3, a(9)=3.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 2..10000

Crossrefs

Cf. A063994, A056020 (n=3), A056021 (n=5), A056022 (n=7), A056024 (n=11), A056025 (n=13), A056028 (n=19), A056031 (n=23), A056034 (n=29), A056035 (n=31).

Programs

Mathematica

A381319[n_] := Times @@ GCD[FactorInteger[n][[All, 1]] - 1, n - 1] + 1;
Array[A381319, 100, 2] (* Paolo Xausa, Mar 05 2025 *)

Formula

a(n) = 1 + A063994(n).

a(p) = p if p is prime.