Question

The remainder, when $7^{103}$ is divided by 23, is equal to:

• A. 6
• B. 17
• C. 9
• D. 14

Answer 1

Answer: (D)

14

Answer 2

To find the remainder when $7^{103}$ is divided by 23, we can use Fermat's Little Theorem.

Fermat's Little Theorem states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, $a^{p-1} \equiv 1 \pmod{p}$. In this case, $p = 23$, so $7^{22} \equiv 1 \pmod{23}$.

We can write $103 = 22 \times 4 + 15$, so $7^{103} = (7^{22})^4 \times 7^{15} \equiv 1^4 \times 7^{15} \equiv 7^{15} \pmod{23}$.

Now we need to compute $7^{15} \pmod{23}$. We can do this by finding a pattern: $7^1 \equiv 7 \pmod{23}$ $7^2 \equiv 49 \equiv 3 \pmod{23}$ $7^3 \equiv 7^2 \times 7 \equiv 3 \times 7 = 21 \pmod{23}$ $7^4 \equiv 7^3 \times 7 \equiv 21 \times 7 = 147 \equiv 9 \pmod{23}$ $7^5 \equiv 7^4 \times 7 \equiv 9 \times 7 = 63 \equiv 17 \pmod{23}$ $7^6 \equiv 7^5 \times 7 \equiv 17 \times 7 = 119 \equiv 4 \pmod{23}$ $7^7 \equiv 7^6 \times 7 \equiv 4 \times 7 = 28 \equiv 5 \pmod{23}$ $7^8 \equiv 7^7 \times 7 \equiv 5 \times 7 = 35 \equiv 12 \pmod{23}$ $7^9 \equiv 7^8 \times 7 \equiv 12 \times 7 = 84 \equiv 15 \pmod{23}$ $7^{10} \equiv 7^9 \times 7 \equiv 15 \times 7 = 105 \equiv 13 \pmod{23}$ $7^{11} \equiv 7^{10} \times 7 \equiv 13 \times 7 = 91 \equiv 22 \equiv -1 \pmod{23}$

Using $7^{11} \equiv -1 \pmod{23}$, we can write $7^{15} = 7^{11} \times 7^4 \equiv (-1) \times 9 \equiv -9 \pmod{23}$. Since we want a positive remainder, $-9 \equiv 23 - 9 = 14 \pmod{23}$.

Therefore, the remainder is 14.