Carmichael Numbers for GL(m)

Eugene Karolinsky and Dmytro Seliutin Department of Pure Mathematics Kharkiv National University Ukraine

                 ekarolinsky@univer.kharkov.ua
                    selyutind1996@gmail.com

Abstract We propose a generalization of Carmichael numbers, where the multiplicative group 𝔾_{m} = GL(1) is replaced by GL(m) for m ≥ 2. We prove basic properties of these families of numbers and give some examples.

1 Introduction

Recall that a composite number n ∈ ℕ is called Carmichael if a^{n−1} ≡ 1 (mod n) for every a ∈ (ℤ/nℤ)^{×}. In other words, Carmichael numbers are Fermat pseudoprimes to all values of a that are coprime to n. Alford, Granville, and Pomerance [1] proved that there are infinitely many Carmichael numbers.

Recently, various generalizations and analogues of Carmichael numbers were proposed, see, e.g., [3, 5, 7] and references therein. In this paper, we introduce another analogue of Carmichael numbers, where the multiplicative group 𝔾_{m} = GL(1) is replaced by GL(m) for m ≥ 2. Namely, we start with the exponent K_{m}(p) of the group GL(m, 𝔽_{p}), extrapolate it naturally to all naturals as K_{m}(n), and then define a composite number n ∈ ℕ to be m-Carmichael if A^{K_{m}(n)} = I for all A ∈ GL(m, ℤ/nℤ). Thus, the “classical” Carmichael numbers can be recovered as 1-Carmichael numbers.

We study basic properties of m-Carmichael numbers, including an analogue of Korselt’s criterion for a number to be Carmichael in terms of its prime divisors. This criterion appears to be practical for numbers of reasonable size. Using this, we compute all m-Carmichael numbers less than or equal to 10^{5} for 2 ≤ m ≤ 10. Also, we describe the structure of m-Carmichael numbers with given prime factors.

Some properties of m-Carmichael numbers for m ≥ 2 appear to be rather different from those of the “classical” Carmichael numbers. Namely, m-Carmichael numbers for m ≥ 2 can be non-squarefree or even. Moreover, all prime powers are m-Carmichael for m ≥ 2. Possible explanation of these phenomena is the fact that the groups GL(m) for m ≥ 2 contain (many copies of) the additive group 𝔾_{a}.

The paper is organized as follows. In Section 2, we define m-Carmichael numbers and discuss their basic properties. The main result of the paper is Theorem 8, an analogue of Korselt’s criterion for m-Carmichael numbers. In Section 3, we consider the distribution of m-Carmichael numbers with prescribed prime factors, give several particular examples, and summarize the general pattern in Theorem 16. In Section 4, we list some open questions and discuss possible generalizations. In Appendix, we describe our computations of relatively small m-Carmichael numbers.

Throughout this paper, p denotes a prime number. In particular, ∏_{p|n} stands for a product taken over all prime divisors of n.

2 m-Carmichael numbers

Let Φ_{k}(X) be the kth cyclotomic polynomial. The following proposition is well known, but for the reader’s convenience we provide a proof.

Proposition 1. If a ∈ ℤ, then

lcm(a − 1, a^{2} − 1, …, a^{m} − 1) = ∏_{k=1}^{m} Φ_{k}(a).

Proof. We proceed by induction with the obvious base. We have

lcm(a − 1, a^{2} − 1, …, a^{m} − 1) = lcm (∏_{k=1}^{m−1} Φ_{k}(a), a^{m} − 1) =

( ∏_{d|m,d<m} Φ_{d}(a)) · lcm ( ∏_{k∤m,k<m} Φ_{k}(a), Φ_{m}(a)) .

By [2, Theorem 5] we have gcd (Φ_{k}(a), Φ_{l}(a)) = 1 unless \frac{k}{l} is a prime power. Therefore,

gcd ( ∏_{k∤m,k<m} Φ_{k}(a), Φ_{m}(a)) = 1,

and

lcm ( ∏_{k∤m,k<m} Φ_{k}(a), Φ_{m}(a)) = Φ_{m}(a) ∏_{k∤m,k<m} Φ_{k}(a),

which finishes the proof.

Recall that the exponent of a (finite) group G is the least common multiple of orders of elements of G.

