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
16Cevap
C
5
D
3

Cevap

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.

Adım Adım Çözüm

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.

Anahtar Kavram

Modular Arithmetic and Fermat's Little Theorem

Alternatif Yöntem

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.

Tahmini Süre:1m 30s

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Alternatif Yöntem

Konular

Bu konudan daha fazla soru