The remainder when `23^23` is divided by 53 is

Options

A. 17
B. 21
C. 30
D. 47

Answer

To find the remainder when \( 23^{23} \) is divided by \( 53 \), we can use properties of modular arithmetic. Here’s a step-by-step solution:

### Step 1: Simplify the expression
We start with the expression \( 23^{23} \mod 53 \).

### Step 2: Break down the exponent
We can express \( 23^{23} \) as \( 23^{22} \cdot 23 \). Therefore, we can write:
\[ 23^{23} \equiv 23^{22} \cdot 23 \mod 53 \]

### Step 3: Calculate \( 23^{22} \mod 53 \)
To simplify \( 23^{22} \mod 53 \), we can use Fermat's Little Theorem, which states that if \( p \) is a prime and \( a \) is not divisible by \( p \), then:
\[ a^{p-1} \equiv 1 \mod p \]
Here, \( p = 53 \) and \( a = 23 \). Since \( 23 \) is not divisible by \( 53 \), we have:
\[ 23^{52} \equiv 1 \mod 53 \]

### Step 4: Reduce the exponent
Since \( 22 < 52 \), we can directly compute \( 23^{22} \mod 53 \). However, we can also compute \( 23^2 \) first to make calculations easier.

### Step 5: Calculate \( 23^2 \mod 53 \)
Calculating \( 23^2 \):
\[ 23^2 = 529 \]
Now, we find \( 529 \mod 53 \):
\[ 529 \div 53 \approx 9.981 \quad \text{(take the integer part, which is 9)} \]
Calculating \( 9 \times 53 = 477 \), we find:
\[ 529 - 477 = 52 \]
Thus,
\[ 23^2 \equiv 52 \mod 53 \]

### Step 6: Substitute back into the expression
Now we can substitute back:
\[ 23^{22} = (23^2)^{11} \equiv 52^{11} \mod 53 \]

### Step 7: Simplify \( 52^{11} \mod 53 \)
Notice that \( 52 \equiv -1 \mod 53 \). Therefore:
\[ 52^{11} \equiv (-1)^{11} \equiv -1 \mod 53 \]

### Step 8: Combine results
Now substituting back into our expression:
\[ 23^{23} \equiv (-1) \cdot 23 \mod 53 \]
This simplifies to:
\[ -23 \mod 53 \]

### Step 9: Find the positive remainder
To convert \( -23 \) into a positive remainder, we add \( 53 \):
\[ -23 + 53 = 30 \]

### Final Answer
Thus, the remainder when \( 23^{23} \) is divided by \( 53 \) is:
\[ \boxed{30} \]