Key Concept: Fermat's Little Theorem

Fermat's Little Theorem is a fundamental result in number theory that simplifies calculations involving large exponents in modular arithmetic. It states that if $p$ is a prime number, then for any integer $a$ not divisible by $p$, we have: $a^{p-1} \equiv 1 \pmod{p}$ This theorem is incredibly useful for reducing large exponents to smaller, more manageable values, making it easier to find remainders.

Problem Setup

We need to find the remainder when $7^{103}$ is divided by 23. Here, $a=7$ and $p=23$. Since 23 is a prime number and 7 is not divisible by 23, we can apply Fermat's Little Theorem.

Step-by-Step Solution

Step 1: Apply Fermat's Little Theorem to simplify the base. According to Fermat's Little Theorem, $7^{23-1} \equiv 7^{22} \equiv 1 \pmod{23}$. This means that any power of $7^{22}$ will also be congruent to 1 modulo 23. This is a powerful simplification, as it allows us to effectively "remove" multiples of 22 from the exponent.

Step 2: Simplify the exponent. Our goal is to express the exponent 103 in terms of multiples of 22. We do this by dividing 103 by 22: $103 = 22 \times 4 + 15$ This tells us that $7^{103}$ can be written as $(7^{22})^4 \times 7^{15}$.

Step 3: Rewrite the expression using modular properties. Now we substitute the result from Step 1 into our expression: $7^{103} = 7^{(22 \times 4) + 15} = (7^{22})^4 \times 7^{15}$ Since $7^{22} \equiv 1 \pmod{23}$, we can replace $7^{22}$ with 1 in the modular congruence: $7^{103} \equiv (1)^4 \times 7^{15} \pmod{23}$ $7^{103} \equiv 1 \times 7^{15} \pmod{23}$ $7^{103} \equiv 7^{15} \pmod{23}$ Now the problem has been significantly reduced to finding the remainder of $7^{15}$ when divided by 23.

Step 4: Calculate the remaining power ($7^{15} \pmod{23}$). To calculate $7^{15} \pmod{23}$, we can compute successive powers of 7 modulo 23: $7^1 \equiv 7 \pmod{23}$ $7^2 \equiv 49 \equiv 3 \pmod{23}$ (since $49 = 2 \times 23 + 3$) $7^3 \equiv 7^2 \times 7^1 \equiv 3 \times 7 \equiv 21 \equiv -2 \pmod{23}$ (using negative remainder simplifies calculations) $7^4 \equiv (7^2)^2 \equiv 3^2 \equiv 9 \pmod{23}$ $7^5 \equiv 7^4 \times 7^1 \equiv 9 \times 7 \equiv 63 \equiv 17 \equiv -6 \pmod{23}$ (since $63 = 2 \times 23 + 17$) $7^{10} \equiv (7^5)^2 \equiv (-6)^2 \equiv 36 \equiv 13 \pmod{23}$ (since $36 = 1 \times 23 + 13$) $7^{11} \equiv 7^{10} \times 7^1 \equiv 13 \times 7 \equiv 91 \equiv 22 \equiv -1 \pmod{23}$ (since $91 = 3 \times 23 + 22$)

Notice that $7^{11} \equiv -1 \pmod{23}$ is a very helpful intermediate result, as it means $7^{22} \equiv (-1)^2 \equiv 1 \pmod{23}$, which aligns with Fermat's Little Theorem. Now, we can use this to calculate $7^{15}$: $7^{15} = 7^{11} \times 7^4 \pmod{23}$ Substitute the values we found: $7^{15} \equiv (-1) \times 9 \pmod{23}$ $7^{15} \equiv -9 \pmod{23}$

To express this as a positive remainder, we add 23: $-9 + 23 = 14$. Therefore, $7^{103} \equiv 14 \pmod{23}$.

Tips for Modular Arithmetic

• Use Negative Remainders: When working with modulo $n$, if a number $x$ has a remainder $r$, then $x \equiv r \pmod{n}$. It's often easier to work with $r-n$ if $r$ is greater than $n/2$ (e.g., $21 \equiv -2 \pmod{23}$ is simpler than $21 \pmod{23}$).
• Break Down Exponents (Binary Exponentiation): To calculate $a^k \pmod{n}$ for large $k$, write $k$ in binary or break it down into powers of 2 (e.g., $7^{15} = 7^{8} \times 7^4 \times 7^2 \times 7^1$) to minimize multiplications.
• Check for Smaller Orders: Always be on the lookout for a smaller exponent $k$ such that $a^k \equiv 1 \pmod{p}$ or $a^k \equiv -1 \pmod{p}$, as this can simplify calculations even further than Fermat's Little Theorem. In this case, we found $7^{11} \equiv -1 \pmod{23}$, which is more efficient than directly using $7^{22} \equiv 1 \pmod{23}$ for smaller exponents.

Summary/Key Takeaway

By leveraging Fermat's Little Theorem, we systematically reduced the large exponent $103$ down to $15$. Subsequent calculations of $7^{15} \pmod{23}$ using intermediate modular results and the property $7^{11} \equiv -1 \pmod{23}$ allowed us to efficiently determine the remainder. The remainder when $7^{103}$ is divided by 23 is 14.