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

If $n$ is a prime, then according to Fermat's Little Theorem, for every integer $1<a<n$, $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?


By Chinese remainder theorem, there exists $1<a<n$ 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy