# Carmichael and $k$-Lehmer Polynomials

Abstract: A Carmichael number is a composite number $n$ that satisfies $a^{n-1} \equiv 1 \mod{n}$, for all integers $a$ such that $\gcd(a,\, n) = 1$. They are of interest in primality testing. Hsu defines Carmichael polynomials in $\mathbb{F}_q[x]$ for any prime power $q$, and shows that there are infinitely many such polynomials. We prove that for any $\mathbf{a},\, \mathbf{M} \in \mathbb{F}_q[x]$ where $\mathbf{M}$ is monic and $\gcd(\mathbf{a},\, \mathbf{M}) = 1$, there are infinitely many Carmichael polynomials that are congruent to $\mathbf{a}$ modulo $\mathbf{M}$. We also define analogues of Grau and Oller-Marc\'{e}n's $k$-Lehmer numbers and prove that for infinitely many $k$ there are Carmichael polynomials that are $k$-Lehmer but not $(k-1)$-Lehmer.