Prove/Disprove

$$n|(a^n-a)~~~\text{and} ~~n\nmid(a^k-a) \text{ for } k \lt n \implies \text{ n is a prime }$$

assume all variables are natural numbers

Question

Prove/Disprove

$$n|(a^n-a)~~~\text{and} ~~n\nmid(a^k-a) \text{ for } k \lt n  \implies \text{ n is a prime }$$

assume all variables are natural numbers

ganeshie8 · Answer

$n|(a^n-a) \implies   n|(a^{n-1}-1)$ when $\gcd(a,n) = 1$
from the hypothesis we have $n-1$ is the smallest such power

from euler theorem we have $n | (a^{\phi(n)}-1)$

combining both we can say $(n-1)|\phi(n)$

ganeshie8 · Answer

but thats possible only if $n$ is a prme $\blacksquare $

mathmath333 · Answer

i was thinking of fermat liar numbers

ganeshie8 · Answer

it is related to that haha

ganeshie8 · Answer

absolute pseudo prime is a composite number that satisfies $n | (a^n-a)$ for all $a$