|
| |
|
|
A329062
|
|
Numbers k that are not prime powers (i.e., not in A000961) such that A328925(k) > 1; numbers k such that if we write k = Product_{i=1..t} p_i^e_i , then t > 1, and lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j) < A002322(k), where ord(a,r) is the multiplicative order of a modulo r, and A002322 is the Carmichael lambda (usually written as psi).
|
|
2
|
|
|
|
14, 34, 39, 46, 55, 62, 65, 68, 82, 86, 94, 95, 98, 111, 112, 117, 123, 124, 133, 136, 142, 145, 146, 153, 155, 158, 164, 172, 175, 178, 183, 194, 201, 203, 205, 206, 209, 218, 219, 221, 224, 226, 248, 253, 254, 259, 272, 274, 275, 287, 291, 292, 295, 299, 301, 302, 305, 309
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Write psi = A002322, b = A118106. These are numbers k that are not prime powers such that b(k) < psi(k).
If k = Product_{i=1..t} p_i^e_i (t > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, then k is here, as b(k) | psi(k)/2.
If k = 2 * Product_{i=1..t} p_i^e_i, where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1, 7 (mod 8), then k is here. For example, k = 2p, where p == 1, 7 (mod 8).
If k = 2^e * Product_{i=1..t} p_i^e_i (e > 1), where {p_i} are distinct odd primes such that p_i is a quadratic residue modulo p_j for all i != j, and p_i == 1 (mod 8), then k is here. For example, k = 2^e*p, where p == 1 (mod 8).
If k = p_1^e_1 * p_2^e_2, where p_1 is not a primitive root modulo p_2^e_2, p_2 is not a primitive root modulo p_1^e_1, then k is not necessarily here: for k = 3^2 * 67 = 603, 3 is not a primitive root modulo 67, 67 is not a primitive root modulo 3^2, but b(603) = psi(603) = 66. Conversely, if p_1 is a primitive root modulo p_2^e_2, then k can still be here: for k = 3^2 * 17 = 153, 3 is a primitive root modulo 17, but b(153) = 16 while psi(153) = 48.
If k is an odd number, then 4k is here if and only if 8k is also here. Write k = Product_{i=1..t} p_i^e_i, then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),lcm_{i=1..t} ord(2,p_i^e_i),b(k)), b(8k) = lcm(lcm_{i=1..t} ord(p_i,8),lcm_{i=1..t} ord(2,p_i^e_i),b(k)). It is easy to see that lcm(ord(p_i,4),ord(2,p_i^e_i)) = lcm(ord(p_i,8),ord(2,p_i^e_i)), so b(4k) = b(8k). Note that psi(4k) = psi(8k).
If k is an odd number such that 4k is here, then 16k is also here (but the converse is not true). Write k = Product_{i=1..t} p_i^e_i, N = lcm(lcm_{i=1..t} ord(2,p_i^e_i),b(k)), then b(4k) = lcm(lcm_{i=1..t} ord(p_i,4),N), b(16k) = lcm(lcm_{i=1..t} ord(p_i,16),N) = b(4k) or b(4k)*2 or b(4k)*4. Note that psi(16k) = lcm(psi(4k),4). If we have b(4k) < psi(4k) and b(16k) = psi(16k), let M = psi(k), then:
Case (a): M == 2 (mod 4), then b(16k) = psi(16k) = 2*psi(4k) = 2M, and b(4k) = b(16k)/4 = M/2 which is an odd number, so ord(2,p_i^e_i) is odd for all i, so p_i == 1, 7 (mod 8), which gives ord(p_i,16) <= 2*ord(p_i,4). As a result, b(16k) <= 2*b(4k), a contradiction!
Case (b): M == 0 (mod 4), then b(16k) = psi(16k) = psi(4k) = M. If N is divisible by 4, then b(4k) = b(16k) = N, a contradiction. So 4 does not divide N, we have v(M,2) = v(lcm(lcm_{i=1..t} ord(p_i,16),N),2) <= 2, but 4 | M, so v(M,2) = 2, where v(,2) is the 2-adic valuation. As a result, there must exist p_i congruent to 5 mod 8 to make v(M,2) = 2, then 4 | ord(2,p_i^e_i), so 4 | N, a contradiction!
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
Let ord(a,r) be the multiplicative order of a modulo r.
For k = 175 = 5^2 * 7, b(175) = lcm(ord(7,5^2),ord(5,7)) = lcm(4,6) = 12, while psi(175) = lcm(20,6) = 60, so 175 is a term.
For k = 410 = 2 * 5 * 41, b(410) = lcm(ord(5,2),ord(41,2),ord(2,5),ord(41,5),ord(2,41),ord(5,41)) = 20, while psi(410) = lcm(1,4,40) = 40, so 410 is a term.
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
