Inclusion-exclusion principle generalization of Fermat's little theorem

Suppose natural number $$p$$ has the unique prime decomposition $$p=\prod_{i=1}^n p_i^{k_i}$$ where $$p_i$$'s are distinct primes and $$k_i$$'s are natural numbers. Let $$N:=\{1,2,\cdots,n\}$$ and $$x:=\sum_{J\subseteq N}(-1)^{|J|}c^{p_J},\quad p_J:=\frac{p}{\prod_{i\in J}p_i},$$ where $$c$$ is yet another natural number. How does one show that $$p|x$$? This conjecture generalizes Fermat's little theorem as it is the case when $$p$$ is prime.

I thought of pairing the summands up and apply Fermat's little theorem but to no avail.

$$x$$ is in fact an enumeration using the inclusion-exclusion principle (hence the sum with alternating signs) resulting from a simplified variation on this question enumerating the bead color arrangement.

• symmetry of cardinality under parity helps. The real stick8ng point is c isn't restricted to coprime and the $p_J$ are simply restricted divisors of p.
– user645636
Jun 25, 2019 at 13:02
• @RoddyMacPhee: I edited my question to include my try of pairing summands up. I do not know if you are making deeper inroads. It would help if you elaborate.
– Hans
Jun 25, 2019 at 16:03
• I don't see Fermat's little theorwm as applicable quite honestly.
– user645636
Jun 25, 2019 at 17:17

Your are looking at $$\sum_{d | m} \mu(d) c^{\frac m d}$$

It is the number of non-periodic sequences $$\in \{1,\ldots, c\}^m$$ $$\# \{ a \in \{1,\ldots, c\}^m,\ \forall l\not\equiv0\mod m,\ T^l a \ne a\}$$ (where $$(T a)_j = a_{j+1 \bmod m}$$ is the shift operator)

The cyclic group generated by $$T$$ acts on $$\{ a \in \{1,\ldots, c\}^m,\ \forall l\not\equiv0\mod m,\ T^l a \ne a\}$$ and $$\frac1m \sum_{d | m} \mu(d) c^{\frac m d}$$ is the number of orbits.

I don't think you'll find other proofs that $$m$$ divides $$\sum_{d | m} \mu(d) c^{\frac m d}$$.

• The end expression of this answer reminds me of the Orbit-Stabilizer Theorem (en.wikipedia.org/wiki/…), is this an analog? Jun 27, 2019 at 6:13
• +1. The first sentence is not necessary. You are right, except @metamorphy has a direct modular arithmetic proof expanding on my vague idea. I am intrigued by your assertion on the number of non-periodic sequence, which is precisely the source of the question itself. I had a proof using the inclusion-exclusion principle which I link to in the question. I suppose your proof applies the Möbius transform which is a special case of the inclusion-exclusion principle. Is this right? More intriguingly, how did you come up with the connection to the non-periodic sequence?
– Hans
Jun 27, 2019 at 10:23

The pairing works, with a step ahead of "little Fermat".

For integers $$a$$, $$b$$, $$k>0$$, $$p$$ prime, we have $$a\equiv b\pmod{p^k}\implies a^p\equiv b^p\pmod{p^{k+1}}.$$

(Indeed, $$(b+p^k c)^p\equiv b^p\pmod{p^{k+1}}$$ by the binomial expansion.)

For integers $$a$$, $$k>0$$, $$p$$ prime, we have $$a^{p^k}\equiv a^{p^{k-1}}\pmod{p^k}$$.

(Induction on $$k$$ using the prior result, the base $$k=1$$ is "little Fermat".)

Returning to the problem in question, we see that $$p_i^{k_i}\mid x$$ for each $$1\leqslant i\leqslant n$$, by pairing each $$J\subseteq N\setminus\{i\}$$ with $$J\cup\{i\}$$, and using the above.

• +1. Nice. Glad to see I went at least in the right direction.
– Hans
Jun 26, 2019 at 1:13