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 {n} $$ 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!

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!

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 {n} $$ for any prime $p$, that is the Fermat's little theorem.

This relationship looks appealing to me, at least for studying Fermat pseudoprimes.

QUESTION 2: Is this generalisation of FLT a known result? If yes, could you please provide references?

Thanks,

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

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 {n} $$ 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!