|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
