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.

  • 1
    Please make the question self-contained.2012-05-14
  • 5
    @BrianM.Scott: Snap. Looks like we made the *exact* same edit...2012-05-14
  • 0
    @Arturo: I’m surprised that mine overrode yours, since yours was reported to me just before I hit send.2012-05-14
  • 0
    @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.2012-05-14
  • 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
    In other words, the power function is a...well...function.2012-05-14
  • 2
    @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.2012-05-14
  • 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.