Is $a^x \pmod{n} = (a\pmod{n})^{x \pmod{n}}$?

Question

Is it right to claim that:

$a^x \pmod{n} = (a \pmod{n})^{x \pmod{n}}$?

I know that:

$a^x \pmod{n} = (a \pmod{n})^{x}$?

Answer 1

Not necessarily. Note that

$$a^{x \text{ mod }n} \text{mod }n \equiv a^x \text{mod } n$$ implies that

$$a^n \text{ mod n}\equiv 1$$,

which by Fermat's Little Theorem is wrong in infinitely many cases, as if n is prime,

$$a^n \text{ mod n} \equiv a^{n-1}$$ which is almost never true. An example of this is $a=2,n=7,x=8$, resulting in

$$2 \text{ mod 7} \equiv 2^8 \text{ mod 7}\equiv 4$$

Which clearly isn't true

Answer 2

It is not true in general. Consider the following example:

$3^3 (mod\;5) = 2$ and $(3^3)^6 (mod\;5) \neq 2^1$

Answer 3

No, and this is an interesting twist in modular arithmetic!

You can see for yourself that the answer is No, with a simple example, such as $$ 2 ^ 3 \bmod 3 = 2 \ne 1 = ( 2 \bmod 3 ) ^ { 3 \bmod 3 } $$ or the examples in the other answers. But more interesting is to see what is true instead.

Modular arithmetic works because $ a + b \equiv c + d \pmod n $ and $ a b \equiv c d \pmod n $ whenever $ a \equiv c \pmod n $ and $ b \equiv d \pmod n $. As the examples show, we don't get $ a ^ b \equiv c ^ d \pmod n $ when $ a \equiv c \pmod n $ and $ b \equiv d \pmod n $. However, we do get $ a ^ b \equiv c ^ d \pmod n $ when $ a \equiv c \pmod n $ and $ b \equiv d \pmod { \lambda ( n ) } $, where $ \lambda $ is the Carmichael function, whenever $ b $ and $ d $ are sufficiently large (specifically, whenever they're both at least as big as the largest exponent on a prime number in the prime factorization of $ n $). So the lesson is, exponents must be reduced modulo $ \lambda ( n ) $ instead of modulo $ n $ like everything else. (And annoyingly, you have to check that this reduced exponent is large enough.)

For example, since $ \lambda ( 3 ) = 2 $, we might get $$ 2 ^ 3 \bmod 3 = ( 2 \bmod 3 ) ^ { 3 \bmod 2 } \text . $$ I say that we might get this, since we still need to check that both exponents, $ 3 $ and $ 3 \bmod 2 $, are sufficiently large. Since $ 3 = 3 ^ 1 $ has $ 1 $ as the highest exponent in its prime factorization, and since both $ 3 $ and $ 3 \bmod 2 = 1 $ are at least as large as $ 1 $, we're good. (And I really only needed to check $ 3 \bmod 2 = 1 $, since the unreduced exponent $ 3 $ can only be even larger.) And you can see if you check that this equation is true.

For a more complicated example, what is $ { 5 1 } ^ { 7 3 } \bmod 1 8 $? Well, you have to calculate $ \lambda ( 1 8 ) $, but that's not too bad. You can see how to calculate it in the Wikipedia article that I linked above, and the answer is $ 6 $. So reduce $ 5 1 $ modulo $ 1 8 $ to $ 1 5 $, and reduce $ 7 3 $ modulo $ 6 $ to $ 1 $. So hopefully, we can just take $ 1 5 ^ 1 = 1 5 $. But wait! We also need to check that the exponents are sufficiently large. Since $ 1 8 = 2 ^ 1 \cdot 3 ^ 2 $, the largest exponent in the prime factorization is $ 2 $, so we need $ 7 3 \bmod 6 $ be at least $ 2 $, which it's not. But don't despair! We'll just lower $ 7 3 $ below a multiple of $ 6 $ to get $ 7 1 \bmod 6 = 5 $, which is large enough. Then write $ 5 1 ^ { 7 3 } = 5 1 ^ { 7 1 } \cdot 5 1 ^ 2 $. For $ 5 1 ^ { 7 1 } $, we reduce $ 5 1 $ modulo $ 1 8 $ to $ 1 5 $ as before, and reduce $ 7 1 $ modulo $ 6 $ to $ 5 $; since $ 5 \geq 2 $ (the largest exponent in the prime factorization of $ 1 8 $), we're allowed to say that $ 5 1 ^ { 7 1 } \equiv 1 5 ^ 5 \pmod { 1 8 } $. And since $ 1 5 \equiv - 3 \pmod { 1 8 } $, we can even change this to $ ( - 3 ) ^ 5 = - 2 4 3 \equiv 9 \pmod { 1 8 } $. (But it's also not too hard to start with $ 1 5 $ as long as you reduce mod $ 1 8 $ at each step.) For $ 5 1 ^ 2 $, we can still reduce $ 5 1 $ mod $ 1 8 $ to $ 1 5 $, and then $ 1 5 ^ 2 = 2 2 5 \equiv 9 \pmod { 1 8 } $. Multiplying these together, we get $ 9 \cdot 9 = 8 1 \equiv 9 \pmod { 1 8 } $. Therefore, $ 5 1 ^ { 7 3 } \bmod 1 8 $ is $ 9 $.