A variation of Fermat's little theorem in the form $a^{n-d}\equiv a$ (mod $p$).

Question

Fermat's little theorem states that for $n$ prime,

$$ a^n \equiv a \pmod{n}. $$

The values of $n$ for which this holds are the primes and the Carmichael numbers. If we modify the congruence slightly,

$$ a^{n - 1} \equiv a \pmod{n}, $$

the values of $n$ for which it holds are listed in A216090: 1, 2, 6, 10, 14, 22, 26, 30, 34, 38, 46, ...

More generally, we can examine the values of $n$ where

$$ a^{n - d} \equiv a \pmod{n} $$

for all $a$ and a given $d$. $d = 0$ gives the primes/Carmichael numbers, $d = 1$ gives the sequence A216090, and $d = 2$ gives the sequence 1, 2, 3, 15, 21, 33, 39, 51, 57, 69, 87, ...

For $d = 3$, the sequence grows much more rapidly: 1, 2, 4, 6, 154, 4774, 23254, 179014, 187054, 1066054, 1168654, ... But for $d = 4$, the growth slows down again: 1, 2, 3, 5, 65, 85, 145, 165, 185, 205, 265, ...

The first few $d$ values which give fast-growing sequences for $n$ are 3, 7, 8, 11, 15, 17, 19, 23, 24, and 26. In general, the sequence seems to grow particularly quickly when $d + 1$ is not squarefree.

I've proven this generalization of Korselt's criterion that characterises the possible $n$ values for a given $d$:

Theorem (Generalized Korselt's criterion). Let $d$ be an arbitrary integer, and $n$ a positive integer such that and $n \ge d + 1$. Then $a^{n - d} \equiv a \pmod{n}$ for all $a \in \mathbb{Z}$ if and only if either

• $n = 1$ or $2$;
• $n = d + 1$; or
• $n$ is squarefree, and for each of $n$'s prime divisors $p_i$, $(p_i - 1) \vert (n - d - 1)$.

Additionally, I've observed the following pattern that would explain why the squarefreeness of $d + 1$ matters:

Conjecture. When $d + 1$ is squarefree, many prime multiples of $d + 1$ are valid values for $n$. But if $d + 1$ is not squarefree, no multiples of it (except possibly itself) are feasible values for $n$. In either case, valid $n$ values which are not multiples of $d + 1$ are much less abundant.

Any ideas how to tackle this conjecture, or at least make it more explicit?

Answer 1

If $d+1$ is not squarefree, then the multiples of it are not squarefree, therefore your value of $n$ is not squarefree, so then by the Generalized Korselt's criterion it is not a valid value of $n$, unless it equals $d+1$ itself, but that is just one case.

If $d+1$ is squarefree, we note that for every prime $p \geq d+1$ we have that $n=p(d+1)$ is squarefree. Then we want that for every prime divisior $q_i$ of $n$, that $q_i-1 \mid (p-1)(d+1)$. It surely holds for $q_i=p$. Note that since $d+1$ is squarefree, we have that $$\varphi(d+1)=(p_1-1)(p_2-1)(p_3-1) \cdots(p_t-1)$$

Here $\varphi(x)$ is the Euler-phi function.

Therefore if $\varphi(d+1) \mid p-1$, then our $n$ is a possibility. In other words, if $p = k \varphi(d+1) + 1$ for some $k$. Note that we always have $\varphi(d+1) \leq d$, so there are quite a few values.

Since $\gcd(\varphi(d+1),1)=1$, we have by a stronger version of Dirichlet's theorem that the primes in this arithmetic progression are distributed just as in the natural numbers, i.e. there are about $\frac{x}{\ln(x)}$ primes when $k<x$ ($k$ as in $p = k \varphi(d+1) + 1$). This gives some information on the second part of the conjecture.

For example, when $d=4$, $13\cdot5$, $17\cdot5$, $29 \cdot 5$ and $31 \cdot 5$, are all in your sequence, and they indeed have the form I described above.

Note: One could use $\lambda(x)$, the Carmichael function, instead of $\varphi(x)$.