Theorem 2. [4, 6] The exponent of GL(m, 𝔽_{p}) equals

p^{⌈log_{p} m⌉} lcm(p − 1, p^{2} − 1, …, p^{m} − 1) = p^{⌈log_{p} m⌉} ∏_{k=1}^{m} Φ_{k}(p).

From now on we assume that m ≥ 2. Notice that if p ≥ m, then the exponent of GL(m, 𝔽_{p}) equals p · ∏_{k=1}^{m} Φ_{k}(p).

Let us introduce the following notation:

D_{m}(n) = ∏_{k=1}^{m} Φ_{k}(n),

∇_{m}(n) = ∏_{p|n} p^{⌈log_{p} m⌉−1},

K_{m}(n) = n∇_{m}(n)D_{m}(n).

In this notation, the exponent of GL(m, 𝔽_{p}) equals K_{m}(p).

Notice also that if p ≥ m, then p^{⌈log_{p} m⌉−1} = 1. Therefore,

∇_{m}(n) = ∏_{p|n, p<m} p^{⌈log_{p} m⌉−1}.

Example 3.

(a) For m = 2, we have ∇_{2}(n) = 1, D_{2}(n) = (n − 1)(n + 1). Thus K_{2}(n) = n(n − 1)(n + 1).

(b) For m = 3, we have ∇_{3}(n) = 1 for n odd, ∇_{3}(n) = 2 for n even, and D_{3}(n) = (n − 1)(n + 1)(n^{2} + n + 1). Therefore, K_{3}(n) = n(n − 1)(n + 1)(n^{2} + n + 1) for n odd and K_{3}(n) = 2n(n − 1)(n + 1)(n^{2} + n + 1) for n even.

Definition 4. A composite number n ∈ ℕ is called an m-Carmichael number if A^{K_{m}(n)} = I for all A ∈ GL(m, ℤ/nℤ).

First, we show that any prime power is an m-Carmichael number. For this purpose, we need two simple lemmas.

Lemma 5. If a ∈ ℤ, k ∈ ℕ, then D_{m}(a) | D_{m}(a^{k}).

Proof. Consider D_{m}(X) = ∏_{k=1}^{m} Φ_{k}(X) ∈ ℤ[X]. Since all roots of D_{m}(X) are simple, and each root of D_{m}(X) is a root of D_{m}(X^{k}), we have D_{m}(X) | D_{m}(X^{k}). Since the polynomial D_{m}(X) is monic, this implies the lemma.

Lemma 6. Let B ∈ Mat(m, ℤ), B ≡ I (mod p). Then for any k ∈ ℕ we have B^{p^{k−1}} ≡ I (mod p^{k}).

Proof. We use induction by k with the obvious base. Let B^{p^{k−1}} = I + p^{k}C. Then, by the binomial theorem, we have

B^{p^{k}} = (I + p^{k}C)^{p} = I + p^{k+1}C + ∑_{l=2}^{p} p^{kl}\binom{p}{l}C^{l} ≡ I (mod p^{k+1}).

Proposition 7. If k ∈ ℕ, k > 1, then p^{k} is an m-Carmichael number.

Proof. Let A ∈ Mat(m, ℤ), gcd(det A, p) = 1. By Theorem 2, we have B := A^{K_{m}(p)} ≡ I (mod p). Therefore, by Lemma 6 we have B^{p^{k−1}} ≡ I (mod p^{k}). Since ∇_{m}(p^{k}) = ∇_{m}(p) and, by Lemma 5, D_{m}(p) | D_{m}(p^{k}), the equation B^{p^{k−1}} = A^{p^{k}∇_{m}(p)D_{m}(p)} ≡ I (mod p^{k}) implies A^{K_{m}(p^{k})} = A^{p^{k}∇_{m}(p^{k})D_{m}(p^{k})} ≡ I (mod p^{k}).

Now we present the main theorem of the paper, an analogue of Korselt’s criterion for a number to be m-Carmichael.

Theorem 8. Let n ∈ ℕ be composite. The following are equivalent:

(1) n is an m-Carmichael number,

(2) if p | n, then D_{m}(p) | K_{m}(n).

