Question

When \(5^{20}\) is divided by 48 then remainder is (a) 2 (b) 0 (c) 1 (d) 5

Short answer

The remainder when \(5^{20}\) is divided by 48 is 1. The correct answer is (c) 1.

Step-by-step solution

Write the expression in congruence form

We want to find the remainder when dividing \(5^{20}\) by 48. This can be written equivalently as finding the value of \(5^{20} \mod 48\).

Express 48 as the product of its factors

To make our calculations easier, we can express 48 as the product of its prime factors, which are 2 and 3. We have: \(48 = 2^4 \cdot 3\).

Use the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) states that if the moduli are pairwise relatively prime, we can find the remainder modulo their product (in this case, 48) by finding the remainders modulo each of the factors (2^4 and 3). So, we want to find the values of \(5^{20} \mod 2^4\) and \(5^{20} \mod 3\).

Calculate the remainders modulo each of the factors

Notice that \(5^{20} \equiv 1 \pmod{2^4}\) because any odd number raised to an even exponent is odd and hence odd number will have remainder 1 when divided by 2^4. For the second congruence, we will use Fermat's Little Theorem. Because 5 and 3 are relatively prime, we know that \(5^{(3-1)} \equiv 1 \pmod{3}\), or \(5^2 \equiv 1 \pmod{3}\). This means 😃 \[5^{20} = (5^2)^{10} \equiv 1^{10} \equiv 1 \pmod{3}\] Now we have that \(5^{20} \equiv 1 \pmod{2^4}\) and \(5^{20} \equiv 1 \pmod{3}\).

Reconstruct the remainder modulo 48

We are now to see the remainder of \(5^{20} \pmod{48}\). Since both congruences have the same remainder (1), we can conclude that \(5^{20} \equiv 1 \pmod{48}\). Therefore, the remainder when \(5^{20}\) is divided by 48 is 1. The correct answer is (c) 1.

Key concepts

Modular Arithmetic

Modular arithmetic is a fundamental concept in number theory. It's like regular arithmetic, but it focuses on the remainder of division by a certain number, called the "modulus." When dealing with modular arithmetic, we often use the notation \(a \equiv b \pmod{m}\). This means that when \(a\) is divided by \(m\), the remainder is \(b\). In the context of the problem, we wanted to find out \(5^{20} \mod 48\), which is basically finding the remainder when \(5^{20}\) is divided by 48.

Here's how it works:

• Start with a base number, in this case, 5.
• Raise it to a power, which is 20 for the problem.
• Divide the result by the modulus, which is 48, and calculate the remainder.

This problem is solved more easily using laws like the Chinese Remainder Theorem and Fermat's Little Theorem, simplifying intermediate steps.

Fermat's Little Theorem

Fermat's Little Theorem is a useful tool in modular arithmetic, especially when dealing with powers. The 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}\). This theorem is particularly handy when we want to calculate large powers modulo a number.

In the problem, we applied Fermat's Little Theorem to simplify the calculation of \(5^{20} \pmod{3}\):

• The number 3 is a prime modulus.
• Apply Fermat's theorem: since \(5^2 \equiv 1 \pmod{3}\), it follows that \((5^2)^{10} \equiv 1^{10} \equiv 1 \pmod{3}\).

This saved us from computing \(5^{20}\) directly, significantly simplifying the process.

Remainder Theorem

The Remainder Theorem bridges polynomial division and modular arithmetic. It states that for any polynomial \(f(x)\), the remainder when \(f(x)\) is divided by \(x-c\) is \(f(c)\). However, in a broader sense, solving remains of numerical power problems like our given exercise shares the same idea.

• This problem explores the computation of remainder on division by considering factors, e.g., using 48 as a product of smaller numbers.
• The Chinese Remainder Theorem (CRT) beautifully exploits this by allowing us to calculate remainders with respect to smaller, relatively prime numbers \(2^4\) and 3.

By individually computing the remainders of \(5^{20}\) with respect to these factors, then consolidating the results, CRT allows us to find the remainder with respect to the original modulus (48). Here, matching remainders expedite solving, ensuring \(5^{20} \equiv 1 \pmod{48}\). This illustrates how modular arithmetic and the remainder theorem can simplify complex computations.