= Solution
The <Fermat-Euler theorem> states that
$$
\gcd(a,n)=1\quad\Longrightarrow\quad a^{\varphi(n)}\equiv1\pmod n.
$$
Indeed, if $r_1,\ldots,r_{\varphi(n)}$ are the reduced residue classes modulo $n$, multiplication by $a$ permutes them. Therefore
$$
\prod_i ar_i\equiv\prod_i r_i\pmod n.
$$
The product $\prod_i r_i$ is invertible modulo $n$, so cancellation gives the theorem.
Now let $p$ be prime. If $k\equiv1\pmod{p-1}$, then for $p\nmid b$, <Fermat little theorem> gives $b^{k-1}\equiv1\pmod p$, while $p\mid b$ makes $b^k\equiv b\equiv0$. Thus $b^k\equiv b$ for every integer $b$.
Conversely, assume this congruence holds for every $b$. Choose a <primitive root> $g$ modulo $p$. Then $g^{k-1}\equiv1\pmod p$. Since $g$ has order $p-1$, one has $p-1\mid k-1$. Hence
$$
\boxed{b^k\equiv b\pmod p\text{ for every }b
\iff k\equiv1\pmod{p-1}.}
$$
Back to article page