Proof. (2) ⟹ (1): Let D_{m}(p) | K_{m}(n) for all p | n. Since p^{ord_{p}(n)}∇_{m}(p) | K_{m}(n) and

gcd(p^{ord_{p}(n)}∇_{m}(p), D_{m}(p)) = 1,

we have p^{ord_{p}(n)}∇_{m}(p)D_{m}(p) | K_{m}(n) for all p | n.

Now consider A ∈ Mat(m, ℤ), gcd(det A, n) = 1. By Theorem 2, we have A^{p∇_{m}(p)D_{m}(p)} ≡ I (mod p) for all p | n. Lemma 6 implies A^{p^{ordp(n)}∇_{m}(p)D_{m}(p)} ≡ I (mod p^{ord_{p}(n)}). Thus, A^{K_{m}(n)} ≡ I (mod p^{ord_{p}(n)}) for all p | n. By the Chinese remainder theorem, A^{K_{m}(n)} ≡ I (mod n). Therefore, n is an m-Carmichael number.

(1) ⟹ (2): Conversely, assume that for some p | n we have D_{m}(p) ∤ K_{m}(n). Since D_{m}(p) = lcm(p−1, p^{2}−1, …, p^{m}−1), there exists k ∈ {1, 2, …, m} such that p^{k}−1 ∤ K_{m}(n).

We construct an element A ∈ GL(m, ℤ/nℤ) of order p^{k} − 1. Therefore, A^{K_{m}(n)} ≠ I, and n is not m-Carmichael.

To this end, let α be a generator of the cyclic group 𝔽_{p^{k}}^{×}. Consider the polynomial (X − α)(X − α^{p}) … (X − α^{p^{k−1}}) ∈ 𝔽_{p}[X], and let B ∈ GL(k, 𝔽_{p}) be its Frobenius companion matrix. Then B is of order p^{k} − 1, and the same is true for C = diag(B, I) ∈ GL(m, 𝔽_{p}). Lift C to an element of Mat(m, ℤ). Then C^{p^{k}−1} ≡ I (mod p). By Lemma 6, we have (C^{p^{ordp(n)−1}})^{p^{k}−1} ≡ I (mod p^{ord_{p}(n)}). Moreover, since gcd(p^{ord_{p}(n)}, p^{k} − 1) = 1, we see that C^{p^{ordp(n)−1}} mod p^{ord_{p}(n)} is also of order p^{k} − 1. Finally, by the Chinese remainder theorem, consider A ∈ GL(m, ℤ/nℤ) such that A ≡ C^{p^{ordp(n)−1}} (mod p^{ord_{p}(n)}) and, for example, A ≡ I (mod \frac{n}{p^{ordp(n)}} ). By construction, A is of order p^{k} − 1, which finishes the proof.

Remark 9. Proposition 7 also follows easily from Theorem 8.

Moreover, applying Theorem 8 and Lemma 5, we get

Corollary 10. If n is an m-Carmichael number, and k ∈ ℕ, then n^{k} is also an m-Carmichael number.

Finally, we present one necessary condition for a number to be m-Carmichael.

Proposition 11. Assume that n is an m-Carmichael number. Then n ≢ 2 (mod 4).

Proof. Let n ∈ ℕ be composite, n ≡ 2 (mod 4). Then D_{m}(n) is odd, and thus ord_{2}(K_{m}(n)) = ⌈log_{2} m⌉.

On the other hand, consider an odd p | n. Since Φ_{2^{k}}(p) = p^{2^{k−1}} + 1 is even for k ≥ 1, and 8 | Φ_{1}(p)Φ_{2}(p) = p^{2} − 1, we have ord_{2}(D_{m}(p)) ≥ ⌊log_{2} m⌋ + 2 > ⌈log_{2} m⌉. Thus, D_{m}(p) ∤ K_{m}(n), and n is not m-Carmichael.

3 m-Carmichael numbers with prescribed prime factors

In Theorem 8, the divisibility condition for small values of m is transparent enough to find some infinite families of m-Carmichael numbers (apart of prime powers).

Let us start with m = 2. Let d_{2}(p, n) denote the condition D_{2}(p) | K_{2}(n), i.e., p^{2} − 1 | n(n^{2} − 1). We have

• d_{2}(2, n) is equivalent to 3 | n(n^{2} − 1), which is satisfied for all n.

