201k views
1 vote
How does Fermat's lil theorem help us to solve 7^148 in ?17?

a) 7^148 is not solvable in ?17 using Fermat's lil theorem
b) 7^148 mod 17 is 1
c) 7^148 mod 17 is 0
d) 7^148 mod 17 is 7

User Jcz
by
7.2k points

1 Answer

3 votes

Final answer:

Using Fermat's Little Theorem, we simplify 7^148 mod 17 to 7^4 mod 17 by reducing the exponent modulo 16. Since 7^4 mod 17 equals 1, the answer is that 7^148 mod 17 is 1.

Step-by-step explanation:

The question asks how Fermat's Little Theorem can be used to solve 7148 mod 17. Fermat's Little Theorem states that if p is a prime number and a is an integer not divisible by p, then ap-1 ≡ 1 (mod p). In this case, 17 is prime and 7 is not divisible by 17, so we can apply the theorem.

According to the theorem, 716 ≡ 1 (mod 17). When we have an exponent that is larger than 16 in this case, we can reduce the power using the exponent's modulo 16 equivalent since 716k ≡ 1k (mod 17) for any integer k. So 7148 ≡ 7(9×16+4) ≡ (716)9×74 ≡ 19×74 ≡ 74 (mod 17). Since 74 = 2401 and 2401 mod 17 = 1, the result is that 7148 mod 17 ≡ 1.

Therefore, the correct answer is (b) 7148 mod 17 is 1.