Question

What is the remainder when x^y is divided by z , where x = 32, y = (32)^(32) and z = 13?

Answer 1

Given

x = 32

y = 32^32

z = 13

We have to find the remainder when x^y is divided by z.

Means, we have to find the remainder when

$32^{32^{32}}\ \ \textsf{is divided by}\ \ 13.$

We can see here that (13, 32) = 1.

Hence, according to Fermat's theorem,

$32^{12}\equiv 1\pmod{13}$

Now we have to find the remainder when y = 32^32 is divided by 12.

$\begin{aligned}&32\equiv -4\pmod{12}\\ \\ &32^2\equiv 16\pmod{12}\\ \\ \Longrightarrow\ \ &32^2\equiv 4\pmod{12}\end{aligned}$

But, since 12 = 4² - 4, we have to remember that,

$\large a^n\equiv a\pmod{a^2 - a}\ \ \normalsize \textsf{where \ \ a\ \&\ n \in \mathbb{N} }$

Thus,

$4^n\equiv 4\pmod{4^2-4}$

This implies,

$\begin{aligned}&(32^2)^n=32^{2n}\equiv 4^n\equiv 4\pmod{12}\\ \\ \Longrightarrow\ \ &32^{2\times 16}=32^{32}\equiv 4\pmod{12}\end{aligned}$

Hence 32^32 leaves remainder 4 on division by 12.

Thus, we can indicate y = 32^32 as y = 12q + 4, where q is the quotient.

Since the remainder is 4, now we have to find the remainder when 32^4 is divided by 13.

$\begin{aligned}&32\equiv -7\pmod{13}\\ \\ \Longrightarrow\ \ &32^2\equiv 49\equiv -3\pmod{13}\\ \\ \Longrightarrow\ \ &32^4\equiv 9\pmod{13}\end{aligned}$

Hence 32^4 leaves remainder 9 on division by 13.

32^32 is indicated as 12q + 4. Thus x^y = 32^32^32 becomes 32^(12q + 4).

$\begin{aligned}&32^{12q+4}\\ \\ =\ \ &32^{12q}\times 32^4\\ \\ =\ \ &(32^{12})^q\times 32^4\\ \\ \equiv\ \ &1^q\times 9\\ \\ =\ \ &1\times 9=\large \mathbf{9}\pmod{13}\end{aligned}$

Hence, x^y = 32^32^32 leaves remainder 9 on division by z = 13.