A307434 a(n) is the smallest k such that the p-rank of (Z/kZ)* is 2, where p = prime(n) and (Z/kZ)* is the multiplicative group of integers modulo n.

8, 63, 275, 1247, 1541, 4187, 14111, 43739, 6533, 13747, 116003, 33227, 61337, 74563, 186497, 79501, 586343, 269011, 432821, 485357, 128627, 451091, 83333, 191351, 377719, 491063, 638189, 551051, 2617309, 359341, 1164083, 206981, 902831, 929633, 2134277

Offset

1,1

Comments

The p-rank of a finite abelian group G is equal to log_p(#{x belongs to G : x^p = 1}) where p is a prime number. By definition, a(n) is the smallest k such that x^p == 1 (mod k) has exactly p^2 solutions, p = prime(n).

a(n) exists for all n: by Dirichlet's theorem on arithmetic progressions, there exists a primes q congruent to 1 modulo p, in which case C_p X C_p is a subgroup of (Z/(q*p^2)Z)*, p = prime(n).

a(n) is the smallest k such that C_p X C_p is a subgroup of (Z/kZ)*, p = prime(n).

Also, a(n) is the smallest k such that there exists some x, y such that ord(x,k) = ord(y,k) = prime(n) and the set of powers of x and the set of powers of y modulo k have trivial intersection {1}, where ord(x,k) is the multiplicative order of x modulo k.

Let p, q be odd primes, then (Z/(q^e)Z)* has p-rank 1 if q == 1 (mod p), or q = p and e >= 2; 0 otherwise. As a result, for n >= 2, a(n) is of the form (q_1)*(q_2) or (q_1)*p^2 where q_1 and q_2 are the smallest two primes congruent to 1 modulo prime(n).

It seems that for n >= 4, a(n) is not divisible by prime(n)^2, that is, there exists at least two primes that are smaller than prime(n)^2 and congruent to 1 modulo prime(n).

Links

Jianing Song, Table of n, a(n) for n = 1..10000

Jianing Song, Factorization of a(n) for n = 4..10000

Wikipedia, Multiplicative group of integers modulo n

Formula

a(1) = 8; a(n) = A307436(prime(n)) for n >= 2.

Example

(Z/8Z)* = C_2 X C_2, in which the solutions to x^2 == 1 (mod 8) are x == 1, 3, 5, 7 (mod 8) (4 solutions);
(Z/63Z)* = C_6 X C_6, in which the solutions to x^3 == 1 (mod 63) are x == 1, 4, 16, 22, 25, 37, 43, 46, 58 (mod 63) (9 solutions);
(Z/275Z)* = C_10 X C_20, in which the solutions to x^5 == 1 (mod 275) are x == 1, 16, 26, 31, 36, 56, 71, 81, 86, 91, 111, 126, 136, 141, 146, 166, 181, 191, 196, 201, 221, 236, 246, 251, 256 (mod 275) (25 solutions).

Prog

(PARI) a(n) = if(n==1, 8, my(p=prime(n), i=0, q=0); for(k=1, +oo, if(isprime(2*k*p+1), i++; if(i==1, q=2*k*p+1)); if(i==2, return(q*min(p^2, 2*k*p+1)))))

Crossrefs

Cf. A307436, A035095.

Sequence in context: A080270 A371402 A178392 * A282311 A085433 A171313

Adjacent sequences: A307431 A307432 A307433 * A307435 A307436 A307437

Keyword

nonn

Author

Jianing Song, Apr 08 2019

Status

approved