Find the remainder when $$ 13^{173} $$ is divided by 84

Question

UpStudy AI · Accepted Answer

To find the remainder when $$ 13^{173} $$ is divided by 84, we can use the **Chinese Remainder Theorem**. Here's a step-by-step breakdown:

1. **Factorize 84:**
   $$
   84 = 4 \times 3 \times 7
   $$

2. **Compute $$ 13^{173} $$ modulo each prime power:**

- **Modulo 4:**
     $$
     13 \equiv 1 \mod 4 \implies 13^{173} \equiv 1^{173} \equiv 1 \mod 4
     $$
   
   - **Modulo 3:**
     $$
     13 \equiv 1 \mod 3 \implies 13^{173} \equiv 1^{173} \equiv 1 \mod 3
     $$
   
   - **Modulo 7:**
     $$
     13 \equiv 6 \mod 7
     $$
     Notice that $$ 6 \equiv -1 \mod 7 $$, so:
     $$
     13^{173} \equiv (-1)^{173} \equiv -1 \equiv 6 \mod 7
     $$

3. **Combine the results using the Chinese Remainder Theorem:**
   We need to find a number $$ x $$ such that:
   $$
   x \equiv 1 \mod 4, \quad x \equiv 1 \mod 3, \quad \text{and} \quad x \equiv 6 \mod 7
   $$
   
   From the first two congruences:
   $$
   x \equiv 1 \mod 12
   $$
   
   Now, solve:
   $$
   x \equiv 1 \mod 12 \quad \text{and} \quad x \equiv 6 \mod 7
   $$
   
   Testing multiples of 12 plus 1:
   $$
   13 \equiv 6 \mod 7
   $$
   So, $$ x = 13 $$ satisfies all three congruences.

Therefore, the remainder when $$ 13^{173} $$ is divided by 84 is **13**.

**Answer:** 13
The remainder when $$ 13^{173} $$ is divided by 84 is **13**.

Find the remainder when is divided by 84

Upstudy AI Solution

Answer

Solution

Beyond the Answer

Related Questions

Latest Arithmetic Questions