• d_{2}(3, n) is equivalent to 8 | n(n^{2} − 1), which is satisfied if and only if n is odd or 8 | n.

• d_{2}(5, n) is equivalent to 3 · 8 | n(n^{2} − 1), which is also satisfied if and only if n is odd or 8 | n.

• d_{2}(7, n) is equivalent to 3·16 | n(n^{2}−1), which is satisfied if and only if n ≡ ±1 (mod 8) or 16 | n.

• d_{2}(11, n) is equivalent to 3 · 5 · 8 | n(n^{2} − 1), which is satisfied if and only if d_{2}(5, n) and 5 | n(n^{2} − 1) are satisfied; the latter is satisfied if and only if n ≡ 0, ±1 (mod 5).

Using the above, the following propositions are proven by a direct application of Theorem 8.

Proposition 12. Let n ∈ ℕ be a composite 7-smooth number which is not a prime power. Then n is 2-Carmichael if and only if n belongs to one of the following families:

1. n = 2^{k} · 3^{l} · 5^{r}, where k ≥ 3, 2. n = 2^{k} · 3^{l} · 5^{r} · 7^{s}, where k ≥ 4, s ≥ 1,

3. n = 3^{l} · 5^{r},

4. n = 3^{l} · 5^{r} · 7^{s}, where l ≡ r (mod 2), s ≥ 1. Proposition 13. Let n ∈ ℕ be a composite 11-smooth number which is not 7-smooth and not a prime power. Then n is 2-Carmichael if and only if n belongs to one of the following families:

1. n = 2^{k} · 3^{l} · 5^{r} · 11^{t}, where k ≥ 3, r ≥ 1,

2. n = 2^{k} · 3^{l} · 5^{r} · 7^{s} · 11^{t}, where k ≥ 4, r ≥ 1, s ≥ 1,

3. n = 2^{k} · 3^{l} · 11^{t}, where k ≥ 3, k ≡ l (mod 2),

4. n = 2^{k} · 3^{l} · 7^{s} · 11^{t}, where k ≥ 4, s ≥ 1, k + l + s is even,

5. n = 3^{l} · 5^{r} · 11^{t}, where r ≥ 1,

6. n = 3^{l} · 5^{r} · 7^{s} · 11^{t}, where r ≥ 1, s ≥ 1, l + r + t is even,

7. n = 3^{l} · 11^{t}, where l is even,

8. n = 3^{l} · 7^{s} · 11^{t}, where s ≥ 1, l ≡ s ≡ t (mod 2). We now consider m = 3 or m = 4. We restrict ourselves to composite numbers of the

form n = 2^{k}3^{l}. Proposition 14. Let n = 2^{k}3^{l}, where k, l ≥ 1. Then n is 3-Carmichael if and only if k ≥ 2, and (k, l) belongs to one of the following families:

1. k ≡ 0 (mod 12), l ≡ 0, 2, 3, 4 (mod 6),

2. k ≡ ±2 (mod 12), l ≡ ±4 (mod 6),

3. k ≡ ±4 (mod 12), l ≡ 0, ±1, 2, 4 (mod 6),

4. k ≡ 6 (mod 12), l ≡ 0 (mod 3). Proposition 15. Let n = 2^{k}3^{l}, where k, l ≥ 1. Then n is 4-Carmichael if and only if k ≥ 3, and (k, l) belongs to one of the families 1) – 4) in Proposition 14 or to one of the following families:

5. k ≡ ±1 (mod 12), l ≡ ±2 (mod 6),

6. k ≡ ±3 (mod 12), l ≡ 0 (mod 3),

7. k ≡ ±5 (mod 12), l ≡ ±4 (mod 6).

