Modulus

Basic Rules

Let $a\equiv a^{\prime }\mathrm{mod}n$ and $b\equiv b^{\prime }\mathrm{mod}n$. Then

• $a+b\equiv a^{\prime }+b^{\prime }\mathrm{mod}n$
• $ab\equiv a^{\prime }{b}^{\prime }\mathrm{mod}n$
• $a^r\equiv (a^{\prime }{)}^r\mathrm{mod}n$ where $r\in {\mathbb{Z}}_{>0}$.

It is not generally true that $a^r\equiv a^{r^{\prime }}\mathrm{mod}n$.

Example 1

$$417\cdot 22\mathrm{mod}10$$

This becomes

$$7\equiv 417\mathrm{mod}102\equiv 22\mathrm{mod}10$$

such that

$$7\cdot 2\mathrm{mod}10\equiv 4$$

Example 2

$$333333+666\mathrm{mod}3$$

becomes $0$, since both are divisible by $3$.

Example 3

$$7^{202320232023}\mathrm{mod}6$$

So, since $7\mathrm{mod}6\equiv 1$, we have that

$$1^{202320232023}\mathrm{mod}6\equiv 1$$

Example 4 (2.5.9)

Fix positive integers $k,n$. Suppose $a,a^{\prime }$ are integers such that $a\equiv a^{\prime }\mathrm{mod}n$. It is not true in general that $k^a\equiv k^{a^{\prime }}\mathrm{mod}n$. Show is by example.

Let $n=5,k=3,a^{\prime }=2,a=17$. Then

$$17\equiv 2\mathrm{mod}5$$

But then as $3$ is periodic as $3,4,2,1$, we have that

$$3^{17}\mathrm{mod}5\equiv 3$$

And

$$3^2\mathrm{mod}5\equiv 4$$

and so

$$3\ne 4$$

We are done.

Example 5 (2.6.15)

Explain why $2$ is not invertible $\mathrm{mod}4$.

Suppose by contradiction it is. Thus, $\exists x\in \mathbb{Z}$ where $2x\equiv 1\mathrm{mod}4$. But when $x$ is even ($x=2k$), then $4k\equiv 0\mathrm{mod}4$, a contradiction. If is odd where $x=2k+1$, Then $4k+2\equiv 0+2\mathrm{mod}4$ which is not $1$, another contradiction.

Example 6

There exist three odd integers $a,b,c$ such that every integer $x$ is congruent mod $3$ to either $a$ or $b$ or $c$.

True. Let $a=3,b=1,c=2$. We would let $a=0$, but we must find an odd integer. Fortunately $3\equiv 0\mathrm{mod}3$.

Consider 4 integers, but with $a,b,c,d$. False. $a,b,c,d$ must be $0,1,2,3$ respectively. But then $0$ must be congruent to some odd multiple of $4$. Since $4$ is even, this cannot be true.