MathGoldMedalist
Sign InRegister
Back to Toolkit

Toolkit 47

Modular Arithmetic: Definition and Properties

Definition

aa is congruent to bb modulo mm if and only if their difference is divisible by mm:

a≡b(modm)⟺m∣(a−b).a \equiv b \pmod m \quad\Longleftrightarrow\quad m\mid(a-b).

Properties

1.a≡a(modm)1.\quad a\equiv a\pmod m
2.a≡b(modm)⟹b≡a(modm)2.\quad a\equiv b\pmod m \Longrightarrow b\equiv a\pmod m
3.a≡b(modm),b≡c(modm)⟹a≡c(modm)3.\quad a\equiv b\pmod m,\qquad b\equiv c\pmod m \Longrightarrow a\equiv c\pmod m
4.a≡b(modm)⟹{a+c≡b+c(modm),a−c≡b−c(modm),ac≡bc(modm).4.\quad a\equiv b\pmod m \Longrightarrow \begin{cases} a+c\equiv b+c\pmod m,\\ a-c\equiv b-c\pmod m,\\ ac\equiv bc\pmod m. \end{cases}
5.a≡b(modm),c≡d(modm)⟹{a+c≡b+d(modm),a−c≡b−d(modm),ac≡bd(modm).5.\quad a\equiv b\pmod m,\qquad c\equiv d\pmod m \Longrightarrow \begin{cases} a+c\equiv b+d\pmod m,\\ a-c\equiv b-d\pmod m,\\ ac\equiv bd\pmod m. \end{cases}
6.a≡b(modm)⟹an≡bn(modm),n∈Z+6.\quad a\equiv b\pmod m \Longrightarrow a^n\equiv b^n\pmod m,\qquad n\in\mathbb Z^+
7.ac≡bc(modm)⟺a≡b(modmgcd⁡(m,c)).7.\quad ac\equiv bc\pmod m \Longleftrightarrow a\equiv b \pmod{\frac{m}{\gcd(m,c)}}.
8.a≡b(modm),d∣m⟹a≡b(modd).8.\quad a\equiv b\pmod m,\qquad d\mid m \Longrightarrow a\equiv b\pmod d.

Proof

1.

a≡a(modm)a\equiv a\pmod m

Proof.

Since

a−a=0,a-a=0,

and

m∣0,m\mid0,

we have

a≡a(modm).a\equiv a\pmod m.

2.

a≡b(modm)⟹b≡a(modm)a\equiv b\pmod m \Longrightarrow b\equiv a\pmod m

Proof.

If

a≡b(modm),a\equiv b\pmod m,

then

m∣(a−b).m\mid(a-b).

Since

b−a=−(a−b),b-a=-(a-b),

we also have

m∣(b−a).m\mid(b-a).

Therefore,

b≡a(modm).b\equiv a\pmod m.

3.

a≡b(modm),b≡c(modm)⟹a≡c(modm)a\equiv b\pmod m,\qquad b\equiv c\pmod m \Longrightarrow a\equiv c\pmod m

Proof.

Since

a≡b(modm),a\equiv b\pmod m,

we have

m∣(a−b),m\mid(a-b),

and since

b≡c(modm),b\equiv c\pmod m,

we have

m∣(b−c).m\mid(b-c).

Adding these two divisibilities,

m∣(a−c),m\mid(a-c),

so

a≡c(modm).a\equiv c\pmod m.

4.

a≡b(modm)⟹{a+c≡b+c(modm),a−c≡b−c(modm),ac≡bc(modm).a\equiv b\pmod m \Longrightarrow \begin{cases} a+c\equiv b+c\pmod m,\\ a-c\equiv b-c\pmod m,\\ ac\equiv bc\pmod m. \end{cases}

Proof.

Since

m∣(a−b),m\mid(a-b),

we obtain

m∣(a+c)−(b+c),m\mid(a+c)-(b+c),
m∣(a−c)−(b−c),m\mid(a-c)-(b-c),

and

m∣c(a−b)=ac−bc.m\mid c(a-b)=ac-bc.

Therefore,

a+c≡b+c(modm),a+c\equiv b+c\pmod m,
a−c≡b−c(modm),a-c\equiv b-c\pmod m,

and

ac≡bc(modm).ac\equiv bc\pmod m.

5.

a≡b(modm),c≡d(modm)⟹{a+c≡b+d(modm),a−c≡b−d(modm),ac≡bd(modm).a\equiv b\pmod m,\qquad c\equiv d\pmod m \Longrightarrow \begin{cases} a+c\equiv b+d\pmod m,\\ a-c\equiv b-d\pmod m,\\ ac\equiv bd\pmod m. \end{cases}

Proof.

Since

a≡b(modm),a\equiv b\pmod m,

we have

m∣(a−b),m\mid(a-b),

and since

c≡d(modm),c\equiv d\pmod m,

we have

m∣(c−d).m\mid(c-d).

Adding the two divisibilities,

m∣(a+c)−(b+d),m\mid(a+c)-(b+d),

so

a+c≡b+d(modm).a+c\equiv b+d\pmod m.

Subtracting the two divisibilities,

m∣(a−c)−(b−d),m\mid(a-c)-(b-d),

so

a−c≡b−d(modm).a-c\equiv b-d\pmod m.

Also,

m∣c(a−b),m\mid c(a-b),

and

m∣b(c−d).m\mid b(c-d).

Adding these,

m∣(ac−bd),m\mid(ac-bd),

so

ac≡bd(modm).ac\equiv bd\pmod m.

6.

a≡b(modm)⟹an≡bn(modm),n∈Z+a\equiv b\pmod m \Longrightarrow a^n\equiv b^n\pmod m,\qquad n\in\mathbb Z^+

Proof.

Using Property 5 repeatedly,

a≡b(modm),a\equiv b\pmod m,

multiplied by itself nn times gives

an≡bn(modm).a^n\equiv b^n\pmod m.

7.

ac≡bc(modm)⟺a≡b(modmgcd⁡(m,c)).ac\equiv bc\pmod m \Longleftrightarrow a\equiv b \pmod{\frac{m}{\gcd(m,c)}}.

Proof.

Let

d=gcd⁡(m,c),d=\gcd(m,c),

and write

m=m′d,c=c′d,m=m'd,\qquad c=c'd,

where

gcd⁡(m′,c′)=1.\gcd(m',c')=1.

(⇒)(\Rightarrow)

Since

ac≡bc(modm),ac\equiv bc\pmod m,

we have

m∣c(a−b).m\mid c(a-b).

Hence

m′d∣c′d(a−b),m'd\mid c'd(a-b),

so

m′∣c′(a−b).m'\mid c'(a-b).

Since

gcd⁡(m′,c′)=1,\gcd(m',c')=1,

Euclid's Lemma gives

m′∣(a−b).m'\mid(a-b).

Therefore,

a≡b(modm′)=(modmgcd⁡(m,c)).a\equiv b \pmod{m'} = \pmod{\frac{m}{\gcd(m,c)}}.

(⇐)(\Leftarrow)

If

a≡b(modm′),a\equiv b \pmod{m'},

then

m′∣(a−b).m'\mid(a-b).

Multiplying by dd,

m∣d(a−b).m\mid d(a-b).

Multiplying by c′c',

m∣c(a−b),m\mid c(a-b),

which is equivalent to

ac≡bc(modm).ac\equiv bc\pmod m.

8.

a≡b(modm),d∣m⟹a≡b(modd)a\equiv b\pmod m,\qquad d\mid m \Longrightarrow a\equiv b\pmod d

Proof.

Since

a≡b(modm),a\equiv b\pmod m,

we have

m∣(a−b).m\mid(a-b).

Because

d∣m,d\mid m,

it follows that

d∣(a−b).d\mid(a-b).

Therefore,

a≡b(modd).□a\equiv b\pmod d. \quad\square