I could use that $17^{2} \equiv 10 (\mod 31)$ and express $17^{23}$ as $17^{16}.17^{4}.17^{3} = (((17^2)^2)^2)^2.(17^2)^2.17^2.17$ and take advantage of the fact that I can more easily work with powers of ten ($17^2 \equiv 10 (\mod 31), (17^2)^2 \equiv 100 (\mod 31) \equiv 7 (\mod 31)$, etc.). While this makes the computation easier, I'm thinking there might be a better way to do this.
$\endgroup$ 16 Answers
$\begingroup$$17^2\equiv10\pmod{31}$
$17^4 \equiv 7\pmod{31}$
$17^3 \equiv 170\pmod{31}\equiv15\pmod{31}$
$17^7=17^3\times17^4\equiv15\times7\pmod{31}\equiv12\pmod{31}$
${(17^7)}^3=17^{21}\equiv23\pmod{31}$
$17^{23}=17^{21}\times17^2\equiv230\pmod{31}\equiv13\pmod{31}$
$\endgroup$ 1 $\begingroup$We can do away with manipulating the powers of $17$ as follows
Observe that $17\equiv-14\pmod{31}$
$\displaystyle\implies 17^{23}\equiv(-14)^{23}\equiv-14^{23}\pmod{31}$
Now, $7^2=49\equiv18\pmod{31}, 7^3\equiv18\cdot7\equiv2\pmod{31}$
$\displaystyle\implies14^{23}=2^{23}\cdot7^{23}=2^{23}(7^3)^7\cdot7^2\equiv2^{23}\cdot2^7\cdot7^2\equiv2^{30}\cdot49\pmod{31}$
Using Fermat's Little Theorem, $2^{30}\equiv1\pmod{31}$
Alternatively, $2^5=32\equiv1\pmod{31}\implies 2^{30}=(2^5)^6\equiv1^6\pmod{31}\equiv1$
So, $\displaystyle-14^{23}\equiv-49\pmod{31}\equiv13$
$\endgroup$ 3 $\begingroup$Modulo $31$ we have:
$$17^1 \equiv 17$$ $$17^2 \equiv 10 \text{ (because $289$ mod $31$ is $10$)}$$ $$17^4 \equiv (10)^2 \equiv 7 \text{ (because $100$ mod $31$ is $7$)}$$ $$17^8 \equiv (7)^2 \equiv 18 \text{ (Similar)}$$ $$17^{16} \equiv (18)^2 \equiv 14 $$
And $17^{23} \equiv 17^{16} \cdot 17^4 \cdot 17^2 \cdot 17^1$.
So $17^{23} \equiv 14 \cdot 7 \cdot 10 \cdot 17$. We note that $7\cdot 10 = 70 \equiv 8 \mod 31$, so $17^{23} \equiv 14 \cdot 8 \cdot 17$, and $8\cdot 17 = 136 \equiv 12 \mod 31$, so $17^{23} \equiv 14 \cdot 12 \mod 31$, and $14 \cdot 12 = 168 \equiv 13 \mod 31$.
$\endgroup$ $\begingroup$It's possible to do this in 6 multiplications. And the first couple multiplications appear to be the hardest.
$$17^2=289\equiv10\pmod{31}$$ $$17^3=17^2\times17\equiv170\equiv15\pmod{31}$$ $$17^5=17^3\times17^2\equiv150\equiv-5\pmod{31}$$ $$17^{10}=(17^5)^2\equiv25\equiv-6\pmod{31}$$ $$17^{20}=(17^{10})^2\equiv36\equiv5\pmod{31}$$ $$17^{23}=17^{20}\times17^3\equiv75\equiv13\pmod{31}$$
$\endgroup$ $\begingroup$Note that $17\equiv 3/2 \pmod {31}$. We can then calculate this.
$2^5 = 1$, so $2^{23}=8$.
$3^3 = -4$, so $3^6 = 16$. We then have $3^{24} = 16^4 = 2$, and dividing through by $8$, we get $8$. Divide this by $3$ to get $31+8 = 39$, divide by 3 to get $13$.
$\endgroup$ $\begingroup$Firstly sorry for my english :( It's easy to see that 〖2〗^5=〖5〗^3=1(mod 31) And 〖3〗^5=-5(mod 31). 〖17〗^23=〖48〗^23=〖3.16〗^23=〖3〗^23.〖〖2〗^4〗^23=〖3〗^23.〖2〗^92=〖3〗^23.〖〖2〗^5〗^18.4=〖3〗^23.〖1〗^18.(-27)=〖3〗^23.〖-3〗^3=-〖3〗^26=-〖〖3〗^5〗^5.3=-〖-5〗^5.3=〖5〗^3.25.3=1.25.3=75=13(mod31). Maximum we calculated 32,125,243 and get answer.
$\endgroup$
