Consider the integer N = 4 - 2 \times 2^{68} + 7 \times 14^{85}. If N is divided by 13, wh… — State PSC Exam

Consider the integer $N = 4 - 2 \times 2^{68} + 7 \times 14^{85}$ . If $N$ is divided by $13$ , which of the following represents the correct remainder?

6Cevap
B
7
C
5
D
9

Cevap

The correct remainder is 6.

By applying Fermat's Little Theorem,

2^{68} \equiv 2^8 \equiv 9 \pmod{13}

, and clearly

14^{85} \equiv 1^{85} \equiv 1 \pmod{13}

. Substituting these values gives the expression

4 - 2(9) + 7(1) = 4 - 18 + 7 = -7

. To find the valid positive remainder, we add the divisor 13 to the negative result, yielding

-7 + 13 = 6

Adım Adım Çözüm

Simplify the term

14^{85} \pmod{13}

Since

14 \equiv 1 \pmod{13}

, any power of 14 will also be congruent to

1^{85} = 1

Simplify the term

2^{68} \pmod{13}

using Fermat's Little Theorem

Fermat's theorem states

a^{12} \equiv 1 \pmod{13}

. Dividing 68 by 12 gives a quotient of 5 and a remainder of 8. Thus,

2^{68} \equiv 2^8 \pmod{13}

. Since

2^8 = 256

, and

256 = 13 \times 19 + 9

, the value is 9.

Substitute the simplified modulo values back into the original expression

4 - 2(9) + 7(1) \pmod{13}

Replacing the large exponent terms with their modulo 13 equivalents allows for simple arithmetic evaluation.

Evaluate the simplified arithmetic expression from left to right

-7

Following the correct order of operations:

4 - 18 + 7 = -14 + 7 = -7

Convert the negative result into a valid positive remainder

Remainders must be non-negative. Add the divisor (13) to the negative result:

-7 + 13 = 6

Anahtar Kavram

Modular Arithmetic, Fermat's Little Theorem, and Negative Remainders

Soru

Cevap

Adım Adım Çözüm

Anahtar Kavram

Sık Yapılan Hatalar

Konular

Bu konudan daha fazla soru