$a^{(n-1)} + (n-1)!\equiv 0\pmod n $ iff $n$ is prime I am trying to prove that, given $a, n \in \mathbb{N}$, $n \geq2$ and $gcd(a,n) =1$
$$a^{n-1} + (n-1)!\equiv 0\pmod n $$ iff $n$ is prime.
I did one direction:
"$\Leftarrow$": Let n be a prime number.
Then, since $a$ and $n$ are coprime, we have that $a^{n-1}\equiv 1\pmod n$.
 Morevoer, by Wilson's theorem, $ (n-1)!\equiv -1\pmod n$.
Therefore, $$a^{n-1} + (n-1)!\equiv 0\pmod n $$
For the other direction, I thought I could prove that $n$ divides $(n-1)! +1$ and conclude again using Wilson's theorem, but it doesn't seem the right approach. Any help?
 A: Suppose that
$$
a^{n-1} + (n-1)! \equiv 0 \mod n
$$
Now assume first that $n$ is composite (not prime) and not a power of one single prime, hence there are $2$ factors $f_1\neq f_2$ s.t. $f_1\cdot f_2$ and $1 < f_1,f_2 < n$. However as $f_1,f_2\leq n-1$ they are both divisors of $(n-1)!$. Together with $f_1\cdot f_2=n$ and $f_1\neq f_2$ we can conclude that $n | (n-1)!$, thus
$$
(n-1)! \equiv 0 \mod n
$$
Inserting that into the first equation yields
$$a^{n-1} + (n-1)! \equiv a^{n-1} \equiv 0 \mod n$$
But we have $gcd(a,n)=1$ so $a^{n-1}$ will never be divisible by $n$! Contradiction!
What happens if $n$ is the power of one single prime, $n=p^k$? If $k > 2$ we can use the factorization $p^k = p \cdot p^{k-1}$ with $p\neq p^{k-1}$ and using $f_1=p,f_2=p^{k-1}$ we can use above formula. What happens if $k=2$?
In that case we can find the two factors $p$ and $2p$ (for $p>2$) which are both $<p^2$ and not equal. Thus we get that $2p^2 | (n-1)!$ which also means that $p^2|(n-1)!$, hence $(n-1)!\equiv 0 \mod p^2$.
So for $n>4$ arbitrary and composite we get $(n-1)!\equiv 0 \mod n$ which yields a contradiction. This means that $n$ must be a prime number if above modulo equivalence is true.
If $n=2$ or $n=3$ we already have prime numbers and there is nothing to show.
The last case is $n=4$. We then have $(n-1)! = 6 \equiv 2 \mod 4$ which yields that
$a^3 + 2 \equiv 0 \mod 4$.
Let's take a look at all possible values $\text{mod } 4$:
$$
0^3 \equiv 0 \mod 4 \\
1^3 \equiv 1 \mod 4 \\
2^3 \equiv 0 \mod 4 \\
3^3 \equiv 3 \mod 4
$$
We can see that we never get a value $\equiv \pm 2$, so we always have $a^3+2 \not\equiv 0 \mod 4$ which does work with our hypothesis as $n=4$ is not a prime.
