# If $a^n \equiv b \pmod m$ and $b^n \equiv c \pmod m$, is it true that $(a^n)^n \equiv c \pmod m$?

If $a^n \equiv b \pmod m$ and $b^n \equiv c \pmod m$, is it true that $(a^n)^n \equiv c \pmod m$?

From testing cases it seems to be true, but I'm unsure of how to prove this.

-
Please make the question self-contained. –  Brian M. Scott May 14 '12 at 20:13
@BrianM.Scott: Snap. Looks like we made the exact same edit... –  Arturo Magidin May 14 '12 at 20:14
@Arturo: I’m surprised that mine overrode yours, since yours was reported to me just before I hit send. –  Brian M. Scott May 14 '12 at 20:15
@Brian: Happens from time to time. Yours was submitted exactly 21 seconds after mine, it may not have had enough time to update and compare it to mine instead of to the original. –  Arturo Magidin May 14 '12 at 20:17
Thank you for fixing my formatting, it is much appreciated. I'm still learning the etiquette of this community. –  Charlie May 14 '12 at 20:17

Yes; because $a\equiv b\pmod{m}$ and $c\equiv d\pmod{m}$ implies $ac\equiv bd\pmod{m}$. Therefore, $x\equiv y\pmod{m}$ implies $x^n\equiv y^n\pmod{m}$ for all positive integers $n$.

Thus, $a^n\equiv b\pmod{m}$ implies that $(a^n)^n \equiv b^n \equiv c\pmod{m}$, and since congruence is transitive, $(a^n)^n\equiv c\pmod{m}$.

-
In other words, the power function is a...well...function. –  Alex Youcis May 14 '12 at 20:14
@Alex: No: in other words, congruence respect multiplication. $a\equiv b\pmod{m}$ does not mean that $a$ and $b$ are equal, so the fact that the power function is a function does not suffice by itself. You need to use the fact that it factors through the quotient as well. –  Arturo Magidin May 14 '12 at 20:15
A function on $\mathbb{Z}/n\mathbb{Z}$...obviously. –  Alex Youcis May 14 '12 at 20:16

To give some direct calculations, although I like Arturos answer:

so $a^n+ k_1 m = b$ and $b^n + k_2 m = c$ for some $k_1, k_2 \in \mathbb Z$. Then \begin{align*} c &= b^n + k_2 m\\\ &= (a^n + k_1m)^n + k_2m\\\ &= (a^n)^n + m \cdot\left( \sum_{\ell=1}^{n} \binom n\ell k_1^\ell m^{\ell-1}a^{n(n-\ell)} +k_2\right) \end{align*} so $(a^n)^n \equiv c \pmod m$.

-

Your $a^n$ is a needless complication here, and may as well be replaced by $x$:

If $x \equiv b \pmod m$ and $b^n \equiv c \pmod m$, is it true that $x^n \equiv c \pmod m$?

You can prove this easily by induction, using the following fact:

If $x \equiv b \pmod m$, then for all $y$, $xy \equiv by \pmod m$.

If this fact is unknown to you, it's not hard to prove it from first principles.

-