How to find remainder when $ 975^{40153}$ is divided by $14$? I still find tricky this kind of problems.
I tried to do solve it by factoring $14$ in $2*7$.
Then, with Fermat's Little Theorem, I find that:
$975^6\equiv 1\pmod 7$
$975^1\equiv 1\pmod 2$
How can I proceed frome here?
 A: $\color\red{975^{3}}\equiv\color\red{1}\pmod{14}\implies$
$975^{40153}\equiv975^{3\cdot13384+1}\equiv(\color\red{975^{3}})^{13384}\cdot975^{1}\equiv\color\red{1}^{13384}\cdot975^{1}\equiv975\equiv9\pmod{14}$
A: $\varphi (14)=6$ and $gcd(975, 14)=1$. From Euler's theorem, we get $975^6 \equiv 1 (\mod 14)$. Now $975^{40153}\equiv 975^{6692*6+1}\equiv975\equiv9 (\mod 14)$
A: Then, $975^{40153}=975^{6692\times6+1}=(975^6)^{6922}\times975\equiv(-1)^{6922}\times975=975\equiv2\mbox{ (mod 7)}$.
Also, $975^{40153}=(975^1)^{40153}\equiv(1)^{40153}=1\mbox{ (mod 2)}$.
Using the Chinese Remainder Theorem (AKA trial and error), you would find the numbers from $0$ to $13$ which $\equiv2\mbox{ (mod 7)}$, which are $2$ and $9$, and then test for $\equiv1\mbox{ (mod 2)}$, which gives us $\underline{\underline{9}}$.
A: Using Fermat's theorem in these type of questions is not a wise decision.You may use a more generalized-Euler Theorem.
According to Euler's Theorem.
$$a^{\phi n}\equiv1\pmod n$$
Where $(\phi{n})$ is the Euler Phi function.
Now,notice that,
$$975^{\phi(14)}\equiv1\pmod{14}$$
$$\implies975^6\equiv1\pmod{14}$$
$$\implies975^{40152}\equiv1\pmod{14}\space\space\space\space\space\space\space\space\space(\text{As,40152=6}\times6692)$$
$$\implies975^{40152}\times975\equiv975\pmod{14}$$
$$\implies975^{40153}\equiv9\pmod{14}\space\space\space\space\space\space\space\space\space\space (\text{As,}975\pmod{14})=9$$
Hope this helps!! 
A: $$975\equiv-5\pmod{14}\implies975^{40153}\equiv(-5)^{40153}$$
As $(-5)^3\equiv1\pmod{14}$ 
and as $4+0+1+5+3\equiv1\pmod3\implies40153\equiv1\pmod3$
$(-5)^{40153}\equiv(-5)^1\pmod{14}\equiv-5+14=?$
