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

-
Yes, you are... –  DonAntonio Mar 7 '14 at 16:06
@Matthew, please verify the edited version –  lab bhattacharjee Mar 7 '14 at 16:14
That should be a $+$ rather than a comma, right? In the formula right before "and then continue". –  Jack M Mar 7 '14 at 17:38

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

-
Good, and complete. For the purposes of students going farther in mathematics, it is disastrous to keep the mindset of relying on the operation rather than the equivalence relation. When talking about $R/I$ where $R$ is a ring and $I$ is an ideal, or $G/H$ where $\supset H$ are groups, the equivalence relation outlook is essential. –  Lubin Mar 7 '14 at 18:49

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.

-
There's nothing wrong with using $\bmod$ as an operator. –  ShreevatsaR Mar 7 '14 at 16:54
Using mod as an operator loses the properties of the equivalence class that makes it so convenient. For example, you cannot assume $a \mod M + b \mod M = (a + b) \mod M$. –  DanielV Mar 7 '14 at 17:48
@DanielV: Assuming the name "mod" refers to a proper modulus operator and not the much-less-useful "remainder" operator found in many programming languages, and one is not expecting one's numeric type to act as an algebraic ring with a modulus which is not a multiple of M, why can't one assume that (a mod M)+(b mod M) will equal ((a+b) mod M) in cases where the result of the addition is defined? –  supercat Mar 7 '14 at 18:25
Ah, if I understand, you are talking about a $\mathbb{N} \rightarrow \text{Galois}[M]$ operator, yes that would be useful indeed. –  DanielV Mar 8 '14 at 0:02

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

-
Either you meant $\mod 39$ in the first line or $mk$ in the second. –  Mike Miller Mar 8 '14 at 3:45
@Mike Right you are. Thank you. –  iamnotmaynard Mar 8 '14 at 20:56
Glad to help!$\$ –  Mike Miller Mar 8 '14 at 21:37

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

-
While this is a good hint for solving the problem "show that $103^{53} + 53^{103}$ is divisible by 39", this doesn't address the question that was asked ("am I allowed to distribute the mod") at all. –  Magdiragdag Mar 7 '14 at 16:05
@Magdiragdag, added a relevant link –  lab bhattacharjee Mar 7 '14 at 16:10

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.

-