2
$\begingroup$

This is a problem from Discrete Mathematics and its Applications enter image description here

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

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 enter image description here

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?

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

2 Answers 2

Reset to default
2
$\begingroup$

Hint $\ {\rm mod}\ 41\!:\,\ 23^2 \equiv (-2\cdot9)^2 \equiv\, 4(\overbrace{-1}^{\large81}) \equiv 37.\ $ Trust your brain more than your calculator.

$\endgroup$
2
  • $\begingroup$ How did you get 23$^2$≡(−2⋅9)$^2$? $\endgroup$
    – committedandroider
    Feb 14, 2015 at 20:05
  • $\begingroup$ @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\ \ $ $\endgroup$
    – Bill Dubuque
    Feb 14, 2015 at 20:06
0
$\begingroup$

$$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}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .