# Modular Arithmetic order of operations

In an assignment, I am given $E_K(M) = M + K \pmod {26}$. This formula is to be applied twice in a formal proof, so that we have $E_a(E_b(M)) =\ ...$. What I'm wondering is; is the original given formula equal to $(M + K)\pmod{26}$, or $M + (K \mod{26})$? This will obviously make a big difference down the line.

I do suspect the first ($(M + K)\pmod{26}$), however I want to be certain before I move forward in my proof.

NB: I did not tag this as homework as this is not actually part of the problem, rather just a clarification.

-
The first (as in, $M+K\pmod{26}$ - just to be clear: this doesn't mean $M+K$ times $\pmod{26}$, which wouldn't make much sense). – user39572 Oct 6 '12 at 1:35
Well, in the event of $M = 27$ and $K = 26$, they could both produce a different result; the first would be $(27 + 26) (mod\ 26) = 53\ mod\ 26 = 1$, the second would be $27 + (26 (mod\ 26)) = 27\ mod\ 26 = 27$. So to me, both do kinda make sense, which is why I ask... if you are certain, you can post that as an answer. – Eric Oct 6 '12 at 1:40
Are you aware of mod as an operator vs. relation? – Bill Dubuque Oct 6 '12 at 1:46
@Julien: You’ve misunderstood Eric’s question. He’s asking whether it means reduce $M+K$ modulo $26$, or reduce $K$ modulo $26$ and then add $M$. – Brian M. Scott Oct 6 '12 at 1:47
@Julien: No, in general they produce different results. See my answer. – Brian M. Scott Oct 6 '12 at 1:51

## 4 Answers

The usual interpretation of would be $E_K(M)$ is equal to $M+K$ if '$\text{mod}\: 26$' is applied to both sides. More generally, putting "$(\text{mod}\: N)$ to the right of a temr or equation usually applies to the whole equation or term. I.e., the following statements hold

$$\begin{eqnarray} 1 &=& 1 + 4 \quad (\text{mod}\: 2) \\ 2 &=& 6 + 2 \quad (\text{mod}\: 2). \end{eqnarray}$$

Note that there's usually a wide blank before the $(\text{mod}\: N)$ term, like in the two equations above. In latex (and thus here) you can insert such a space with \quad. To make it absolutely clear that the equal sign doesn't mean normal equation, people also often use $\equiv$ (\equiv) instead of $=$. The above then becomes

$$\begin{eqnarray} 1 &\equiv& 1 + 4 \quad (\text{mod}\: 2) \\ 2 &\equiv& 6 + 2 \quad (\text{mod}\: 2). \end{eqnarray}$$

-
Interesting, my LaTeX-obsessed teacher used $=$, not $\equiv$, and there is not a big space before the $($. I transposed it exactly as she posted it. This is helpful, though, thanks! – Eric Oct 6 '12 at 1:52

I suspect that what is meant is $(M+K)\bmod 26$, where $\bmod$ is the operator, especially if this is in a cryptographic context. More careful writers reserve the parenthesized notation $\pmod{26}$ for the relation of congruence modulo $26$, using it only in connection with $\equiv$, as in $27\equiv 53\pmod{26}$.

Thus, if $M=K=27$, the intended result is probably $54\bmod 26=2$, not $27+(27\bmod 26)=28$.

-

$$M+K\pmod{26}$$

Your suggestion and use of brackets makes me want to clarify something (just in case):

$$E\equiv M+K\pmod{26}\iff E=M+K+26k,\;\;k\in\mathbb{Z}$$

The mod is not a variable you can operate on (not as written at least).

Edit: it appears I misread the question, although I suppose the $k$ relation above clarifies the order of operations anyway.

-
That iff statement is helpful, but you didn't quite get my question. Thanks for the answer anyway, though! – Eric Oct 6 '12 at 1:53
@Eric Yes, sorry about that. The way it was written I thought you were suggesting multiplication. My fault entirely (or perhaps I can blame it on the late hour...). – user39572 Oct 6 '12 at 1:58

Without further context it is impossible to determine what is intended, because there are many abuses of the mod notation.

However, with high probability, the expression $\rm\: M\!+\!K\ (mod\ 26)\:$ denotes the remainder of $\rm\:M\!+\!K\:$ when divided by $26\,$ (or the entire residue class $\rm\ M\!+\!K+26\,\Bbb Z\:$ containing the remainder).

Your other possible interpretation, $\rm\:M + (K\ mod\ 26),\:$ is much more rare, though it does sometimes occur when discussing parity, e.g. authors may write $\rm\:n\ (mod\ 2)\:$ or $\rm\: n\ mod\ 2\:$ in arithmetical expressions that depend upon the parity of $\rm\:n.$

In the first case one is performing modular arithmetic, i.e. addition modulo $26$. In the second case one is performing integer arithmetic, i.e. normal integer addition. If the ambient context reveals which type of arithmetic is intended, then you can infer the meaning of the notation.

-
"... many abuses of the mod notation." That is absolutely the truth. If everyone would just use the notation correctly... – Eric Oct 6 '12 at 2:45