Prove monoalphabetic cipher is a valid symmetric cipher I should prove mathematically that:

$D_k(E_k(p))=p$

I know

$E_k(p)=c=(p+k)\bmod26$

and

$D_k(c)=p=(c-k)\bmod26$

Substituting the two formulas to the initial assertion I have

$((p+k)\bmod26-k)\bmod26=p$

And applying the $\bmod$ property twice I have

$((p \bmod26+k \bmod26)\bmod26)-k)\bmod26=p$
$((p\bmod26+k\bmod26)\bmod26)\bmod26-k\bmod26)\bmod26=p$

But from here? How can I get rid of all that bunch of $\bmod$ to have $p$?
The lemma you need for this is that $$((a \bmod m) + b) \bmod m = (a + b) \bmod m \tag{1}$$ for all integers $a$, $b$ and for all positive integers $m$.  In other words, this lemma says that, if you're going to add (or subtract) a bunch of numbers together and then reduce the sum modulo $m$, it doesn't matter whether or not you reduce any (or all) of the summands modulo $m$ first.



The easiest (and most usefully generalizable) way to prove the lemma (1) above is via the notion of modular congruence.  Basically, we define $a$ and $b$ to be congruent modulo $m$, written as $a \equiv b \pmod m$, if $a = b + km$ for some integer $k$.  From this definition, it immediately follows that $$(a \bmod m) \equiv a \pmod m$$ and, in fact, that $$(a \bmod m) = (b \bmod m) \iff a \equiv b \pmod m.$$

We can also show that the modular congruence relation $\equiv$ obeys many of the same algebraic laws as normal equality.  In particular, we can show that it is transitive, i.e. that $$a \equiv b \text{ and } b \equiv c \implies a \equiv c \pmod m,$$ and that it is compatible with addition in the sense that $$a \equiv b \iff a + c \equiv b + c \pmod m.$$

Applying these properties of modular congruence, we can see that $(a \bmod m) \equiv a \pmod m$ implies $(a \bmod m) + b \equiv a + b \pmod m$, which then implies lemma (1).


  Bonus exercise: Also show that modular congruence is compatible with multiplication in the sense that $$a \equiv b \implies ac \equiv bc \pmod m.$$




Now that we've proven lemma (1), the rest is simple: $$\begin{aligned}
D_k(E_k(p)) &amp;= ((p + k) \bmod 26) - k) \bmod 26 \\
&amp;= (p + k - k) \bmod 26 \\
&amp;= p \bmod 26.
\end{aligned}$$  If $0 \le p &lt; 26$, then $p \bmod 26 = p$, and we're done.  (We do need to make this additional assumption for the encryption to be reversible, since it would not hold if $p$ could take other values!)



Of course, we could've also skipped lemma (1) entirely, and just appealed directly to modular congruence, and in particular to the fact that $$E_k(p) = (p + k) \bmod 26 \equiv p + k \pmod{26}\,\,$$ and $$D_k(c) = (c - k) \bmod 26 \equiv c - k \pmod{26},$$ from which it follows that $$D_k(E_k(p)) \equiv p + k - k = p \pmod{26}.$$