Introduction to Finding Remainders Using Number Theory Theorems

In this article, we explore the process of finding the remainder of a complex expression involving large exponents, prime numbers, and specific integers. We will use two fundamental theorems in number theory: Fermat's Little Theorem and Euler's Theorem. These theorems are powerful tools for simplifying such calculations. By following these steps, we can efficiently determine the remainders of expressions when divided by a given prime number.

Understanding the Problem

Consider the expression (3^{2002} times 7^{2002} 2002). Our goal is to find the remainder when this expression is divided by 29. To solve this, we will use the theorems of Fermat and Euler. Both theorems provide shortcuts for calculating remainders when dealing with large powers.

Finding the Remainder Using Fermat's Little Theorem

Fermat's Little Theorem states that if (p) is a prime number and (a) is an integer not divisible by (p), then (a^{p-1} equiv 1 pmod{p}).

In our case, (p 29). Therefore, for any integer (a) not divisible by 29, (a^{28} equiv 1 pmod{29}).

Step 1: Calculating (3^{2002} mod 29)

First, we reduce the exponent 2002 modulo 28:

(2002 div 28 approx 71.5) rarr; (2002 28 times 71 14)

Hence, (2002 equiv 14 pmod{28}). Therefore, (3^{2002} equiv 3^{14} pmod{29}).

Next, we calculate (3^{14} mod 29):

(3^1 3)

(3^2 9)

(3^4 9^2 81 equiv 23 pmod{29})

(3^8 23^2 529 equiv 30 equiv 1 pmod{29})

Using these results, we can compute (3^{14}):

(3^{14} 3^8 times 3^4 times 3^2 equiv 1 times 23 times 9 mod 29)

This simplifies to: ((23 times 9) equiv 207 equiv 10 pmod{29})

Hence, (3^{2002} equiv 10 pmod{29}).

Step 2: Calculating (7^{2002} mod 29)

Using Fermat's theorem again, (7^{28} equiv 1 pmod{29}). Since (2002 equiv 14 pmod{28}), we have:

(7^{2002} equiv 7^{14} pmod{29})

Now, we calculate (7^{14} mod 29):

(7^1 7)

(7^2 49 equiv 20 pmod{29})

(7^4 20^2 400 equiv 23 pmod{29})

(7^8 23^2 529 equiv 30 equiv 1 pmod{29})

Using these results, we can compute (7^{14}):

(7^{14} 7^8 times 7^4 times 7^2 equiv 1 times 23 times 20 mod 29)

This simplifies to: ((23 times 20) equiv 460 equiv 24 pmod{29})

Hence, (7^{2002} equiv 24 pmod{29}).

Step 3: Calculating (2002 mod 29)

Dividing 2002 by 29, we get:

(2002 div 29 approx 69.0345) rarr; (2002 29 times 69 11)

Hence, (2002 equiv 11 pmod{29}).

Combining the Results

Now, we combine all the parts:

(3^{2002} times 7^{2002} 2002 equiv 10 times 24 11 pmod{29})

This simplifies to:

(10 times 24 11 240 11 251)

Dividing 251 by 29, we get:

(251 div 29 approx 8.6552) rarr; (251 29 times 8 26)

Hence, (251 equiv 26 pmod{29}).

Therefore, the remainder when (3^{2002} times 7^{2002} 2002) is divided by 29 is 26.

Alternative Solution Using Euler's Theorem

Euler's Theorem states that if (a) and (n) are coprime, then (a^{phi(n)} equiv 1 pmod{n}), where (phi(n)) is Euler's totient function. For a prime (p), (phi(p) p-1). Therefore, (a^{p-1} equiv 1 pmod{p}), which is essentially Fermat's Little Theorem.

In our problem, (n 29), so (phi(29) 28). Thus, (a^{28} equiv 1 pmod{29}).

Given (2002 28 times 71 14), we have:

(3^{2002} equiv 3^{14} pmod{29}) and (7^{2002} equiv 7^{14} pmod{29}).

Using the same calculations as in the Fermat's Little Theorem approach, we find:

(3^{2002} equiv 10 pmod{29}) and (7^{2002} equiv 24 pmod{29}).

Adding these together:

(10 times 24 11 240 11 251), and thus:

(251 equiv 26 pmod{29}).

Hence, the remainder is again found to be 26.

Conclusion

By applying Fermat's Little Theorem and Euler's Theorem, we have demonstrated a systematic method to find the remainder of complex expressions without directly calculating the large powers. The remainder when (3^{2002} times 7^{2002} 2002) is divided by 29 is definitively 26.