\(3 \times 7^{22} + 2 \times 10^{22} - 44\) when divided by 18 leaves the remainder _________.
Show Hint
When calculating \(a^b \pmod n\), look for a power \(k\) such that \(a^k \equiv 1 \pmod n\) (using Euler's totient theorem if applicable) or find a repeating cycle. This greatly simplifies the calculation for large exponents by using the property \(b = kq + r\), which implies \(a^b \equiv (a^k)^q \cdot a^r \equiv 1^q \cdot a^r \equiv a^r \pmod n\).
Step 1: State the problem in terms of modular arithmetic.
We need to find the value of \(N = 3 \cdot 7^{22} + 2 \cdot 10^{22} - 44 \pmod{18}\). We will evaluate each term separately.
Step 2: Evaluate the first term, \(3 \cdot 7^{22} \pmod{18}\).
First, find the pattern of powers of 7 modulo 18.
- \(7^1 \equiv 7 \pmod{18}\)
- \(7^2 = 49 = 2 \times 18 + 13 \equiv 13 \pmod{18}\)
- \(7^3 = 7^2 \cdot 7 \equiv 13 \cdot 7 = 91 = 5 \times 18 + 1 \equiv 1 \pmod{18}\)
The cycle length of powers of 7 is 3. We use this to simplify \(7^{22}\).
The exponent is \(22 = 3 \times 7 + 1\).
So, \(7^{22} = (7^3)^7 \cdot 7^1 \equiv 1^7 \cdot 7 \equiv 7 \pmod{18}\).
Therefore, the first term is \(3 \cdot 7^{22} \equiv 3 \cdot 7 = 21 \equiv 3 \pmod{18}\).
Step 3: Evaluate the second term, \(2 \cdot 10^{22} \pmod{18}\).
Find the pattern of powers of 10 modulo 18.
- \(10^1 \equiv 10 \pmod{18}\)
- \(10^2 = 100 = 5 \times 18 + 10 \equiv 10 \pmod{18}\)
It appears that \(10^k \equiv 10 \pmod{18}\) for all \(k \ge 1\).
So, \(10^{22} \equiv 10 \pmod{18}\).
Therefore, the second term is \(2 \cdot 10^{22} \equiv 2 \cdot 10 = 20 \equiv 2 \pmod{18}\).
Step 4: Evaluate the third term, \(-44 \pmod{18}\).
First, find the remainder of 44 when divided by 18.
\(44 = 2 \times 18 + 8\), so \(44 \equiv 8 \pmod{18}\).
This means \(-44 \equiv -8 \pmod{18}\). To get a positive remainder, we add 18: \(-8 + 18 = 10\).
So, \(-44 \equiv 10 \pmod{18}\).
Step 5: Combine the results.
\[ N \equiv (3) + (2) + (10) \pmod{18} \]
\[ N \equiv 15 \pmod{18} \]
The remainder is 15.
