10
$\begingroup$

I would like to share a personal result, which I interpret as a "generalisation of Fermat's little theorem". I know that there exist already several generalisations (e.g. Euler's) but I would like to know whether the result I found is something original or not. Let me explain...

Some years ago, my researches on binary representation of numbers lead me to this sequence of naturals: 1, 2, 1, 2, 3, 6, 9, 18, 56, ... . After some researches, I found that this was already indexed as A001037 sequence in OEIS; this is known as number of "binary Lyndon words of length $n$" or "$n$-bead necklaces with beads of 2 colors". Such sequence can easily be generalised to other bases than 2. After naming $\lambda_a(n)$ the number of $n$-bead necklaces with beads of $a$ colors with $a \ge 2$, I found that $$ a^n = \sum_{d|n} d \lambda_a(d) $$ For example, $$ 2^6 = 1\lambda_2(1) + 2\lambda_2(2) + 3\lambda_2(3) + 6\lambda_2(6) = 2 + 2 + 6 + 54 = 64 $$

This is NOT an original result since you can find this relationship on the afore-mentioned OEIS page, at least.

QUESTION 1: Can someone provides references for a proof of this equation (papers, books, ...)?

Now, after defining $$ \sigma_a(n) \triangleq \sum_{\substack{ d|n \\ 1<d<n}} d \lambda_a(d) $$ the previous equation can be rewritten $$ a^n = a + n\lambda_a(n) + \sigma_a(n) $$ Then, using modular arithmetic, we obtain a generalisation of Fermat's little theorem: $$ a^n \equiv a + \sigma_a(n) \pmod {n} $$

Note that this is indeed a generalisation since it applies on any natural $n$ and it boils down to $$ a^p \equiv a \pmod {p} $$ for any prime $p$, that is the Fermat's little theorem.

This relationship looks appealing to me, at least for studying Fermat pseudoprimes: these are the composites $n$ having the "rare" property that $\sigma_a(n) \equiv 0 \pmod {n}$.

QUESTION 2: Is this generalisation of Fermat's little theorem a known result? If yes, could you please provide references?

Thanks,

PS: Please, be indulgent: this is my very first post on MO!

$\endgroup$
  • 1
    $\begingroup$ Does Example 2.2(3) here suffice? $\endgroup$ – Benjamin Dickman Jun 12 '15 at 23:07
  • $\begingroup$ This may be in Joe Roberts's calligraphic text on number theory. $\endgroup$ – The Masked Avenger Jun 12 '15 at 23:48
  • 9
    $\begingroup$ According to Dickson's History of the Theory of Numbers, Volume 1, p. 84 (archive.org/details/historyoftheoryo01dick) this generalization of Fermat's theorem is due to Gauss, at least when $a$ is a prime. On p. 82 Dickson gives a reference for the general case to Thue in 1910, though it may be older. $\endgroup$ – Ira Gessel Jun 12 '15 at 23:54
  • 2
    $\begingroup$ This is not new. Google "necklace polynomials" and consider the fact that they are integral-valued. $\endgroup$ – KConrad Jun 13 '15 at 3:50
  • 1
    $\begingroup$ This result has also been attributed to Ramachandra (mathoverflow.net/questions/87048/…). $\endgroup$ – Ira Gessel Jun 13 '15 at 15:36
7
$\begingroup$

Here's a massive generalization, with references.

Consider a sequence $\{a_n \}_{n\ge 1}$ of integers. We'll say it satisfies the necklace congruences if $a_{n} \equiv a_{n/p} \mod n$ whenever $p \mid n$ ($p$ prime).

Here are some equivalent formulations:

  • $a_{p^{k+1} m} \equiv a_{p^k m} \mod {p^{k+1}}$ for all $p,m,k$
  • $\sum_{d \mid n} a_d \mu(n/d) \equiv 0 \mod n$ for all $n$
  • The Mobius function can be replaced by any arithmetic function $f$ satisfying $\sum_{d \mid n} f(d) =0 \mod n, f(1) = \pm 1$.

So any such sequence gives rise to an integer sequence $\lambda_{\tilde{a}}(n) := \frac{1}{n}\sum_{d \mid n} a_d \mu(n/d)$ which satisfies $a_n = \sum_{d \mid n} d \lambda_{\tilde{a}}(n)$ by Mobius inversion. One can then define $\sigma_{\tilde{a}}(n):=\sum_{d \mid n, 1<d<n} d\lambda_{\tilde{a}}(d)$ and obtain the following generalization of Fermat's little theorem:

$a_n \equiv a_1 + \sigma_{\tilde{a}}(n) \mod n$

Now, let's go back to necklace congruences. A less obvious equivalence is the following:

Theorem: $\{a_n\}_{n \ge 1}$ satisfies the necklace congruences iff $\zeta_{a}(x):=\exp(\sum_{n\ge1} \frac{a_n}{n}x^n)$ has integer coefficients.

Proof: Write, $\zeta_a$ formally as $\prod_{n\ge 1} (1-x^n)^{-\frac{b_n}{n}}$. The $b_n$'s are uniquely determined, and in fact (by taking logarithmic derivative) it can be seen that they are $b_n = \sum_{d \mid n} a_d \mu(n/d)$. Now one direction is immediate and the other requires an inductive argument. $\blacksquare$

(Reference: Exercise 5.2 (and its solution) in Richard Stanley's book "Enumerative Combinatorics, vol. 2")

As Sergei remarked, for any integer square matrix $A$, the sequence $a_n := \text{Tr}(A^n)$ satisfies the necklace congruences. This is immediate from the last theorem, as the corresponding "zeta" function $\zeta_a$ is just:

$\exp( \sum_{n \ge 1} \frac{\text{Tr}((Ax)^n)}{n}) = \exp (\text{Tr} (- \ln (I -Ax)))=\det(I-Ax)^{-1} \in \mathbb{Z}[x]$

In particular, by taking a 1 on 1 matrix, we recover your observation.

Another generalization is $a_n = [x^n]f^n(x)$, where $f \in \mathbb{Z}[[x]]$. By taking the linear polynomial $f(x)=1+ax$ we recover your example, by taking $f(x)=(1+x)^m$ we get $a_n = \binom{nm}{n}$.

The really interesting feature is that this notion has a local version. Specifically, theorems of Dieudonne-Dwork and Hazewinkel give the following result:

Theorem: Given $\{ a_n \}_{n\ge 1} \subseteq \mathbb{Q}_{p}$ ($p$-adic numbers), the following are equivalent:

  • $\zeta_{a}(x) := \exp(\sum_{n\ge 1} \frac{a_n }{n}x^n)\in\mathbb{Z}_{p}[x]$
  • $\exp( \sum_{n \ge 1} p \frac{a_n - a_{n/p}}{n} x^n) \in 1+px\mathbb{Z}_{p}[x]$ (I defnite $a_{n/p}=0$ if $p\nmid n$)
  • $\sum_{n \ge 1} \frac{a_n - a_{n/p}}{n} x^n) \in \mathbb{Z}_{p}[x]$
  • $p \mid n \implies a_n \equiv a_{n/p} \mod {n\mathbb{Z}_{p}}$

Applying this simultaneously for all $p$, we recover the previous theorem. A reference for this theorem is "A Course in p-adic Analysis" by Alain M. Robert (the theorems are stated there in a much more general context).

$\endgroup$
  • $\begingroup$ Impressive, Ofir! You show that the Fermat's little theorem can be generalised even further than for $a^n$, which is a special case of a sequence satisfying the "necklace congruence", as you defined. You provide other general instances of such sequences, which indeed can be instantiated as $a^n$. However, I am still wondering whether you answered my questions or not... I must admit that some parts remain obscure for me, due to my lack of background. $\endgroup$ – Pierre Denis Jun 14 '15 at 22:06
  • 1
    $\begingroup$ Small typo: You wrote $\sum_{d|b}$ after the bullet points. Should be $\sum_{d|n}$ ! $\endgroup$ – Pierre Denis Jun 14 '15 at 22:11
  • $\begingroup$ I am trying to understand the very last paragraph. I cannot even understand the syntax after "in the congruences...". Can you please check and/or rephrase? Thanks. $\endgroup$ – Pierre Denis Jun 14 '15 at 22:19
  • 1
    $\begingroup$ @PierreDenis First of all, thanks for pointing out the typo (corrected now). My last paragraph was indeed not very clear, and I deleted it. What I do have to say is that (as far as I can tell), calculating the $\sigma_{a}(n)$ requires knowing the factorization of $n$, unless $n=1$ or $n=p$ (which are the non-interesting cases), and it is probably easier to study the equation $a^n \equiv a \mod n$ directly. But I'm not an expert in this field at all. $\endgroup$ – Ofir Gorodetsky Jun 15 '15 at 14:52
  • $\begingroup$ Indeed, $ \sigma_a(n) \bmod n $ doesn't bring any new information compared to $ (a^n-a) \bmod n $. However, my idea was to look at residues term by term, i.e. the $ (d \lambda_a(d)) \bmod n $. I have at least one result so far for Fermat pseudoprimes with just two prime factors (aka semiprimes): I think that I can prove that for any distinct primes $p,q$, $a^{pq} \equiv a \pmod{pq} \iff a^p \equiv a \pmod{q} \wedge a^q \equiv a \pmod{p}$. OK, probably another known result...! $\endgroup$ – Pierre Denis Jun 15 '15 at 22:44
3
$\begingroup$

In this paper (in Russian) : http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=mp&paperid=238&option_lang=eng there are discussion of this result, including theorem of Gauss, generalization to matrices by V.I.Arnold and so on.

$\endgroup$
  • $\begingroup$ Thanks Sergei but I don't understand Russian, unfortunately. I've tried to guess by looking at the formulas but I don't see something similar to the congruence I gave above. Could you please give me the page number / formula number in the paper so I can use a translator on the right part? $\endgroup$ – Pierre Denis Jun 13 '15 at 18:09
  • $\begingroup$ @PierreDenis, equation (12) in section 3 is the main point for you. It says $\sum_{d|m} \mu(m/d)a^d \equiv 0 \bmod m$ for any $a \in \mathbf Z$ (of course it suffices to check only for $1 \leq a \leq m-1$). He notes Gauss proved it for prime $a$ and other mathematicians proved it in general by several mathematicians in the 1880s. $\endgroup$ – KConrad Jun 13 '15 at 20:40
  • $\begingroup$ Thanks for spotting. This is indeed a generalisation of Fermat's little theorem. However, as I wrote to Ira Gessel (see comments above), I am looking for references that do not use Möbius function or the like, i.e. without any negative terms, as shown in my post. $\endgroup$ – Pierre Denis Jun 14 '15 at 9:42

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.