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?

  • 19
    $\begingroup$ For your proved result, did you look at this paper? user.math.uzh.ch/halbeisen/publications/pdf/lauchmichel.pdf $\endgroup$ Sep 29 '14 at 21:01
  • $\begingroup$ @JeffreyShallit No I didn't, but that paper seems to have a lot of relevant information. Thanks! $\endgroup$ Sep 29 '14 at 21:08
  • 5
    $\begingroup$ Thanks for the paper @Jeffrey Shallit $\endgroup$
    – Muneeb
    Mar 31 '15 at 0:40
  • $\begingroup$ Why have you written $a^{n-1}\equiv a\pmod n$ instead of $a^{n-1}\equiv1\pmod n$? $\endgroup$
    – Soham
    Sep 2 '16 at 11:32
  • 1
    $\begingroup$ @tatan: Erm, because that's the congruence I'm interested in? $a^{n - 1} \equiv 1 \pmod{n}$ is just Fermat's little theorem again for $p \nmid a$. $\endgroup$ Sep 2 '16 at 19:22

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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.