For a certain positive integer $n$, the number $n^{6873}$ leaves a remainder of $3$ when divided by $23.$ What remainder does $n$ leave when divided by $23$?

Answer 1

To determine the remainder \( n \) when divided by \( 23 \) given that \( n^{6873} \equiv 3 \pmod{23} \), we start by employing properties of modular arithmetic, specifically Lagrange's Theorem and Fermat's Little Theorem.

First, according to Fermat's Little Theorem, for any integer \( a \) not divisible by a prime \( p \), it holds that:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
For \( p = 23 \), this can be rewritten as:
\[
a^{22} \equiv 1 \pmod{23}
\]
Given \( n^{6873} \equiv 3 \pmod{23} \), we want to reduce the exponent 6873 modulo 22 (since \( 22 = 23 - 1 \)) to utilize Fermat's theorem efficiently.

### Step-by-Step Calculation
\[
6873 \mod 22
\]
We compute the modulo operation:
\[
6873 \div 22 = 312 \text{ R } 9
\]
This implies:
\[
6873 \equiv 9 \pmod{22}
\]

Therefore, the original congruence simplifies to:
\[
n^{6873} \equiv n^9 \pmod{23}
\]
Hence, we now have:
\[
n^9 \equiv 3 \pmod{23}
\]

### Exploring the Solution
We need to find an integer \( n \) such that \( n^9 \equiv 3 \pmod{23} \). To do this systematically, we test all integers \( n \) from 0 to 22 for which this holds.

Testing values manually:
1. \( n = 1 \):
\[
1^9 = 1 \equiv 1 \pmod{23}
\]
2. \( n = 2 \):
\[
2^9 = 512 \rightarrow 512 \mod 23 = 6
\]
3. \( n = 3 \):
\[
3^9 = 19683 \rightarrow 19683 \mod 23 = 3
\]

Upon finding:
\[
3^9 \equiv 3 \pmod{23}
\]
This calculation confirms our viable solution.

Therefore, the remainder \( n \) when divided by 23 is:
\[
\boxed{3}
\]