Question

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

(1) 14

(2) 9

(3) 17

(4) 6

Answer 1

Correct option is (1) 14  

\(7,7^2=49,7^3=343 \equiv(-2)(\bmod 23)\)

\( \Rightarrow 7^{102} \equiv\left(7^3\right)^{34} \equiv(-2)^{34} \equiv 4^{17}(\bmod 23) \)

\( \Rightarrow 4^6 \equiv 2(\bmod 23) \)

\(4^{17} \equiv(2)(2)(12) \equiv 2(\bmod 23) \)

\( 7^{103} \equiv 7.4^{17} \equiv 14(\bmod 23) \)

Alter : \( 7^{\phi(23)} \equiv 1(\bmod 23), \operatorname{gcd}(7,23)=1\)

\(\phi(23)=(23-1)=22 \)

\(\Rightarrow 7^{22} \equiv 1(\bmod 23) \Rightarrow 7^{11} \equiv(-1) \bmod (23) \)

\({\left[\text { as } 7^{11} \equiv 1 \bmod 23\right] \Rightarrow 7^{99} \equiv-1 \bmod (23)} \)

\( 7^{102} \equiv 2(\bmod 23) \)

\( \Rightarrow 7^{103} \equiv 14 \bmod 23\)

Answer 2

Correct option is (1) 14 

Using Fermat’s Theorem:

Since 23 is a prime number, by Fermat’s theorem:

7^22 ≡ 1 (mod 23)

Reducing the Exponent:

Divide 103 by 22:

103 ÷ 22 = 4 remainder 15

So, 103 ≡ 15 (mod 22)

This means: 7^103 ≡ 7^15 (mod 23)

Breaking Down 7^15 mod 23:

First, calculate smaller powers:

7^2 = 49 ≡ 3 (mod 23)

7^4 = (7^2)^2 = 3^2 = 9 (mod 23)

7^8 = (7^4)^2 = 9^2 = 81 ≡ 12 (mod 23)

Now, compute 7^15:

7^15 = 7^8 × 7^4 × 7^2 × 7 (mod 23)

Step-by-Step Modulo 23 Computation:

12 × 9 = 108 ≡ 16 (mod 23)

16 × 3 = 48 ≡ 2 (mod 23)

2 × 7 = 14 (mod 23)

Thus, the remainder is 14.

Final Answer: (1) 14