# Carmichael polynomials from Egyptian fractions

A Carmichael number is a number that is a Fermat pseudoprime modulo all coprime bases. Equivalently, by Korselt's criterion, it is a squarefree number that is congruent to one modulo \( p-1 \) for each prime factor \( p \). Chernick (1939) seems to have been the first to observe that Korselt's criterion can be generalized to integer polynomials. Chernick considered polynomials that are congruent to one modulo all the polynomials formed by subtracting one from an irreducible factor. When an argument to the polynomial makes all its irreducible factors evaluate to prime numbers, the polynomial itself evaluates to a Carmichael number. For this reason Chernick called these polynomials universal forms.

One of Chernick's universal forms is the polynomial \( (6x+1)(12x+1)(18x+1) \). This produces Carmichael numbers when \( x \) is 1, 6, 35, 45, 51, 55, 56, 100, ... (OEIS:A046025). By Dickson's conjecture there are infinitely many values of \( x \) that make all three factors prime and therefore infinitely many Carmichael numbers of this form. Not all of Chernick's universal forms are like this, but in this one all the irreducible factors are a monomial plus one. This property makes it particularly easy to test that the whole polynomial is one modulo each irreducible factor minus one: we need only test whether each of the leading monomials \( 6x \), \( 12x \), and \( 18x \) in the factors of the polynomial divides each of the non-constant monomials in the polynomial itself.

So what's special about (6,12,18) here? Do other triples of numbers work? Why or why not? Obviously, integer multiples of the same three numbers also work, but what about other triples that are not in the proportions (1,2,3)?

To answer this we need to look for coefficients \( c_i \) such that each monomial \( c_i x \) divides each non-constant monomial of the polynomial \( N(x)=\prod(c_i x + 1) \). We can easily ensure that each monomial \( c_i x \) divides the monomials of \( N(x) \) of degree two or more, by multiplying all coefficients by the same common factor, the least common multiple of the original coefficients. E.g. if we start with (1,2,3) and multiply by the least common multiple 6, we get Chernick's coefficients (6,12,18).

So the tricky part is divisibility for the linear term of \( N(x) \), which is just the sum of the coefficients \( c_i x \). To get a universal form, we seek a set of coefficients such that each coefficient divides the sum of all coefficients, including itself. And we might as well add the constraint that the coefficients have no common factor, because such a factor doesn't help with this part and can be dealt with separately for the higher-degree terms. For instance, for the reduced version of Chernick's set, each coefficient 1, 2, 3 divides the sum of coefficients 1 + 2 + 3 = 6.

If we set up an equation with the left side being the sum of the coefficients and the right side being the value they sum to, we can get an equivalent equation by dividing by the sum. Each term on the left side becomes a unit fraction (because each coefficient divides the sum) and the value on the right side just becomes 1. So we get an equation like 1/integer + 1/integer + 1/integer = 1. All three of the unit fractions in this expression must be distinct, because we want our universal form to be squarefree. And conversely, if we have a solution to an equation like this, we can multiply everything by the least common multiple of the denominators of the unit fractions and get a collection of integer coefficients that divide their sum.

But what this equation describes is exactly an Egyptian fraction representation of 1. What the analysis above shows is that, if you have an Egyptian fraction representation, and then multiply both sides of the equation by the square of the LCM (one LCM to turn everything from fractions to integers and a second one to deal with the higher-degree divisibility requirements) you get the coefficients of a universal form. And every universal form with linear terms whose constant coefficients are 1 is proportional to a solution to an Egyptian fraction in this way.

There are infinitely many Egyptian fraction representations of 1, but only finitely many of each length. \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{6} \) is the only one of length three, but for length four we have \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{7}+\tfrac{1}{42} \), \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{8}+\tfrac{1}{24} \), \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{9}+\tfrac{1}{18} \), \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{10}+\tfrac{1}{15} \), \( \tfrac{1}{2}+\tfrac{1}{4}+\tfrac{1}{5}+\tfrac{1}{20} \), \( \tfrac{1}{2}+\tfrac{1}{4}+\tfrac{1}{6}+\tfrac{1}{12} \), etc. To find a Chernick-like tuple from one of these monomials, say \( \tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{10}+\tfrac{1}{15} \), first multiply it by the least common multiple \( 30 \) of the denominators to give an integer tuple \( (15,10,3,2) \) and then multiply it by the least common multiple \( 30 \) again to make sure that the high-degree divisibilities work, giving \( (450,300,90,60) \). Then whenever we can find \( x \) such that \( 60x+1 \), \( 90x+1 \), \( 300x+1 \), and \( 450x+1 \) are all prime, their product will be a Carmichael number. The first \( x \) that works is 11, giving the Carmichael number \( 661\times 991\times 3301\times 4951 = 10705662910801 \).

Chernick's original paper includes universal forms that don't have 1 as their constant coefficient, which allows for a much greater variety of these polynomials. For instance, \( (10x+7)(20x+13)(50x+31) \) is one of Chernick's universal forms; this is related to the fact that \( 7\times 13\times 31 \) is a Carmichael number. Chernick also proves the existence of universal forms with any number of factors greater than two, with \( 1 \) as the constant coefficient for all polynomials. But he seems to have missed the connection to Egyptian fractions. If this connection is represented elsewhere in later publications, I'd be interested to find out about it.