How to calculate $276^{246} \mod 323$ without a calculator?

Question

How do I simplify this expression?

$276^{246} \mod 323$

Thank you so much.

Answer 1

There are more systematic ways to do this, but often you can get the answer by using a few simple rules and tricks.

Let $N = 276^{246}$. First note that the modulus is $17\cdot 19$. If the modulus were to be large and prime, the problem will be quite difficult.

Your problem is now reduced to solving the pair of congruences for $x$ and $y$:

$N \equiv x \pmod{17}$

$N \equiv y \pmod{19}$

Now note that $276 \equiv 4 \pmod {17}$.

Since $4^2 = 16 \equiv -1 \pmod {17}$, we can easily "dispose of" this one:

$N \equiv 4^{246} \equiv (-1)^{123} \equiv -1 \pmod{17}$

For the other congruence, start by reducing the base modulo $19$ to deal with smaller numbers, noting that $276 \equiv 10 \pmod {19}$

Then note that the exponent $246 = (18)(13) + 12$. I used $18$ because it is one less than the prime modulus $19$ and that allows us to employ Fermat's little theorem. Remember that $a^{p-1} \equiv 1 \pmod p$, where prime $p$ does not divide $a$.

So, $N \equiv 10^{18\cdot 13 + 12} = (10^{13})^{18}\cdot 10^{12} \equiv 10^{12}\pmod{19}$.

Now $10^{12} = 100^6 \equiv 5^6 = 25^3 \equiv 6^3 \equiv 7 \pmod{19}$

by successive squaring.

So you now know that $N \equiv -1 \pmod {17}$ and $N \equiv 7 \pmod{19}$. You are now left with solving the pair of simultaneous congruences:

$x \equiv -1 \pmod{17}$

$x \equiv 7 \pmod{19}$

For which a solution modulo $17\cdot 19 = 323$ is guaranteed by the Chinese Remainder Theorem since $(17,19) = 1$ (obviously, they're distinct primes). And since we've established that $x \equiv N \pmod{323}$, the solution to these simultaneous congruences will be the required answer.

From the first congruence, you can write:

$x = 17k - 1$

Substituting into the second congruence,

$17k - 1 \equiv 7 \pmod{19}$

$17k \equiv 8 \pmod{19}$

$k \equiv 8\cdot 17^{-1} \equiv 8\cdot 9 = 72 \equiv 15 \pmod {19}$

(note that $17^{-1}$ refers to the modular inverse of $17 \pmod {19}$, which you can find either by trial and error or using the Extended Euclidean Algorithm).

So $k = 19m + 15$ and $x = 17(19m + 15) - 1 = 323m + 254$

Hence $x \equiv 254 \pmod {323}$.

So the answer is $254$.