# Find every positive integer $n>1$ such that there aren't any integers $a$ ($1<a<n$) so that $n|a^n-1$

Find every positive integer $$n>1$$ such that there aren't any integers $$a$$ ($$1) so that $$n|a^n-1$$

If $$n$$ is a prime, then according to Fermat's Little Theorem, for every integer $$1, $$n|a^{n}-a$$, so every prime number satisfy the question.

If $$n$$ has a divisor which is also a square number, then there exist a prime number $$p$$ such that $$v_p(n)>1$$, so $$gcd(n,\phi(n))>1$$. Thus from Is it true that there is always an integer $$a$$ such that $$n|a^n-1$$ , there exists $$a$$ so that $$n|a^n-1$$.

However if $$n=p_1p_2...p_k$$, with $$k>1$$ and $$p_1,p_2,...,p_k$$ are distinct prime numbers, I cannot find any number that satisfy the problem. How can I progress?

## 1 Answer

By Chinese remainder theorem, there exists $$1 with $$n\mid a^n-1$$ ($$n$$ is square-free) if and only if one of the prime divisor $$p$$ of $$n$$ have nontrivial solution to $$a^n\equiv 1\pmod p$$. Since $$\mathbb{F}_p^\times$$ is cyclic, this means $$1\neq\gcd(n,p-1)=\gcd(n/p,p-1)$$.

Note that this condition is equivalent to $$\gcd(n,\phi(n))>1$$: if $$p$$ is a factor of $$\gcd(n,\phi(n))$$, then $$p$$ is one of the $$p_i$$'s and $$p\mid p_j-1$$ for some other $$p_j$$, giving $$\gcd(n/p_j,p_j-1)\neq 1$$. Converse is clear since $$(n/p_j)\mid n$$ and $$(p_j-1)\mid\phi(n)$$.