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.3k 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.

Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories