Question

Calculate 40^13 (mod85)

Answer 1

@ganeshie8 "mod" <----- :D

Answer 2

lol

Answer 3

mm so you guys are covering modular exponentiation?

Answer 4

there are two key modular arithmetic laws that will help you here, namely
ab mod c is congruent to a mod c * b mod c

Answer 5

or maybe that was the only law lol

Answer 6

^_^ idk i just saw him doing "mod" problems so i just tagged .....

Answer 7

@danyboy9169 are you there?

Answer 8

yes, just few hrs old on Open Study so trying to understand how this works

Answer 9

its easy let me post a solution

Answer 10

\(\large \begin{align} \color{black}{40^{13} \pmod {85}\hspace{.33em}\\~\\
=40\cdot 40^{12} \pmod {5\times 17}\hspace{.33em}\\~\\
=8\cdot 40^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (17\times 2+6)^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (6)^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (6^2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (36)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (17\times 2+2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (2^2)^{3} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (4)^{3} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (4)^{2} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot 16 \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (17-1) \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=32\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=(17\times 2-2)\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=(-2)\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=2 \pmod { 17}\hspace{.33em}\\~\\
\normalsize \text{we have calculated mod 17 but the question asks mod 85 , so} \hspace{.33em}\\~\\
\normalsize \text{but 17*5=85} \hspace{.33em}\\~\\
=2\times 5 \pmod { 17\times 5}\hspace{.33em}\\~\\
=10 \pmod { 85}\hspace{.33em}\\~\\
}\end{align}\)

Answer 11

ask for doubt if any in a step or 2

Answer 12

TBH I rather multiply 40 then reduce it and do it 13 times than do it your way. The steps required are too complex for me.

Answer 13

I reread it and it is much better than when I first read it lol.

Answer 14

\[8\times 40^{12}\equiv 2 \pmod{17} \implies 5\times 8\times 40^{12} \equiv 5\times 2 \pmod{5\times 17} \]

Answer 15

Something seems wrong though. I don't think \(2\pmod {17}=10\pmod {85}\). For example, \(19\equiv2\pmod {17}\) but clearly \(19\neq10\pmod{85}\)

Answer 16

x/5 = 2 (mod 17)

multiply 5 through out

x = 10 (mod 85)

Answer 17

\[2 \pmod{17} \ne 10 \pmod{85}\]

Answer 18

you're right abot that but i dont see anyone saying they are eqal in this thread ?

Answer 19

The last five lines of mathmath333 proof.

Answer 20

I see... he meant this i think :

we want to find the remainder
\(x\equiv 40^{13} \pmod{85}\)

divide through out by 5
\(x/5\equiv 8\cdot 40^{12} \pmod{17}\)
\(\cdots\)
\(x/5\equiv 2 \pmod{17}\)

multiply by 5 through out
\(x\equiv 10 \pmod{85}\)

Answer 21

he just divided 5 in the start so that he can work easily in a smaller moduli

in the end he miltiplied everything by 5 to keep things same

looks good to me :)

Answer 22

If \(x\equiv a\pmod n\), does \(bx\equiv ba \pmod {bn}\)?

Answer 23

yes lets prove it

Answer 24

\(\large \begin{align} \color{black}{40^{13} \pmod {85}\hspace{.33em}\\~\\
=40\cdot 40^{12} \pmod {\color{red}{5}\times 17}\hspace{.33em}\\~\\
=8\cdot 40^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (17\times 2+6)^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (6)^{12} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (6^2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (36)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (17\times 2+2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (2)^{6} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (2^2)^{3} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot (4)^{3} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (4)^{2} \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot 16 \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (17-1) \pmod { 17}\hspace{.33em}\\~\\
=8\cdot4\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=32\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=(17\times 2-2)\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=(-2)\cdot (-1) \pmod { 17}\hspace{.33em}\\~\\
=2 \pmod { 17}\hspace{.33em}\\~\\
\normalsize \text{we have calculated mod 17 but the question asks mod 85 , so} \hspace{.33em}\\~\\
\normalsize \text{but 17*5=85} \hspace{.33em}\\~\\
=2\times 5 \pmod { 17\times \color{red}{5}}\hspace{.33em}\\~\\
=10 \pmod { 85}\hspace{.33em}\\~\\
}\end{align}\)

Answer 25

\(x\equiv a \pmod{n} \implies n|(x-a) \implies bn|b(x-a)~~ \implies b(x-a) \equiv 0 \pmod{bn}\)

Answer 26

first i removed 5 and and then gave it back to make life easy

Answer 27

can also use the chineese remainder theorem here
but that is not need since i can cancel 5

Answer 28

Exactly !

Answer 29

proof from wolfram

http://www.wolframalpha.com/input/?i=40%5E%2813%29+mod+85%3D

Answer 30

the actual calculation is very short , but i extended it step by step to understand comprehensively

Answer 31

\(19\equiv 2 \pmod {17}\)

and

\(19*5=95\equiv 2\times 5\equiv 10 \pmod {85}\)

Answer 32

Wow!! you guys are amazing.. I am new to this study group, am amazed the responses I have had. gr!8. - thanks

We can use the rules of exponents to write 40^13 (mod 85) as (40^2)^6 (mod 85. )

Since 40^2 = 1600 = equiv 70 (mod 85), we can write our expression as 70^6 .40(mod 85)

Applying rules of exponents again, we have (70^2)^3* 40 mod 85.

With 70^2 = 4900 = equiv 55(mod 85), our expression is now 55^3 * 40 (mod 85)

We can also rewrite this as 55^2 * 55 * 40 (mod 85)

With 55^2 = 3025 =equiv 50 (mod 85) and 55 * 40 = 2200 =equiv 75 (mod 85), we can simplify the expression again to 50 * 75 (mod 85)

We calculate 50* 75 = 3750=equiv 10 (mod 85.)

Ans: 10

Answer 33

ur applying \(\mod 85 \) which is also good, but \(\mod 17 \) is definitely easy that \(\mod 85\)

Answer 34

@mathmath333 I agree and thank all guys!