When the integer N = 4^{43} + 9^{43} is divided by 7, what is the remainder? — GMAT

When the integer $N = 4^{43} + 9^{43}$ is divided by $7$ , what is the remainder?

Answer: 6

The remainder when

N = 4^{43} + 9^{43}

is divided by

7

6

Reducing

9 \pmod 7

yields

2

, allowing

N

to be expressed as

2^{86} + 2^{43} \pmod 7

. The powers of

2 \pmod 7

repeat every 3 powers

(2, 4, 1)

. Reducing the exponents

86

and

43

modulo 3 gives remainders of

2

and

1

, corresponding to values of

4

and

2

. Their sum

4 + 2 = 6

is the final remainder.

Simplify the base modulo 7 and express in powers of 2

9 \equiv 2 \pmod 7

, so

N = 4^{43} + 9^{43} \equiv 2^{86} + 2^{43} \pmod 7

Reducing bases modulo 7 simplifies calculating large exponents.

Determine the remainder cyclicity of powers of 2 modulo 7

The cycle length is 3 with pattern

(2, 4, 1)

, because

2^1 \equiv 2

2^2 \equiv 4

, and

2^3 \equiv 1 \pmod 7

Powers of integers modulo a divisor repeat periodically.

Evaluate each term using the exponent modulo the cycle length

86 \equiv 2 \pmod 3 \implies 2^{86} \equiv 2^2 = 4 \pmod 7

, and

43 \equiv 1 \pmod 3 \implies 2^{43} \equiv 2^1 = 2 \pmod 7

The position in the cyclicity sequence is dictated by the exponent modulo the period length.

Add the individual remainders

4 + 2 = 6 \pmod 7

The remainder of a sum equals the sum of the individual remainders.

Modular arithmetic cyclicity of powers and addition of remainders

Question