Find the remainder when \( 13^{173} \) is divided by 84

To find the remainder when \( 13^{173} \) is divided by \( 84 \), we can apply the properties of modular arithmetic and the Chinese Remainder Theorem since \( 84 = 4 \times 21 \). **Step 1: Find \( 13^{173} \mod 4 \)** We notice that: \[ 13 \equiv 1 \mod 4 \] Therefore: \[ 13^{173} \equiv 1^{173} \equiv 1 \mod 4 \] **Step 2: Find \( 13^{173} \mod 21 \)** Next, we will calculate \( 13^{173} \mod 21 \). We first find \( \phi(21) \) using Euler's Totient Function, where: \[ \phi(21) = (3-1)(7-1) = 2 \times 6 = 12 \] So by Euler's theorem, since \( \gcd(13, 21) = 1 \): \[ 13^{12} \equiv 1 \mod 21 \] Now, we need to compute \( 173 \mod 12 \): \[ 173 \div 12 = 14 \quad \text{remainder: } 5 \] Thus: \[ 173 \equiv 5 \mod 12 \] This tells us: \[ 13^{173} \equiv 13^5 \mod 21 \] Now calculating \( 13^5 \mod 21 \): \[ 13^2 = 169 \quad \Rightarrow \quad 169 \mod 21 = 169 - 7 \times 21 = 169 - 147 = 22 \quad \Rightarrow \quad 22 \mod 21 = 1 \] So: \[ 13^2 \equiv 1 \mod 21 \] Thus, we calculate \( 13^4 \): \[ 13^4 \equiv (13^2)^2 \equiv 1^2 \equiv 1 \mod 21 \] Now we compute \( 13^5 \): \[ 13^5 = 13^4 \times 13 \equiv 1 \times 13 \equiv 13 \mod 21 \] **Step 3: Combine the results using the Chinese Remainder Theorem** We have: \[ 13^{173} \equiv 1 \mod 4 \] \[ 13^{173} \equiv 13 \mod 21 \] Now we need to find a number \( x \) such that: \[ x \equiv 1 \mod 4 \] \[ x \equiv 13 \mod 21 \] We can express \( x \) in the form \( x = 21k + 13 \) for some integer \( k \). We substitute into the first congruence: \[ 21k + 13 \equiv 1 \mod 4 \] Calculating \( 21 \mod 4 \): \[ 21 \equiv 1 \mod 4 \] Thus: \[ 1k + 13 \equiv 1 \mod 4 \quad \Rightarrow \quad k + 1 \equiv 1 \mod 4 \quad \Rightarrow \quad k \equiv 0 \mod 4 \] This means \( k = 4m \) for some integer \( m \). Plugging it back we have: \[ x = 21(4m) + 13 = 84m + 13 \] Thus: \[ x \equiv 13 \mod 84 \] Finally, the remainder when \( 13^{173} \) is divided by \( 84 \) is: \[ \boxed{13} \]