Modulo

Question

What will be the remainder when $\large 6457^{76^{57}}$ is divided by $\large 23$ ?

Comments

is it 16??

---

@lokesh.....I got the last digit of divisor 1...After that how did you get 16..?

---

what do you mean by last digit of divisor?

---

 this number has last digit as 1

---

means you calculated $6457^{76^{57}}$ mod $10$ not mod 23

---

no i didnt calculated the number but i performed modulo operations

but i need the ans to cross check what i calculated

---

is it $6457^{76^{57}} or (6457)^{76^{57}}$ ?

---

Answer is 6.

---

Anirudh what  u r asking??

---

Yes, I got the same answer. Also code in python verifies the same.

Answer 1

$6457^{76^{57}}$ is evaluated as $6457^{(76^{57})}$

$6457 = 280*23 + 17$, So $6457\;mod\;23 = 17$

So, problem reduces to $17^{76^{57}}\;mod \;23$

$17^{11}\;mod23 = -1$. So, $17^{22}\;mod\;23 = (17^{11}\;mod\;23)*(17^{11}\;mod\;23) = -1*-1 = 1$

So, If we are able to reduce above problem to $17^{22n + k} \;mod\;23$, then we need to find $17^k \;mod\;23$ to get our answer.

So, let's see $\color{blue}{76^{57}\;mod\;22 = (66+10)^{57}\;mod\;22 = 10^{57}\;mod\;22}$

And $10^3\;mod\;22 = 10$, So, $10^{57}\;mod\;22 = 10$

$17^{76^{57}}\;mod\;23 = 17^{22n + 10}\;mod\;23$ (remember $\color{red}{17^{22}\;mod\;23 = 1}$)

$6457^{76^{57}}\;mod\;23 = 17^{10}\;mod\;23 = 4$

Answer 2

 here we let  N=  76⁵⁷   so it will  be  ( 6457^N) /23  so it will reduce to  = (6457mod23)^N /  23   =  17^N / 23

 after my goal to find a cycle of 17 which either get 1 or -1. so lets try..

  17¹ mod 23 = 17

   17² mod 23 = 13

    17³ mod 23 =  14

      17⁴ mod 23 = 8

   17⁵ mod 23 = 21

  17⁶ mod 23 = 12

  17⁷ mod 23 = 20

  17⁸ mod 23 = 18

  17⁹ mod 23 = 7

   17¹⁰ mod 23 = 4

  17¹¹ mod 23 = 22    so here remainder is -1  so its cycle of 11.

  so that    N/11   =    76⁵⁷ /11 =   (- 1)⁵⁷/11  =  - 1 ( remainder is 10  ) so that its 10 th term of cycle   =  4 is answer.

  

Comments

@hradesh can u please give any reference to this topic? what is this particular method called?

---

@anusha these question commanly ask in CAT ..u refer you tube  CAT lecture number system