$n^{n-1}-1$ is a multiple of $k$

Question

Find the number of integers $k$ with $2 \leq k \leq 1000$ satisfying the following property:

• For every positive integer $n$ relatively prime to $k$, $n^{n-1}-1$ is a multiple of $k$.

Let $k = 2^{\alpha_1}3^{\alpha_2} \cdots p_n^{\alpha_n}$ be the prime decomposition of $k$. Then by the Chinese Remainder Theorem $n^{n-1} \equiv 1 \pmod{k}$ for all $n$ such that $\gcd(n,k) = 1$ if and only if\begin{align*}n^{n-1} &\equiv 1 \pmod{2^{\alpha_1}}\\n^{n-1} &\equiv 1 \pmod{3^{\alpha_2}}\\&\vdots\\n^{n-1} &\equiv 1 \pmod{p_n^{\alpha_n}}\end{align*} for all $n$ such that $\gcd(n,k) = 1$. How can we continue?

Answer 1

If $\gcd(n,k)=1$ then $\gcd(n+k,k)=1$. So:

$$1\equiv (n+k)^{n+k-1}\equiv n^{n+k-1}=n^{n-1}n^k\pmod{k}$$

and hence $n^k\equiv 1\pmod{k}$ for all $n$ relatively prime to $k$.

Now if $0<n<k$ with $\gcd(n,k)=1$, then:

$$1\equiv (k-n)^{k-n-1} \equiv (-1)^{k-n-1} n^kn^{-(n-1)}n^{-2}\pmod{k}$$

But $n^k\equiv n^{-(n-1)}\equiv 1\pmod{k}$ so you have $$n^2\equiv (-1)^{k-n-1}\pmod{k}$$

That should reduce the problem greatly for case-by-case analysis. The only prime powers where every relatively prime square is $\pm 1$ are $2,4,8,3,5$. And $k$ has to be a product of these.

We know $k$ must be even, since otherwise $(2,k)=1$ and $k$ must divide $2^{2-1}-1=1$, we are most of the way.

When $k$ is even, we get that $n$ is odd, and hence $(-1)^{k-n-1}=1$ so we need $n^2\equiv 1\pmod{k}$ for all relevant $n$. But that means that $5$ can't be a factor.

This leaves us with $k=2,4,8,6,12,24$. We can quickly check each case.

---

Okay, more verbosely, you need to prove this lemma:

If $p^{a}\mid k$ and there is some $n_0$ such that $\gcd(n_0,p^a)=1$ and $n_0^2\not\equiv 1\pmod{p^a}$, then there is an $n$ with $\gcd(n,k)\neq 1$ such that $n^{2}\not\equiv 1\pmod{k}$.

Essentially, this is because you can write $k=p^bk'$ for $\gcd(k',p)=1$ and then solve the Chinese remainder question:

$$n\equiv n_0\pmod{p^b}\\ n\equiv 1\pmod{k'}$$

This gives you an $n$ with $n^2\not\equiv -1\pmod{p^b}$ so $n^2\not\equiv -1\pmod{k}$.