2
$\begingroup$

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.

  • 2
    Thank you for fixing my formatting, it is much appreciated. I'm still learning the etiquette of this community.2012-05-14

3 Answers 3

10

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}$.

  • 1
    A function on $\mathbb{Z}/n\mathbb{Z}$...obviously.2012-05-14
1

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$.

0

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.