Proof of Propositions 14 and 15. We have D_{3}(2) = 3 · 7, D_{4}(2) = 3 · 5 · 7, D_{3}(3) = 2^{3} · 13, D_{4}(3) = 2^{4} · 5 · 13, ∇_{3}(n) = 2, ∇_{4}(n) = 2 · 3. Therefore, n is 3-Carmichael if and only if K_{3}(n) = 2n(n^{2} − 1)(n^{2} + n + 1) is divisible by 2^{3}, 3, 7, and 13, which is equivalent to the conditions 4 | n (i.e., k ≥ 2), n ≡ ±1, 2, 4 (mod 7), n ≡ ±1, 3, 9 (mod 13). Similarly, n is 4-Carmichael if and only if K_{4}(n) = 6n(n^{2} −1)(n^{2} +n+1)(n^{2} +1) is divisible by 2^{4}, 3, 5, 7, and 13, which is equivalent to 8 | n (i.e., k ≥ 3), n ≡ ±1, 2, 4 (mod 7), n ≡ ±1, 3, 9, ±5 (mod 13). Since |𝔽_{7}^{×}| = 6, |𝔽_{13}^{×}| = 12, and 3 mod 13 is of order 3, we see that the conditions on n modulo 7 and 13 depend only on k mod 12, l mod 6. The corresponding values of k mod 12, l mod 6 are obtained by a direct calculation.

Now we describe the general pattern of the distribution of m-Carmichael numbers with prescribed prime factors.

Let P be a finite nonempty subset of primes. Let D_{m}(P) denote the least common multiple of D_{m}(p) for all p ∈ P.

Let us say that n ∈ ℕ is a P -number, if n is divisible precisely by the primes in P. By Theorem 8, a P -number n is m-Carmichael if and only if D_{m}(P) | K_{m}(n).

Further, write D_{m}(P) = D′_{m}(P)D′′_{m}(P), where D′_{m}(P) is a product of primes in P, and D′′_{m}(P) is coprime to all p ∈ P. Then a P -number n is m-Carmichael if and only if D′_{m}(P) | K_{m}(n) and D′′_{m}(P) | K_{m}(n).

First, notice that, since n | K_{m}(n), ∇_{m}(P) := ∇_{m}(n) depends only on P, and D′_{m}(P) is coprime to D_{m}(n), it follows that the condition D′_{m}(P) | K_{m}(n) is satisfied if and only if ord_{p} n ≥ ord_{p} D′_{m}(P) − ord_{p} ∇_{m}(P) for all primes p ∈ P.

Secondly, since a P -number n is, by construction, invertible modulo D′′_{m}(P), we see that the condition D′′_{m}(P) | K_{m}(n) depends only on the values of ord_{p} n mod λ(D′′_{m}(P)) for p ∈ P. Here λ is the Carmichael function, i.e., λ(D′′_{m}(P)) is the exponent of the group (ℤ/D′′_{m}(P)ℤ)^{×}. Moreover, if p ∈ P, let v_{m,P} (p) denote the order of p mod D′′_{m}(P) in the group (ℤ/D′′_{m}(P)ℤ)^{×}. Then the condition D′′_{m}(P) | K_{m}(n) depends only on the values of ord_{p} n mod v_{m,P} (p) for p ∈ P.

Thus, we get the following

Theorem 16. For any p ∈ P, the set of P -numbers which are m-Carmichael is invariant under multiplication by p^{v_{m,P} (p)}.

Corollary 17. Assume that there exists a P -number which is m-Carmichael. Then there are infinitely many of them.

Remark 18. Corollary 17 follows also from Corollary 10.

All propositions of this section can be viewed as examples of Theorem 16. For example, for m = 3 and P = {2, 3} we have D′_{m}(P) = 2^{3}·3, D′′_{m}(P) = 7·13, and λ(7·13) = lcm(6, 12) = 12, v_{m,P} (2) = 12, v_{m,P} (3) = 6, which is in accordance with Proposition 14.

4 Concluding remarks

We list some natural questions that remain open.

• For what m and P are there P -numbers which are m-Carmichael?

• Are there squarefree m-Carmichael numbers for m ≥ 3?

Remark 19. One can consider an analogous notion for other affine group schemes of finite type defined over ℤ. Namely, if G is such a group scheme, K_{G}(p) the exponent of the group G(𝔽_{p}), and K_{G}(n) its reasonable extrapolation to all n ∈ ℕ, then one can consider G-Carmichael numbers, i.e., composite n ∈ ℕ such that g^{K_{G}(n)} = 1 for all g ∈ G(ℤ/nℤ).

5 Acknowledgments

The research of the second author was partially supported by the Akhiezer Foundation.

A Numerical experiments

