How do I solve $(68!+68^{86} ) \mathrm{ \ mod \ }75$? I feel like it's really easy and i'm just misunderstanding something. It's obvious that I need to use Wilson' and Fermat's theorems:

*

*$(p-1)!≡-1\mathrm{ \ mod \ }p$

*$a^{p-1}≡1\mathrm{ \ mod \ }p$ if $p$ does not divide $a$.

i figured i might divide $75$ (since it's not prime) into $5^2$ and $3$ and get the system:
$68!\mathrm{ \ mod \ }3+68^{86}\mathrm{ \ mod \ }3$
$68!\mathrm{ \ mod \ }5+68^{86}\mathrm{ \ mod \ }5$
Am i going in the right direction?
 A: There are several approaches and your approach seems essentially fine, except that knowing $68^{86}
\bmod 3$ and $68^{86}
\bmod 5$ is not sufficient to obtain $68^{86}
\bmod 75$. Instead, you need $68^{86}
\bmod 3$ and $68^{86}
\bmod 25$.
Fermat's theorem says $68^{4}\equiv 1 \pmod 5$ , but you need more precise evaluation. You need to calculate $68^{4} \equiv 5a+1 \pmod {25}$ to find $68^{4k} \equiv 5ak+1 \pmod {25}$ using binomial expansion.
In this case $68^{4} \equiv 1 \pmod {25}$, so it is rather easy.
A: Note that $3\mid 68! $ and $ 25\mid 68! $. So $68!\equiv 0$(mod 75).Now for the second part Fermat's little theorem is of no use as 75 is not a prime,here you need to use the Euler's totient function.You can find it here
.
We have $\phi (75)=(25-5)(3-2)=40$
Now by Euler's formula $68^{\phi (75)}=68^{40}\equiv 1 $(mod 75) $\Rightarrow 68^{80}\equiv 1$(mod 75).
Also $$68\equiv -7(mod 75)$$
$$\Rightarrow 68^6\equiv 7^6(mod75)$$
$$\Rightarrow 68^6\equiv 343^2\equiv 43^2\equiv 1849\equiv 49(mod 75)$$
$$\Rightarrow 68^{86}\equiv 68^{80}\times 68^6\equiv 49(mod 75)$$
So the whole thing is equivalent to 49 mod 75
