Question

Use Euler’s theorem (or Fermat’s little theorem) to compute the following exponent without

using calculators and justify your answers.
(a) 63⁸⁰ mod 200
(b) 63⁸¹ mod 200

Answer 1

To compute 63⁸⁰ mod 200 and 63⁸¹ mod 200 using Euler's theorem, we find the totient function value and apply the theorem to obtain the answers 1 and 63 respectively.

Step-by-step explanation:

To compute 63⁸⁰ mod 200 and 63⁸¹ mod 200 using Euler's theorem, we need to find the totient function value and apply the theorem. Since 200 = 2² × 5², the totient function value is φ(200) = (2² - 2¹) × (5² - 5¹) = 40. Now, we can use Euler's theorem:

For part (a), 63⁸⁰ mod 200 = 63⁴⁰ mod 200 = (63²)²⁰ mod 200 = (1)²⁰ mod 200 = 1.

For part (b), 63⁸¹ mod 200 = 63 × 63⁸⁰ mod 200 = 63 × 1 mod 200 = 63.