We calculate, via brute force, all m-Carmichael numbers up to 10^{5} for 2 ≤ m ≤ 10. Let us call an m-Carmichael number nontrivial if it is not a prime power. There are 1330 nontrivial 2-Carmichael numbers, 44 nontrivial 3-Carmichael numbers, and 28 nontrivial 4-Carmichael numbers on the researched interval. There are no nontrivial m-Carmichael numbers for 5 ≤ m ≤ 10 on the researched interval.

Among 16 Carmichael numbers less than 10^{5}, the following four, namely,

1729 = 7 · 13 · 19, 2465 = 5 · 17 · 29, 6601 = 7 · 23 · 41, 41041 = 7 · 11 · 13 · 41,

are 2-Carmichael. None of these Carmichael numbers are m-Carmichael for 3 ≤ m ≤ 10. Moreover, none of m-Carmichael numbers for 3 ≤ m ≤ 10 on the researched interval are squarefree.

There are 18 numbers on the researched interval, namely,

48 = 2^{4} · 3,  144 = 2^{4} · 3^{2},  1296 = 2^{4} · 3^{4},  1728 = 2^{6} · 3^{3},
2304 = 2^{8} · 3^{2},  5760 = 2^{7} · 3^{2} · 5, 9216 = 2^{10} · 3^{2},  11664 = 2^{4} · 3^{6},
20736 = 2^{8} · 3^{4},  25600 = 2^{10} · 5^{2},  27000 = 2^{3} · 3^{3} · 5^{3}, 30720 = 2^{11} · 3 · 5,
34992 = 2^{4} · 3^{7},  36864 = 2^{12} · 3^{2},  46656 = 2^{6} · 3^{6},  62208 = 2^{8} · 3^{5},
96768 = 2^{9} · 3^{3} · 7, 99225 = 3^{4} · 5^{2} · 7^{2},

that are nontrivial m-Carmichael numbers for all m ∈ {2, 3, 4}, and one number, 22815 = 3^{3} · 5 · 13^{2}, that is nontrivial 3-Carmichael and 4-Carmichael, but not 2-Carmichael.

Also, on the researched interval there are 19 numbers, namely,

160 = 2^{5} · 5,  448 = 2^{6} · 7,  704 = 2^{6} · 11,  800 = 2^{5} · 5^{2},
1056 = 2^{5} · 3 · 11, 2640 = 2^{4} · 3 · 5 · 11, 3136 = 2^{6} · 7^{2}, 5929 = 7^{2} · 11^{2},
7744 = 2^{6} · 11^{2},  18144 = 2^{5} · 3^{4} · 7, 20000 = 2^{5} · 5^{4}, 21952 = 2^{6} · 7^{3},
28672 = 2^{12} · 7,  29952 = 2^{8} · 3^{2} · 13, 31744 = 2^{10} · 31, 34496 = 2^{6} · 7^{2} · 11,
39424 = 2^{9} · 7 · 11, 45056 = 2^{12} · 11,  85184 = 2^{6} · 11^{3},

that are nontrivial 2- and 3-Carmichael, but not 4-Carmichael; 8 numbers, namely,

\begin{matrix}216 = 2^{3} · 3^{3}, & 1152 = 2^{7} · 3^{2}, & 2592 = 2^{5} · 3^{4}, & 4000 = 2^{5} · 5^{3}, \\ 5832 = 2^{3} · 3^{6}, & 13824 = 2^{9} · 3^{3}, & 28800 = 2^{7} · 3^{2} · 5^{2}, & 73728 = 2^{13} · 3^{2}, \end{matrix}

that are nontrivial 2- and 4-Carmichael, but not 3-Carmichael; 6 numbers, namely,

\begin{matrix}324 = 2^{2} · 3^{4}, & 900 = 2^{2} · 3^{2} · 5^{2}, & 1404 = 2^{2} · 3^{3} · 13, \\ 39204 = 2^{2} · 3^{4} · 11^{2}, & 74088 = 2^{3} · 3^{3} · 7^{3}, & 74536 = 2^{3} · 7 · 11^{3}, \end{matrix}

that are nontrivial 3-Carmichael, but not 2- or 4-Carmichael. Finally, one number, 26112 = 2^{9} · 3 · 17, is nontrivial 4-Carmichael, but not 2- or 3-Carmichael.

Below we list all nontrivial 2-Carmichael numbers up to 3000 that are not treated by Propositions 12 and 13 (i.e., not 11-smooth).

104 = 2^{3} · 13  171 = 3^{2} · 19  195 = 3 · 5 · 13  273 = 3 · 7 · 13
351 = 3^{3} · 13  435 = 3 · 5 · 29  455 = 5 · 7 · 13  609 = 3 · 7 · 29
615 = 3 · 5 · 41  624 = 2^{4} · 3 · 13 665 = 5 · 7 · 19  715 = 5 · 11 · 13
736 = 2^{5} · 23  759 = 3 · 11 · 23 832 = 2^{6} · 13  855 = 3^{2} · 5 · 19
903 = 3 · 7 · 43  1001 = 7 · 11 · 13 1015 = 5 · 7 · 29 1045 = 5 · 11 · 19
1071 = 3^{2} · 7 · 17 1088 = 2^{6} · 17  1183 = 7 · 13^{2}  1216 = 2^{6} · 19
1265 = 5 · 11 · 23 1352 = 2^{3} · 13^{2}  1377 = 3^{4} · 17  1431 = 3^{3} · 53
1456 = 2^{4} · 7 · 13 1520 = 2^{4} · 5 · 19 1539 = 3^{4} · 19  1560 = 2^{3} · 3 · 5 · 13
1595 = 5 · 11 · 29 1625 = 5^{3} · 13  1729 = 7 · 13 · 19 1856 = 2^{6} · 29
1881 = 3^{2} · 11 · 19 1911 = 3 · 7^{2} · 13 1984 = 2^{6} · 31  2001 = 3 · 23 · 29
2009 = 7^{2} · 41  2015 = 5 · 13 · 31 2080 = 2^{5} · 5 · 13 2211 = 3 · 11 · 67
2255 = 5 · 11 · 41 2365 = 5 · 11 · 43 2375 = 5^{3} · 19  2457 = 3^{3} · 7 · 13
2465 = 5 · 17 · 29 2535 = 3 · 5 · 13^{2} 2565 = 3^{3} · 5 · 19 2624 = 2^{6} · 41
2639 = 7 · 13 · 29 2736 = 2^{4} · 3^{2} · 19 2808 = 2^{3} · 3^{3} · 13 2871 = 3^{2} · 11 · 29
2912 = 2^{5} · 7 · 13 2925 = 3^{2} · 5^{2} · 13

Also, we manage to compute a few larger m-Carmichael numbers for m ≥ 5. We consider numbers of the form 2^{k}3^{l} for relatively small values of k and l and apply Theorem 8. For instance, 2^{22} · 3^{2} is 2- (by Proposition 12), 3- (by Proposition 14), 4- (by Proposition 15), 5- and 6-Carmichael, but not 7- or 8-Carmichael. Similarly, 2^{286} · 3^{36} is 2-, 6-, 7-, and 8-Carmichael, but not 3-, 4-, or 5-Carmichael.

References

[1] W. R. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), 703–722.

[2] Y. Ge, Elementary properties of cyclotomic polynomials, Math. Reflec. 2 (2008).

[3] E. W. Howe, Higher-order Carmichael numbers, Math. Comp. 69 (2000), 1711–1719.

[4] J. B. Marshall, On the extension of Fermat’s theorem to matrices of order n, Proc. Edinb. Math. Soc. 6 (1939), 85–91.

[5] R. J. McIntosh, M. Dipra, Carmichael numbers with p + 1 | n + 1, J. Number Theory 147 (2015), 81–91.

[6] I. Niven, Fermat’s theorem for matrices, Duke Math. J. 15 (1948), 823–826.

[7] G. A. Steele, Carmichael numbers in number rings, J. Number Theory 128 (2008), 910–917.

2010 Mathematics Subject Classification: Primary 11A51, Secondary 11Y11, 20G30. Keywords: Carmichael number, pseudoprime, general linear group.

(Concerned with sequences \underline{A002997} and \underline{A336663}.)

Received March 3 2020; revised version received July 30 2020. Published in Journal of Integer Sequences, October 18 2020.

Return to Journal of Integer Sequences home page.