Show that for each prime \(p\), there exists a prime \(q\) such that \(n^p − p\) is not divisible by \(q\) for any positive integer \(n\).
Note that $\dfrac{p^p-1}{p-1}=p^{p-1}+\ldots + p + 1 \equiv p+1 (\bmod\ p^2)$. Then this integer has a prime divisor $q$ such that $q\not\equiv 1 \pmod{p^2}$ and $q \mid p^p-1$. Suppose that for some ${n\in \mathbb{N}}$ integer $q$ divides $n^p-p$. Then $$n^p\equiv p (\bmod\ q) \quad \Rightarrow \quad n^{p^2}\equiv p^p\equiv 1 (\bmod\ q)$$ Also since $(n, q)=1$, from Fermat's little theorem we know $n^{q-1}\equiv 1(\bmod q)$. It's clear that $q-1$ doesn't divided by $p^2$, so either $(p^2, q-1)=p$ or $(p^2, q-1)=1$. In any case $n^p\equiv 1 (\bmod\ q)$, from which $p\equiv 1(\bmod\ q)$. Thus $0\equiv p^{p-1}+\ldots + p + 1 \equiv p (\bmod\ q)$, contradiction.
| Attributes | Красива, Олімпіадна |
|---|---|
| Source | International Mathematical Olympiad |
| Year | 2003 |
| Number | 6 |
| Difficulty | 10.0 |
| Themes |