What is the positive remainder when the expression 12^{77} - 26^{77} is divided by 19? — State PSC Exam

What is the positive remainder when the expression $12^{77} - 26^{77}$ is divided by $19$ ?

A
9
16Answer
C
5
D
3

Answer

The correct positive remainder is 16.

By reducing the bases modulo 19, we get

12 \equiv -7

and

26 \equiv 7

. The expression transforms to

(-7)^{77} - 7^{77}

, which simplifies to

-2 \times 7^{77}

since the exponent is odd. Finding the cycle of

7 \pmod{19}

reveals that

7^3 \equiv 1 \pmod{19}

. Because

77 = 3 \times 25 + 2

, we have

7^{77} \equiv 7^2 \equiv 11 \pmod{19}

. Finally,

-2 \times 11 = -22

, and adjusting this to a positive remainder by adding 38 (a multiple of 19) gives 16.

Step-by-Step Solution

Express the bases of the exponents in terms of their remainders when divided by 19.

12 \equiv -7 \pmod{19}

and

26 \equiv 7 \pmod{19}

Converting large bases to smaller equivalent modular values (especially symmetric ones) simplifies the exponentiation.

Substitute the simplified bases back into the original expression.

12^{77} - 26^{77} \equiv (-7)^{77} - 7^{77} \pmod{19}

This reduces the problem to calculating powers of 7.

Simplify the expression by handling the negative sign.

Since 77 is an odd number,

(-7)^{77} = -(7^{77})

. The expression becomes

-(7^{77}) - 7^{77} = -2 \times 7^{77} \pmod{19}

Factoring out

7^{77}

isolates the exponentiation part of the problem.

Determine the remainder of

7^{77}

divided by 19.

Using modulo operations,

7^1 = 7

7^2 = 49 \equiv 11

7^3 = 7 \times 11 = 77 \equiv 1 \pmod{19}

. Since

7^3 \equiv 1

, the cyclicity is 3. We divide the exponent by 3:

77 = 3 \times 25 + 2

. Thus,

7^{77} \equiv 7^2 \equiv 11 \pmod{19}

Finding the cycle of powers (where the remainder is 1) drastically reduces large exponents.

Multiply by the coefficient and convert to a positive remainder.

-2 \times 11 = -22

. To find the positive remainder, add multiples of 19:

-22 + 19 \times 2 = -22 + 38 = 16

Remainders must be positive integers strictly less than the divisor.

Key Concept

Modular Arithmetic and Fermat's Little Theorem

Alternative Method

Instead of finding the specific cyclicity of 3, Fermat's Little Theorem states that

a^{18} \equiv 1 \pmod{19}

. Dividing 77 by 18 gives a remainder of 5. Calculating

7^5 \pmod{19}

will also yield 11, leading to the same final answer.

Estimated Time:1m 30s

Question

Answer

Step-by-Step Solution

Key Concept

Common Mistakes

Alternative Method

Topics

More questions from this topic