After reading an article by Peter Norvig about Beal's Conjecture I became pretty interested in digging into it. In his article here he goes into the use of a technique to optimize checking by this:
If $A^x + B^y = C^z$ and $p$ is some word-sized prime then $A^x \pmod p + B^y \pmod p = C^z \pmod p$.
I am aware of a few different properties of modular arithmetic with primes that are useful, but I do not see how this one is derived. I have a feeling that it involves the Chinese Remainder Theorem and some fiddling, but I couldn't find a proof of this equality anywhere and it's really starting to bother me.
Could someone tell me how Norvig arrived at this conclusion? I would really appreciate it. I've never seen such an equality before. Thank you!
There’s nothing relevant about the exponents used in this equation or pertinent about the modulus being prime. To clarify matters, let $a=A^x,$ $b=B^y,$ and $c=C^z.$ If $a+b=c$, then obviously $(a+b) \equiv c\bmod p$ (in the notation Norvig is using, this is saying $(a+b)(\bmod p)=c(\bmod p)).$ So, the only question you might have is whether $ a(\bmod p) + b(\bmod p) = (a+b)(\bmod p).$ But this is clear since if $r_a \equiv a\bmod p$ and $r_b\equiv b \bmod p,$ then we know that $(r_a + r_b)\equiv (a+b)\bmod p.$