Question

What is the remainder of (32^31^301) when it is divided by 97?

Answer 1

8 can be the remainder

Answer 2

Answer:

11

Step-by-step explanation:

⇒ Divide 32² by 97. We get remainder 54. So,

$\mapsto 32^2 \equiv 54\pmod{97}$

⇒ Square them.

$\mapsto (32^2)^2\equiv 54^2\pmod{97} \\ \\ \mapsto 32^4\equiv 2916\pmod{97} \\ \\ \mapsto 32^4\equiv 6\pmod{97} \ \ \ \ \ \ \ \ \ \ [\because\ 2916\equiv6\pmod{97}]$

⇒ Take the cubes.

$\mapsto\ (32^4)^3\equiv 6^3\pmod{97} \\ \\ \mapsto\ 32^{12} \equiv 216\pmod{97} \\ \\ \mapsto\ 32^{12} \equiv 22\pmod{97}\ \ \ \ \ \ \ \ \ \ [\because\ 216\equiv 22\pmod{97}]$

⇒ Again squaring and then squaring...... we get 1.

$\mapsto\ (32^{12})^2 \equiv 22^2\pmod{97} \\ \\ \mapsto\ 32^{24}\equiv484\pmod{97} \\ \\ \mapsto\ 32^{24}\equiv-1\pmod{97}\ \ \ \ \ \ \ \ \ \ [\because\ 484\equiv-1\pmod{97}] \\ \\ \\ \mapsto\ (32^{24})^2\equiv(-1)^2\pmod{97} \\ \\ \mapsto\ 32^{48}\equiv1\pmod{97}$

⇒ Now we've to find the remainder on dividing 31³⁰¹ by 48.

$\mapsto\ 31\equiv-17\pmod{48} \\ \\ \mapsto\ 31^2\equiv(-17)^2\pmod{48} \\ \\ \mapsto\ 31^2\equiv289\pmod{48} \\ \\ \mapsto\ 31^2\equiv1\pmod{48}\ \ \ \ \ \ \ \ \ \ [\because\ 289\equiv1\pmod{48}] \\ \\ \mapsto\ (31^2)^{150}=(1)^{150}\pmod{48} \\ \\ \mapsto\ 31^{300}=1\pmod{48} \\ \\ \mapsto\ 31^{300} \times 31\equiv1 \times 31\pmod{48} \\ \\ \mapsto\ 31^{301}\equiv31\pmod{48}$

⇒ The remainder is 31. So we have to find the remainder on dividing 32³¹ by 97.

$From\ \ 32^4\equiv6\pmod{97} \\ \\ \mapsto\ 32^4 \times 32\equiv6 \times 32\pmod{97} \\ \\ \mapsto\ 32^5\equiv192\pmod{97} \\ \\ \mapsto\ 32^5\equiv-2\pmod{97} \ \ \ \ \ \ \ \ \ \ [192\equiv-2\pmod{97}] \\ \\ \mapsto\ (32^5)^6\equiv(-2)^6\pmod{97} \\ \\ \mapsto\ 32^{30}\equiv64\pmod{97} \\ \\ \mapsto\ 32^{30} \times 32\equiv64 \times 32\pmod{97} \\ \\ \mapsto\ 32^{31} \equiv2048\pmod{97} \\ \\ \mapsto\ 32^{31}\equiv11\pmod{97}$

⇒ The remainder is 11 here. Let 31³⁰¹ = 48x + 31.

$\mapsto\ 32^{31^{301}}\equiv32^{48x+31}\pmod{97} \\ \\ \mapsto\ 32^{31^{301}}\equiv32^{48x}\times 32^{31}\pmod{97} \\ \\ \mapsto\ 32^{31^{301}}\equiv(32^{48})^x \times 11\pmod{97}\ \ \ \ \ \ \ \ \ \ [\because\ 32^{31}\equiv11\pmod{97}] \\ \\ \mapsto\ 32^{31^{301}}\equiv1^x \times 11\pmod{97}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [\because\ 32^{48}\equiv1\mod{97}] \\ \\ \mapsto\ 32^{31^{301}}\equiv1 \times11\pmod{97}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ [1^n=1]$

$\mapsto\ 32^{31^{301}}\equiv\bold{11}\pmod{97}$

So the answer is 11.