A351177 Number of distinct residues of k^(n^2) (mod n^2+1), k=0..n^2.

2, 2, 10, 2, 26, 2, 42, 8, 82, 2, 122, 16, 170, 2, 226, 2, 290, 12, 362, 2, 170, 50, 530, 2, 626, 2, 90, 80, 842, 70, 962, 36, 130, 92, 1226, 2, 1370, 138, 1522, 2, 1626, 178, 1554, 152, 2026, 152, 2210, 232, 2402, 12, 2602, 272, 2810, 2, 306, 2, 1010, 338, 3482

Offset: 1

Author

Michel Lagneau, Mar 18 2022

Keywords

• nonn

Comments

a(A005574(n)) = 2.

a(n) = n for n = 2, 8, 128, ...

a(n) = n^2+1 (subsequence of A134406) for n = 1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 29, 31, ...

a(n) > 2 and a(n) <= n for n = 8, 18, 50, 60, 64, 72, 98, 112, 128, 132, 162, ... .

For n odd, gcd(a(n),n) = 1 except for n = 7, 27, 63, 75, 93, 105, 111, 125, 135, 153, 177, 207, 213, ...

For n even, gcd(a(n),n) = 2 for n in {A005574} union {22, 34, 38, 42, 46, 50, 58, 62, 78, 82, 86, 98, 102, 106, 114, 118, 122, 138, ...}

gcd(a(n),n) > 2 for n = 7, 8, 12, 18, 27, 28, 30, 32, 44, 48, 52, 60, 63, 64, 68, ...

Examples

			a(2) = 2 because k^(2^2) == 0, 1 (mod 5) implies 2 distinct residues.
The table of k^(n^2) (mod n^2+1) of residues starts in row n=1 with columns k>=2 as:
0,1;
0,1,1,1,1;
0,1,2,3,4,5,6,7,8,9;
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25;
Its row sums are 1, 4, 45, 16, 325, ...
		

Crossrefs

Cf. A005574, A134406, A195637.

Programs

Maple

a:= n-> nops ({seq (k&^(n^2) mod (n^2+1), k=0..n^2)}):
seq (a(n), n=1..100);

Mathematica

Table[Length[Union[PowerMod[Range[0,n^2],n^2,n^2+1]]],{n,100}]

PARI

a(n) = #Set(vector(n^2+1, k, k--; Mod(k, n^2+1)^n^2)); \\ Michel Marcus, Mar 18 2022