Question

Find 89^(307) (mod 713).

Answer 1

You're familiar with the Chinese Remainder theorem correct?

Answer 2

hahahha not really lol

Answer 3

kinda jumped 2 chapters

Answer 4

Well we may not need it. Let's try without it first.

Answer 5

I know 307 needs to be broken up which i have :
307=1+2^1+2^4+2^5+2^8

Answer 6

First, note that \(713=23\cdot31\) so we we want a number \[x\equiv89^{307}\pmod{23}\]\[x\equiv89^{307}\pmod{31}\]The way you're doing it will also work, bu you have to deal with much larger numbers. This way will require the Chinese Remainder Theorem, but will use smaller numbers. Is the chapter subject about successive squaring/fast powering?

Answer 7

ok my book uses the way u started off

Answer 8

idk uses the method i used tooo idk i guess i can use whtvr method i want

Answer 9

Let's do it the way I started with then. Either way though, we'll have to end up breaking a number up into powers of 2.

Answer 10

i just checked how they solved a similar question in my book and they use my method but it makes no diff as long as i get the right answer

Answer 11

First, we solve \[89^{307}\equiv20^{307}\equiv20^{21}\pmod{23}\]First I reduced \(89\pmod{23}\), and by Fermat's Little Theorem, I can reduce \(307 \pmod{22}\) This is actually a very nice exponent to work with.

Note that by Fermat's Little Theorem, we have that \(a^{p-2}\equiv a^{-1}\pmod{p}\) So really we just need to find \(20^{-1}\pmod{23}\).

Answer 12

We do this by the Extended Euclidean Algorithm to get that \(20^{-1}\equiv 15 \pmod{23}\), so \(x\equiv 15\pmod{23}\).

Answer 13

Next, we have \[89^{307}\equiv 27^7\pmod{31}\]For this one, we'll have to break 7 up into powers of 2. We get \(7=2^2+2^1+2^0\), so \[27^7\equiv 27^{2^0}\cdot27^{2^1}\cdot27^{2^2}\pmod{31}\]

Answer 14

\[27^{2^0}\equiv27\pmod{31}\]\[27^{2^1}\equiv27^2\equiv(-4)^2\equiv16\pmod{31}\]\[27^{2^2}\equiv16^2\equiv8\pmod{31}\]

Answer 15

Multiply these all together, we have \[27^7\equiv27\cdot16\cdot8\pmod{31}\]\[27^7\equiv (-4)\cdot8\cdot16\equiv(-32)\cdot16\equiv(-1)\cdot16\equiv-16\equiv15\pmod{31}\]

Answer 16

Since both\[89^{307}\equiv15\pmod{23}\]and\[89^{307}\equiv15\pmod{31}\]It means that \(89^{307}\equiv15\pmod{713}\).

Answer 17

okkkkkkk i seeeeeee gotcha

Answer 18

In this case, we got lucky and didn't need to use the CRT. However, if one was congruent to 15, and the other 16, we would have to use the CRT.

Answer 19

Thanks that was awesome. I am gonna review the steps. Thank You :DDDDDDD

Answer 20

The advantage of this method, is that it's often very easy to do by hand. The hardest steps were calculating \(20^{-1}\pmod{23}\) and \(16^2\pmod{31}\).

If you want me to demonstrate it the way you were originally going for, feel free to ask.

Answer 21

hahha i wldnt make u do that. THANKS I REALLY APPRECIATE IT :DDD

Answer 22

You're welcome :)

I will also point out that if you're using very large numbers, and weren't able to factor 713, you would want to do it your way.