login
A302140
Numbers n with the property that for every m coprime to n, there are solutions to x^(psi(n)/ord(m,n)) == m (mod n), where psi(n) = A002322(n) and ord(m,n) is multiplicative order of m modulo n.
1
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 31, 33, 34, 36, 37, 38, 41, 42, 43, 44, 46, 47, 49, 50, 53, 54, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 69, 71, 72, 73, 74, 76, 77, 79, 81, 82, 83, 84, 86, 88, 89, 92, 93, 94, 97, 98, 99, 101, 103, 106, 107, 108
OFFSET
1,2
COMMENTS
Contains A033948 as a subsequence.
n cannot be divisible by 16. If n is divisible by 4 (but not by 16), all odd prime factors of n must be == 3 (mod 4). If an odd number n is in this sequence, so is 2n.
Decompose the multiplicative group of integers modulo n as a product of cyclic groups C_{k_1} x C_{k_2} x ... x C_{k_m}, where k_i divides k_j for i < j, then n is a term if and only if gcd(k_i,k_j/k_i) = 1 for i < j. - Jianing Song, Apr 29 2018
Terms < N become more and more sparse as N increases. The number of terms below 100, 1000, 10000 and 100000 are 73, 539, 4238 and 35559, respectively. - Jianing Song, Sep 05 2018
LINKS
Jianing Song, Table of n, a(n) for n = 1..7998 (all terms below 20000)
EXAMPLE
A002322(21) = 6, and 21 is in this sequence because for every m coprime to 21, x^(6/ord(m,21)) == m (mod 21) has solutions (e.g., ord(4,21) = ord(16,21) = 3 and we have 2^2 == 4 (mod 21), 4^2 == 16 (mod 21); ord(8,21) = ord(13,21) = ord(20,21) = 2 and we have 2^3 == 8 (mod 21), 19^3 == 13 (mod 21), 20^3 == 20 (mod 21)). Also, the multiplicative group of integers modulo 21 is isomorphic to C_2 x C_6, and since gcd(2,6/2) = 1, 21 is a term.
A002322(15) = 4, and 15 is not in this sequence because ord(11,15) = 2, but x^2 == 11 (mod 15) has no solution. Also, the multiplicative group of integers modulo 15 is isomorphic to C_2 x C_4, and since gcd(2,4/2) = 2, 15 is not a term.
PROG
(PARI) isA302140(n)=(prod(i=1, #znstar(n)[2]-1, gcd(znstar(n)[2][i+1], znstar(n)[2][i]/znstar(n)[2][i+1]))==1) \\ Jianing Song, Sep 05 2018
CROSSREFS
Sequence in context: A344022 A166535 A247764 * A039698 A347620 A078107
KEYWORD
nonn
AUTHOR
Jianing Song, Apr 02 2018
EXTENSIONS
a(30)-a(78) from Jianing Song, Apr 29 2018
STATUS
approved