Modular Arithmetic - Are we allowed to distribute the Modularity? Assume I have a problem such as "Prove that $\displaystyle103^{53} + 53^{103}$ is divisible by $39$."
This would mean I wanted to prove that $\displaystyle103^{53} + 53^{103}\equiv0\pmod{39}$.
My starting statement would be then "$\displaystyle103^{53} + 53^{103}\pmod{39}$" and I would then equate this to "$\displaystyle103^{53}\pmod{39} + 53^{103}\pmod{39}$" and then continue.
Am I allowed to distribute the mod like that?
Thanks.
 A: Mathematicians and programmers have two different ways of thinking about mod. To the latter, it is a binary operation in which ${\rm Mod}[a,b]$ is the remainder of $a$ when divided by $b$ (so it will return an integer in the range $0\le r<b$). To the former, it is a binary relation (a symbol that relates things in some way, like $<,=,>,\approx,\sim$ etc.) for each modulus $b$. We say that $n\color{Red}{\equiv}m$ mod $b$ if the difference $n-m$ is divisible by $b$, or equivalently if ${\rm Mod}[n,b]={\rm Mod}[m,b]$. Sometimes the equivalence symbol $\equiv$ is simply replaced by an equality symbol $=$, in which case we are understood to be equating equivalence classes. The relation $n\equiv m$ mod $b$ is in fact a congruence relation (it "respects" $+$ and $\times$), and the equivalence classes are called residue classes, or just residues.
So if $a\equiv b$ and $c\equiv d$ mod $m$ then $ac\equiv bd$ and $a+c\equiv b+d$ mod $m$. One can use this to end up proving that, in particular, $f(a)\equiv f({\rm Mod}[a,m])$ mod $m$ for integer-coefficient polynomials $f$. 
Thus for example ${\rm Mod}[a,m]+{\rm Mod}[b,m]$ and $a+b$ and ${\rm Mod}[a+b,m]$ are all congruent mod $m$, however it is not strictly true that the first and last are equal as integers. Take $a,b=2$ and $m=3$, in which case ${\rm Mod}[2,3]+{\rm Mod}[2,3]=2+2=4\ne1={\rm Mod}[2+2,3]$, albeit $4\equiv1$ mod $3$.
If $n$ and $m$ are coprime, then $a\equiv b$ modulo both $n$ and $m$ if and only if $a\equiv b$ mod $nm$. In particular this means $x\equiv 0$ mod $39$ if and only if $x\equiv0$ mod $3$ and mod $13$.  Compute
$$103^{53}+53^{103}\equiv 1^{53}+(-1)^{103}\equiv 1+(-1)\equiv0\mod 3 $$
because $103\equiv1$ and $53\equiv-1$ mod $3$. And then compute
$$103^{53}+53^{103}\equiv(-1)^{53}+1^{103}\equiv(-1)+1\equiv0\mod 13 $$
because $103\equiv-1$ and $53\equiv1$ mod $13$. Since $103^{53}+53^{103}$ is $0$ mod $3$ and $13$, it is $0$ mod $39$.
A: If $103^{53} \equiv a \mod 39$ and $53^{103} \equiv b \mod 39$, than it is indeed true that $103^{53} + 53^{103} \equiv a+b \mod 39$. I wouldn't recommend your notation, which makes $ \mod\mbox{ }$ look like an operator.
A: To say that
$$x \equiv a \pmod{m}$$
means that there is some integer $k$ such that
$$x - a = mk$$
Thus, expanding on user133281's answer (i.e. if $103^{53}\equiv a \pmod{39}$ and $53^{103}\equiv b \pmod{39}$), we have
$$(103^{53}-a)+(53^{103}-b)=39k+39l$$
which is equivalent to
$$(103^{53}+53^{103})-(a+b)=39(k+l)$$
so
$$103^{53}+53^{103}\equiv a+b\pmod{39}$$
A: HINT:
Please have  a look into this for the properties of congruence
$\displaystyle 103\equiv-1\pmod{13}\implies 103^{53}\equiv(-1)^{53}\equiv-1$
$\displaystyle 53\equiv1\pmod{13}\implies 53^{103}\equiv(1)^{103}\equiv1$
Similarly, for $\pmod3$
Now if $13$ and $3$ both divides $a,a$ will be divisible by lcm$(13,3)$ 
A: The "equivalent modulo $n$" relation is a congruence: a congruence is an equivalence relation with the additional property that for all relevant arithmetic operations (in this case, $0, 1, +, \times$, and anything derived from those), if the inputs the the arithmetic operation are congruent, then the outputs are also congruent.
In the actual ring of integers modulo $n$, though, there is no "congruence" or "mod": e.g. $39 = 0$ is a literal equality. Your question to prove
$$ 103^{53} + 53^{103} \equiv 0 \pmod{39} $$
in the integers is the same thing as trying to prove
$$ 103^{53} + 53^{103} = 0$$
in the ring of integers modulo $39$. And since we're working with actual equality, it's clear that we can simplify the two summands separately, then add the simplified results.
