1

I've been having trouble with this example while studying for my exams. Why is

$$2023^{2297}\equiv 20 \pmod{3953}\;?$$

Thanks so much for any help I can get!

The examples solves the answer by using $2297 = 2^{11} + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^0$

Ross Millikan
  • 374,822
Michael
  • 397

3 Answers3

3

Here is how I would approach the problem: the factorization of $3953$ is $59\times 67$ (hopefully you're allowed to use a calculator or Mathematica for this). I'd find the solutions $a$ and $b$ to $$2023^{2297}\equiv 17^{2297}\equiv 17^{35} \equiv a\bmod 59\qquad 2023^{2297}\equiv 13^{2297}\equiv 13^{53}\equiv b\bmod 67$$ (note the use of Fermat's little theorem here). Unfortunately nothing about these numbers is particularly convenient, so I'd resort to repeated squaring to figure out $a$ and $b$. Finally, I'd use the Chinese remainder theorem to combine these results into an answer modulo $3953$.

Zev Chonoles
  • 129,973
0

This is not an answer, it is just a rescue part of Zev Chonoles' factoring. I couldn't include this in the comment, as it is exceeding word-limit.

$3953$ is your number. The square root of the number is approximately $62$, so you just gotta check the PRIME numbers until $62$ to find the factors. And the rest follows.

Why this works?

If you have a number $N$, write it as

$\sqrt{N} \cdot \sqrt{N}$ , if you choose any number below $\sqrt {N}$, the other number has to be larger than $\sqrt{N}$. So, if you get numbers until $\sqrt{N}$, obviously you will have the other number larger than $\sqrt{N}$, which you don't need to check.

Inceptio
  • 7,881
0

The point of the example is to show the use of repeated squaring. Once you write $2297 = 2^{11} + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^0$ you can do $x^{2297}=x^{(2^{11} + 2^7 + 2^6 + 2^5 + 2^4 + 2^3 + 2^2 + 2^0)}=x^{2^{11}}x^{2^7}x^{2^6}x^{2^5}x^{2^4}x^{2^3}x^{2^2}x$ and you can get each of the last terms by squaring $x \ 11$ times, taking it $\pmod {3957}$ each time. Then you can multiply two of them, take it $\pmod {3957}$, multiply by the next, take it $\pmod {3957}$, and so on. You never need numbers of more than eight digits this way.

Ross Millikan
  • 374,822
  • I'm sorry, I still don't understand it. Is 2 a random number or does it have to be 2 everytime? Also I still don't understand how the answer gets to 20 mod 3957 from there. – Michael Apr 09 '13 at 22:28
  • @Michael: You could use other values than $2$. For example, if you wanted the $13$th power, you could cube and use $x^{13}=x^9x^3x$, but squaring is often convenient. The real idea is not to multiply by the first power every time, which would force you to multiply $2296$ times in this case. – Ross Millikan Apr 09 '13 at 22:33
  • @Michael: for the final calculation, we have $2023^4\equiv 2632, 2023^8 \equiv 1768, 2023^{16}=2954 \pmod {3953}$. Then we can say $2032 \cdot 2632 \equiv 3798, 3798 \cdot 1768 \equiv 2670, 2670 \cdot 2954 \equiv 945 \pmod {3953}$ and keep going until you get all the factors accounted for. This way it takes eleven squarings and eight multiplies to get your answer. – Ross Millikan Apr 09 '13 at 22:39
  • The way I solved it to get the same answer used 5 squarings by solving for 17^35= x (mod 59) since 59*67 = 3957 and using fermat's little theorem I got that 2023^35 = 2023^2297 and that 2023 = 17 mod 59. With what you did, did you have to actually calculate 2023^4? I'm confused because I thought your way would be easier. Sorry if I'm wrong. – Michael Apr 09 '13 at 22:45
  • @Michael: If I factored $3957=59*67$ I would do the problem mod $59,67$ and combine them. You are right that uses fewer squarings. I was responding to the example, trying to show how it works. If $3957$ were prime you would have to do it this way. – Ross Millikan Apr 09 '13 at 22:53
  • I see, thank you so much1 – Michael Apr 09 '13 at 23:02