What is the remainder when 3^{53} is divided by 7? — State PSC Exam

What is the remainder when $3^{53}$ is divided by $7$ ?

The remainder when

3^{53}

is divided by

7

5

By applying modular arithmetic rules,

3^3 = 27 \equiv -1 \pmod{7}

. Expanding

3^{53}

gives

(3^3)^{17} \times 3^2 \equiv (-1)^{17} \times 2 = -2 \pmod{7}

. Adding

7

to the negative remainder yields the standard positive remainder of

5

Express the base

3

in terms of powers close to a multiple of

7

3^3 = 27 = 7 \times 4 - 1 \equiv -1 \pmod{7}

Finding a power that yields

\pm 1 \pmod{7}

simplifies modular exponentiation.

Rewrite

3^{53}

using

3^3

3^{53} = (3^3)^{17} \times 3^2

Break down the exponent

53

3 \times 17 + 2

using laws of indices.

Evaluate the expression modulo

7

3^{53} \equiv (-1)^{17} \times 9 \equiv -1 \times 2 = -2 \pmod{7}

Since

(-1)

raised to an odd power is

-1

, and

9 \equiv 2 \pmod{7}

Convert negative remainder to positive equivalent

-2 + 7 = 5

Remainders in standard arithmetic must be non-negative integers in the range

[0, \text{divisor}-1]

Remainder Theorem and Modular Arithmetic

Question