Inclusion-exclusion principle generalization of Fermat's little theorem

Question

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.

Answer 1

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

Answer 2

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.