Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Please make the question self-contained. –  Brian M. Scott May 14 '12 at 20:13
4  
@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
2  
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

3 Answers 3

up vote 9 down vote accepted

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

share|improve this answer
1  
In other words, the power function is a...well...function. –  Alex Youcis May 14 '12 at 20:14
1  
@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
1  
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$.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.