Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
This question has no direct link to cryptography. It would be like tagging a question about wheels with "bicycle", "motorcycle", "car", "truck", "plane", "scooter", ... –  Thomas Oct 30 '13 at 8:12

6 Answers 6

up vote 10 down vote accepted

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

share|improve this answer
    
@FrenzYDT. Thanks for the edit. –  Ramanujan Oct 30 '13 at 4:34

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$

share|improve this answer
    
@pldimitrov, how about this? –  lab bhattacharjee Oct 30 '13 at 5:14
    
Small mistake on the very last calculation. –  Mike Oct 30 '13 at 6:53
    
@Mike, thanks for your observation –  lab bhattacharjee Oct 30 '13 at 6:55

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

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.