What mistake am I making when trying to apply Fermat's little theorem?

This is a problem from Discrete Mathematics and its Applications

This is Fermat's little theorem from https://www.youtube.com/watch?v=w0ZQvZLx2KA,

Here is my work so far

First 41 is prime and $41\not\mid23$

So $23^{40}\equiv1\pmod {41}$

From my observation that $1002/40 = 25$, I rooted both sides of $23^{40}\equiv1$ by $25$

(allowed to so by Congruence product rule, Divisibility for 7)
Here is what am I left with $$23^{1000}\equiv1\pmod {41}$$ Then I used the fact that $1002 \mod 40 = 2$ and the congruence product rule to get
$$23^{1002}\equiv 23^2\pmod {41}$$ Then with this property from my book

I know that $23^{1002}\mod 41 = 23^2 \mod 41$. $23^2\mod 41$ from my calculator is $18$ so that be my final answer as well.
But when I checked my answer on http://www.mathcelebrity.com/modexp.php?num=+23%5E1002+mod+41&pl=Modular+Exponentiation, the correct answer was 37.

Does anyone know I did wrong -either arithmetically or applying theorems?

• Your calculator misled you when you found $23^2(\mod41)$ Commented Feb 14, 2015 at 19:38
• Actually I think I mislead myself haha Commented Feb 14, 2015 at 20:04

Hint $\ {\rm mod}\ 41\!:\,\ 23^2 \equiv (-2\cdot9)^2 \equiv\, 4(\overbrace{-1}^{\large81}) \equiv 37.\$ Trust your brain more than your calculator.
• How did you get 23$^2$≡(−2⋅9)$^2$? Commented Feb 14, 2015 at 20:05
• @com ${\rm mod}\ 41\!:\ 23\equiv 23-41\equiv -18.\$ Generally modular arithmetic is easier with least magnitude reps, here $\,|{-}18| < 23.\$ Recall also the use of $\,-1\,$ vs. $\,m\!-\!1\pmod m\ \$ Commented Feb 14, 2015 at 20:06
$$23^2 \equiv (20+3)^2=20*20+20*2*3+9=\\ = 40*10+40*3+9 \equiv -10-3+9=-4=37 \pmod{41}$$