Congruence

Fix an integer

m

called the modulus, then say

a \equiv b (\mod m)

if and only if

m | b - a

It is not immediately clear why we prefer the above definition, it's most important property follows below:

congruence iff same remainder

a, b \in ℤ

are congruent modulo

m

if and only if

a % m

= b % m

note: this means that $a$ and $b$ have the same remainder upon division by $m$

Suppose that $a \equiv b (\mod m)$ , so we know $m | b - a$ , then we can write $b = k_{b} m + r_{b}$ and $a = k_{a} m + r_{a}$ so that $b - a = m \cdot (k_{b} + k_{a}) + k_{b} - k_{a}$ thus $m | k_{b} - k_{a}$ .

Notice that $0 \leq k_{a}, k_{b} < | m |$ also we know that $k_{a} \neq k_{b}$ therefore $k_{b} - k_{a} \neq 0$ so then $- | m | < k_{b} - k_{a} < | m |$

Congruence Commutes

Let

a, b, m \in ℤ

then

a \equiv b (\mod m) ⟺ b \equiv a (\mod m)

Division iff Congruent Mod 0

Let

a, b \in ℤ

such that

a \neq 0

, then

a | b ⟺ b \equiv 0 (\mod a)

a | b

if and only if

a | b - 0

iff

0 \equiv b (\mod a)

iff

b \equiv 0 (\mod a)

as needed.

Congruence is Transitive

Let

a, b, c, m \in ℤ

such that

a \equiv b (\mod m)

and

b \equiv c (\mod m)

, then we have that

a \equiv c (\mod m)

TODO

Sum of Two Congruent Numbers are Congruent

Suppose that

a \equiv b (\mod m)

and that

c \equiv d (\mod m)

then we know that

a + c \equiv b + d (\mod m)

Product of Two Congruent Numbers is Congruent

Suppose that

a \equiv b (\mod m)

and that

c \equiv d (\mod m)

then we know that

a c \equiv b d (\mod m)

Note that we don't have the same theorem about division, we can observe that in general this is false, because any odd square has remainder 1, upon division by four, so that $5^{2} \equiv 3^{2} (\mod 4)$ but we can see that $5 \equiv 3 (\mod 4)$ is false.

Congruent Numbers raised to Congruent Powers may not be Congruent

Suppose that

a \equiv b (\mod n)

and

c \equiv d (\mod n)

, then its NOT true that

a^{c} \equiv b^{d} (\mod n)

Consider

2 \equiv 5 (\mod 3)

but then

2^{5} \equiv 2

whereas

5^{2} \equiv 1

2^{5} \equiv̸ 5^{2} (\mod 3)

If two Two Numbers are Congruent, they are still Congruent mod a divisor of the Original Mod

Suppose that

a \equiv b (\mod n)

and

m | n

then

a \equiv b (\mod m)

Since

a \equiv b (\mod n)

then we know that

n | b - a

but also

m | n

so that

m | b - a

therefore

a \equiv b (\mod m)

as needed.

Note that if instead we required that $n | m$ then the above would not be true because we see that $3 \equiv 6 (\mod 3)$ but $3 \equiv̸ 6 (\mod 6)$

If Two Numbers are Congruent Using Two Different Moduli they are Congruent Using the LCM

Suppose that

a \equiv b (\mod n)

and that

a \equiv b (\mod m)

then

a \equiv b (\mod lcm (n, m))

We have that

m, n | a - b

but the definition of the LCM then states that

l c m (n, m) | a - b

Switching Prime Powers

Let

p \neq q \in ℙ

then

p^{q - 1} + q^{p - 1} \equiv 1 (\mod p q)

FLT tells us that

p^{q - 1} \equiv 1 (\mod q) and q^{p - 1} \equiv 1 (\mod p)

but since

p - 1, q - 1 \geq 1

then we know that

q^{p - 1} \equiv 0 (\mod q) and p^{q - 1} \equiv 0 (\mod p)

therefore we know that

p^{q - 1} + q^{p - 1} \equiv 1 (\mod q) and q^{p - 1} + p^{q - 1} \equiv 1 (\mod p)

since

lcm (p, q) = p q \cdot \gcd (p, q)

and we know that

p \neq q \in ℙ

then

\gcd (p, q) = 1

so that

lcm (p, q) = p \cdot q

then we conclude that

p^{q - 1} + q^{p - 1} \equiv 1 (\mod p q)

a p q

Suppose that

a \in ℤ

and that

p \neq q \in ℙ

, then

a^{p q} - a^{p} - a^{q} + a \equiv 0 (\mod p q)

By FLT, we know that

a^{p q} - a^{p} - a^{q} + a \equiv {(a^{p})}^{q} - a^{p} - a^{q} + a \equiv a^{q} - a - a^{q} + a = 0 (\mod p)

and symetrically the same thing occurs mod

q

therefore

a^{p q} - a^{p} - a^{q} + a \equiv 0 (\mod p q)

Division by a Common Factor Maintains Congruence

Suppose that

a \equiv b (\mod m)

then if

k | a, b, m

then we have that

\frac{a}{k} \equiv \frac{b}{k} (\mod \frac{m}{k})

Recall that

\frac{a}{k} \equiv \frac{b}{k} (\mod \frac{m}{k})

iff

\frac{m}{k} | \frac{a}{k} - \frac{b}{k}

but we know that statement is true because since

m | a - b

and we by linearity we know that

k | a - b

therefore it holds true.

Division by a Common Factor Maintains Congruence if Mod is Divided by GCD

Let

a, b, m, k \in ℤ

such that

k \neq 0

and suppose that

a \equiv b (\mod m)

then if

k | a, b

then

\frac{a}{k} \equiv \frac{b}{k} (\mod \frac{m}{\gcd (m, k)})

Let $g : = \gcd (m, k)$ our goal is to prove that $\frac{m}{g} | \frac{a}{k} - \frac{b}{k}$ , towards this note that we have $a \equiv b (\mod m)$ which means that $m | a - b$ so there is some $r \in ℤ$ such that $a - b = m r$ therefore dividing by $g \neq 0$ we have $\frac{a - b}{g} = \frac{m}{g} r$

Recall that we want $k$ in the denominator, to get there we recall that $g | k$ and so there is some $j \in ℤ$ such that $k = g j$ , since $k \neq 0$ then $g j \neq 0$ so $j \neq 0$ thus we divide our previous equation by $j$ to obtain $\frac{a - b}{g j} = (\frac{m}{g} r) \frac{1}{j} ⟺ \frac{a - b}{k} = (\frac{m}{g} r) \frac{1}{j}$ Since $k | a, b$ then $k | a - b$ so $\frac{a - b}{k} \in ℤ$ thus $(\frac{m}{g} r) \frac{1}{j} \in ℤ$ and therefore $j | \frac{m}{g} r$ .

Note that $j | k$ and $\frac{m}{g} | m$ therefore $\gcd (j, \frac{m}{g}) = 1$ therefore $j | r$ so that $\frac{r}{j} \in ℤ$ thus we have the equation $\frac{a - b}{k} = \frac{a}{k} - \frac{b}{k} = \frac{m}{g} \frac{r}{j}$ where we know the left hand side is an integer, $\frac{r}{j}$ is and so is $\frac{m}{g}$ therefore $\frac{m}{g} | \frac{a}{k} - \frac{b}{k}$ so that $\frac{a}{k} \equiv \frac{b}{k} (\mod m)$ as needed.

Multiplicative Cancellation if Mod Prime

Suppose that

p

is prime and that

k a \equiv k b (\mod p)

and

p ∤ k

then

a \equiv b (\mod p)

Since

p ∤ k

then we know that

\gcd (p, k) = 1

therefore the result follows from the previous proposition.

n Consecutive Numbers have Unique Remainders Mod n

For any

m \in ℕ_{1}

\forall x, y \in [0, \dots m - 1], (x \neq y ⟺ x \equiv̸ y (\mod m))

$⟹$ Suppose that $x \neq y$ but that $x \equiv y (\mod m)$ for the sake of contradiction, without loss of generality assume that $x > y$ . Since they're congruent we have $m | x - y$ but we know that $x - y \leq m - 1 - 0 = m - 1$ but if $m | x - y$ we have $m \leq x - y \leq m - 1$ so $m \leq m - 1$ which is impossible, therefore we must have that $x \equiv̸ y (\mod m)$ .

$⟸$ Now suppose that $x \equiv̸ y (\mod m)$ therefore $x % m \neq y % m$ but since $x, y \in [0, \dots, m - 1]$ then $x = x % m$ and $y = y % m$ therefore $x \neq y$ as needed.

When a Linear Modular Equation has a Solution

The equation

a x \equiv b (\mod m)

has a solution iff

\gcd (a, m) | b

Note that

a x \equiv b (\mod m)

iff

m | a x - b

so there is some

k \in ℤ

such that

a x - b = m k

so that

a x - m k = b

this has a solution iff

\gcd (a, m) | b

Relatively Prime Modular Equation has a Solution

Suppose that we have the equation:

a x \equiv b (\mod m)

where

\gcd (a, m) = 1

then it has a solution.

Since

\gcd (a, m) = 1 | b

it has a solution.

Modular Inverse

Given

a, m \in ℤ

we say that an integer

x \in ℤ

is a the modular inverse for

a

mod

m

when:

a \cdot x \equiv 1 (\mod m)

When a given number has an inverse we say that it is invertible.

When a Rational Can be Converted to a Modular Inverse

Suppose that

a, b \in ℤ

and

m \in ℕ_{1}

such that

b

is invertible mod

m

and

\frac{a}{b} \in ℤ

then:

a \cdot b^{- 1} \equiv \frac{a}{b} (\mod m)

where the right hand side is interpreted as division of integers.

Note that since

b | a

then there is some

k \in ℤ

such that

a = b k

therefore

a \equiv b k (\mod p) ⟺ b^{- 1} a \equiv k ⟺ a b^{- 1} \equiv \frac{a}{b} (\mod p)

2p Choose p

Prove that

(\binom{2 p}{p}) \equiv 2 (\mod p)

We have that

(\binom{2 p}{p}) = \frac{(p + 1) \dots (p + p - 1) (2 p)}{p!} = \frac{(p + 1) \dots (p + p - 1) 2}{(p - 1)!} \in ℤ

therefore

\begin{matrix} \frac{(p + 1) \dots (p + p - 1) 2}{(p - 1)!} & a m p; \equiv (p + 1) \dots (p + p - 1) 2 {[(p - 1)!]}^{- 1} \\ a m p; \equiv 2 (p - 1)! {[(p - 1)!]}^{- 1} \\ a m p; \equiv 2 (\mod p) \end{matrix}

Every Non Zero Number is Invertible Mod a Prime

For any

p \in ℙ

a \in ℤ

such that

p ∤ a

there exists

b \in [1, \dots, p - 1]

such that

a b \equiv 1 (\mod p)

Consider the equation

a x \equiv 1 (\mod p)

, since

\gcd (a, p) = 1

then it has a solution, as needed.

A Linear Modular Equation with a Solution has GCD many Solutions

Suppose that

a x \equiv b (\mod m)

has a solution

x_{0}

, then it has exactly

g : = \gcd (a, m)

solutions mod

m

. Moreover the unique solutions are given by the remainders of

x_{0}, x_{0} + \frac{1 m}{g}, x_{0} + \frac{2 m}{g}, \dots, x_{0} + \frac{(g - 1) m}{g}

when taken mod

m

Since it has a solution, we have an $x_{0} \in ℤ$ such that $a x_{0} \equiv b (\mod m)$ , so therefore $m | a x_{0} - b$ so that $a x_{0} - b = m k$ for some $k \in ℤ$ therefore $a x_{0} + m (- k) = b$ .

Recall that we have a method of obtaining more solutions once we have one, and hence are given by $(x_{0}, - k) + (\frac{m}{g}, - \frac{a}{g}) t, where t \in ℤ$ Note that for each new solution $x, y$ it satisfies $a x + m y = b$ so that $a x - b = - y m$ so that $m | a x - b$ so that $a x \equiv b (\mod m)$ , therefore we only need to observe the $x$ component of each of solutions obtained from the equation

With this we observe the solutions: $\dots x_{0} - \frac{m}{g}, x_{0}, x_{0} + \frac{1 m}{g}, x_{0} + \frac{2 m}{g}, \dots, x_{0} + \frac{(g - 1) m}{g}, x_{0} + \frac{g m}{g} = x_{0} + m, \dots$ and note that for any $t \in ℤ$ such that $t \geq g$ then $t = q g + r$ where $r \in [0, \dots g - 1]$ $x_{0} + \frac{t m}{g} = x_{0} + q m + \frac{r}{g} \equiv x_{0} + \frac{r}{g} (\mod m)$ which is to say that it is congruent to a solution of the form $x_{0} + \frac{j m}{g}$ where $j \in [0, \dots, g - 1]$ similarly any solution that is of the form $x_{0} + \frac{n m}{g}$ where $n < 0$ can be turned into one of these solutions by repetitively adding $m$ .

This shows that the entire solution set mod $m$ is given by $x_{0}, x_{0} + \frac{1 m}{g}, x_{0} + \frac{2 m}{g}, \dots, x_{0} + \frac{(g - 1) m}{g}$ we'll now verify that every pair of solutions are incongruent mod $m$ to show that there are $g$ total solutions.

So suppose for the sake of contradiction that $x_{0} + \frac{l m}{g} \equiv x_{0} + \frac{p m}{g} (\mod m)$ where $l, p \in [0, \dots, g - 1]$ and without loss of generality $l > p$ so that $m | \frac{l m}{g} - \frac{p m}{g} = \frac{m}{g} (l - p)$ since $l, p \in [0, \dots g - 1]$ then $l - p \leq g - 1$ so that $\frac{m}{g} (l - p) < \frac{m}{g} g = m$ which means that $m$ divides a number smaller than it, which is impossible so that $x_{0} + \frac{l m}{p} \equiv̸ x_{0} + \frac{p m}{g}$ as needed.

Note that modulo a prime, since the gcd is always one, then this shows that every element has a unique inverse mod p.

24 and 60

Find all incongruent solutions of the linear congruence given by

24 x \equiv 60 (\mod 102)

First we verify that the above has a solution, since $102 = 17 \cdot 6$ , then $\gcd (24, 102) = 6$ and so $\gcd (24, 102) | 60$ , so we deduce that $24 x \equiv 60 (\mod 102)$ has a solution, call it $x_{0}$ .

Since it has a solution, then we know that it actually has $\gcd (24, 102) = 6$ solutions explicitly given by $x_{0} + (\frac{102}{6}) k$ for $k \in [0, \dots, 5]$ . Now to actually find a solution, we can divide through by $6$ which yields $4 x \equiv 10 (\mod 17)$ since $17$ is prime, then we know that $4$ has an inverse, we can see that $- 4$ works, so that $x \equiv - 40 \equiv 11 (\mod 17)$ so our solutions are given by $11 + 17 k$ for $k \in [0, \dots, 5]$ mod $102$

Chinese Remainder

Suppose that for some

l \in ℕ_{1}

we have that

x \equiv c_{i} (\mod m_{i})

for each

i \in [1, \dots, l]

such that for any

i < j \in [1, \dots, l]

we have

\gcd (m_{i}, m_{j}) = 1

, then there is a unique

x

satisfying the modular equations

(\mod \prod_{i = 1}^{l} m_{i})

Set $M = \prod_{i = 1}^{l} m_{i}$ , then clearly we have that $M \equiv 0 (\mod m_{i})$ . Now recall the following fact, and that it can be extended to finite products by induction which shows that $\gcd (\frac{M}{m_{j}}, m_{j}) = 1$ for any $j \in [1, \dots, l]$ . Therefore we obtain a solution to the equation $\frac{M}{m_{j}} x \equiv 1 (\mod m_{j})$ , let this solution be denoted by $x_{j}$ .

As just discussed we obtained a solution $x_{j}$ such that $\frac{M}{m_{j}} x_{j} \equiv 1 (\mod m_{j})$ , in other words $\frac{M}{m_{j}} x_{j} c_{j} \equiv c_{j} (\mod m_{j})$ and so we've found $l$ different solutions to each of the congruence equations we required, but we need to find one solution to all of them.

Note that $\frac{M}{m_{j}} \equiv 0 (\mod m_{i})$ for any $i \neq j$ so that $\frac{M}{m_{j}} x_{j} c_{j} \equiv 0 (\mod m_{i})$ as well, with this fact we see that $S : = \sum_{i = 1}^{l} \frac{M}{m_{j}} x_{j} c_{j}$ has the following property $S \equiv 0 + 0 + \dots c_{j} + 0 + 0 \equiv c_{j} (\mod m_{j})$ in other words using $x = S$ works.

We now show that the solution is unique. Suppose that $y$ is another solution to all of the modular equations then we'll prove that $x \equiv y (\mod \prod_{i = 1}^{l} m_{i})$

Seven Divides Ones and Threes

Show that

7 | (111^{333} + 333^{111})

$111 = 7 \cdot 15 + 6$ therefore $111 \equiv 6 \equiv - 1 (\mod 7)$ therefore $111^{2 k + 1} \equiv - 1$ so therefore $111^{333} \equiv - 1 (\mod 7)$ .

Now note that $333 \equiv 3 (111) \equiv 3 (- 1) \equiv - 3 (\mod 7)$ , consider the following $\begin{matrix} - 3^{1} & a m p; \equiv - 3 (\mod 7) \\ - 3^{2} & a m p; \equiv 2 (\mod 7) \\ - 3^{3} & a m p; \equiv 1 (\mod 7) \end{matrix}$ therefore ${(- 3)}^{3 k + i} \equiv {\begin{matrix} - 3 & a m p; if i = 1 \\ 2 & a m p; if i = 2 \\ 1 & a m p; if i = 0 \end{matrix}$ since the sum of the digits of $111 = 3$ then $3 | 111$ and therefore $3^{111} \equiv 1$ therefore $111^{333} + 333^{111} \equiv - 1 + 1 \equiv 0$ therefore $7 | 111^{333} + 333^{111}$ as needed.

Alternating Congruence Again

Prove that

39 | (53^{103} + 103^{53})

Note that

53 = 39 + 14

thus

53 \equiv 14 (\mod 39)

, looking at

14^{2} = (10 + 4) 14 = 140 + 56 = 196

, then since

39 \cdot 5 = (40 - 1) 5 = 200 - 5 = 195

then we see that

196 = 39 \cdot 5 + 1

so that

14^{2} \equiv 1 (\mod 39)

therefore we have that

14^{k} \equiv {\begin{matrix} 14 & a m p; if k odd \\ 1 & a m p; if k even \end{matrix}

therefore

53^{103} \equiv 14^{103} \equiv 14

. Now we look at

103 = 2 \cdot 39 + 25

so that

103 \equiv 25

now

25^{2} = 625

since we see that

16 \cdot 39 = 16 (40 - 1) = (400 + 240) - 16 = 640 - 16 = 624

then

625 = 16 \cdot 39 + 1

so that

25^{2} \equiv 1

so we deduce that

25^{k} \equiv {\begin{matrix} 25 & a m p; if k odd \\ 1 & a m p; if k even \end{matrix}

therefore

103^{53} \equiv 25^{53} \equiv 25

so then

53^{103} + 103^{53} \equiv 14 + 25 \equiv 39 \equiv 0

therefore we know that

39 | 53^{103} + 103^{53}

43 Divides a Sum of Powers of 6 and 7

Show that

43 | (6^{n + 2} + 7^{2 n + 1})

Note that

\begin{matrix} 6^{1} & a m p; \equiv 6 (\mod 43) \\ 6^{2} & a m p; \equiv 36 (\mod 43) \\ 6^{3} & a m p; \equiv 3 \cdot 36 \equiv 130 + 36 \equiv 216 (\mod 43) \end{matrix}

Note that $216 = 43 \cdot 5 + 1$ therefore $6^{3} \equiv 1 (\mod 43)$ therefore the modular power sequence is given by $(6, 36, 1, 6, 36, 1, \dots)$ . Therefore if we look at $a_{n} = 6^{n + 2}$ then $(a_{n}) = (1, 6, 36, 1, 6, 36, \dots)$

Now we'll look at $7$ power sequence mod $43$ we have $\begin{matrix} 7 & a m p; \equiv 7 (\mod 43) \\ 7^{2} & a m p; \equiv 49 \equiv 6 (\mod 43) \\ 7^{3} & a m p; \equiv 6 \cdot 7 \equiv 42 \equiv - 1 (\mod 43) \\ 7^{4} & a m p; \equiv - 1 \cdot 7 \equiv - 7 (\mod 43) \\ 7^{5} & a m p; \equiv 7^{3} 7^{2} \equiv (- 1) 6 (\mod 43) \\ 7^{6} & a m p; \equiv 7 (- 6) \equiv - 42 \equiv 1 (\mod 43) \end{matrix}$ therefore it's power sequence mod $43$ is $(b_{n}) = (7, 6, - 1, - 7, - 6, 1, 7, 6, - 1, - 7, - 6, 1, \dots)$ , therefore the power sequence of $7^{2 n + 1}$ is given by $(c_{n}) = (- 1, - 6, 7, - 1, - 6, 7, \dots)$ , therefore $x_{n} = 6^{n + 2} + 7^{2 n + 1}$ is given by $\begin{matrix} (x_{n}) & a m p; = (1, 6, 36, 1, 6, 36, \dots) \\ a m p; + (- 1, - 6, 7, - 1, - 6, 7, \dots) \\ a m p; = (0, 0, 43, 0, 0, 43, \dots) \end{matrix}$ Since $x_{n} \equiv 0 (\mod 43)$ for every $n$ as needed.

Remainder of a Sum of Powers

Find

(\sum_{i = 1}^{100} i^{5}) % 4

For

i

odd, then recall that

i^{2}

is an odd perfect square and thus

i^{2} % 4 = 1

therefore

i^{5} = i^{2} i^{2} i = i

, also when

i

is even, then

i^{5} % 4 = 0

therefore we know that

(\sum_{i = 1}^{100} i^{5}) \equiv 1 + 3 + 5 + \dots + 2 (50) - 1 = 50^{2}

using this fact since

50 % 4 = 2

then we know that

50^{2} % 4 = 0

so we deduce that

(\sum_{i = 1}^{100} i^{5}) % 4 = 0

Remainder of a Sum of Factorials

Determine

(\sum_{i = 1}^{100} i!) % 15

Observe that for any

i \geq 5

we see that

15 = 3 \cdot 5 | i!

therefore we reduce it to

(\sum_{i = 1}^{100} i!) \equiv \sum_{i = 1}^{4} i! (% 15)

But we know that

1! + 2! + 3! + 4! = 33 \equiv 3 (% 15)

so that

(\sum_{i = 1}^{100} i!) \equiv 3 (% 15)

Modular Inverse iff GCD 1

Suppose that

a, m \in ℤ

and that

a

has a modular inverse mod

m

, iff

\gcd (a, m) = 1

$⟹$ We know that $a \cdot x \equiv 1 (\mod m)$ therefore by definition $m | (1 - a \cdot x)$ therefore $1 - a x = k \cdot m$ for some $k \in ℤ$ .

Therefore $x a - k m = 1$ , so now suppose that $g = \gcd (a, m)$ , so by definition $g | a$ and $g | m$ so that $g | x a - k m = 1$ which implies that $g = 1$ as needed.

$⟸$ We have some $s, t \in ℤ$ such that $1 = \gcd (a, m) = a s + m t$ so that $1 - a s = m t$ which means that $m | 1 - a s$ so that by definition we have that $a s \equiv 1 (\mod m)$ which means that $s$ is $a$ 's inverse mod $m$ .

Not Relatively Prime iff No Modular Inverse

\gcd (a, m) \neq 1

iff

a

doesn't have an inverse mod

m

This follows by the contra-positive of the above.

Complete System of Residues Modulo n

A collection of

R = {r_{1}, \dots, r_{n}} \subseteq ℤ

is said to be a complete system of residues modulo $n$ if they are pairwise incongruent modulo

n

, meaning that for any

x, y \in R

, if

x \neq y

then

x \equiv̸ y (\mod n)

Equality is the Same as Congruent in a Complete System of Residues Modulo n

Suppose that

R \subseteq ℤ

is a complete system of residues modulo

n

, then for any

x, y \in R

x = y ⟺ x \equiv y (\mod n)

⟹

Suppose that

x = y

therefore we have that

x \equiv y (\mod n)

⟸

Suppose that

x \equiv y (\mod n)

we want to show that

x = y

, but if it was that

x \neq y

then by the definition of complete system of residues we would have

x \equiv̸ y (\mod n)

which would be a contradiction, therefore

x = y

Complete and Incomplete Systems Modulo n

Prove that

0, 2^{1}, \dots, 2^{9}

is a complete system of residues modulo

11

but

0, 3^{1}, \dots, 3^{9}

is not.

Suppose for the sake of contradiction that the former was not a complete system, before doing anything else note that $0 \equiv̸ 2^{z} (\mod 11)$ for any $z \in [1, \dots 9]$ since $11 ∤ 2^{z}$ and therefore instead there would exist some $x, y \in [0, \dots 9]$ such that $x \neq y$ and that $2^{x} \equiv 2^{y} (\mod 11)$ therefore $11 | 2^{x} - 2^{y}$ and without loss of generality assume that $x > y$ then $2^{x} - 2^{y} = 2^{y} (2^{x - y} - 1)$ , since $11$ is prime then $11 | 2^{y}$ or $11 | 2^{x - y} - 1$ , we know that $11 | 2^{y}$ is impossible as noted before so we must have that $11 | 2^{x - y} - 1$ .

We'll show that $11 | 2^{x - y} - 1$ also leads to a contradiction, because if we look at $2$ 's power sequence modulo $11$ we see that it is $(2, 4, 8, 5, - 1, - 2, - 4, - 8, - 5, 1)$ therefore since $x - y \in [0, \dots, 9]$ and the smallest integer such that $2^{k} \equiv 1$ is $k = 10$ then $2^{x - y} \equiv̸ 1$ and thus is in contradiction with the fact that $11 | 2^{x - y} - 1 ⟺ 2^{x - y} \equiv 1 (\mod 11)$ . Therefore our assumption is false and so the former is a complete system of residues.

Following a similar thread we note that $3^{k} \equiv̸ 0 (\mod 11)$ which is impossible by the uniqueness of the prime factorization. We want to find some $x, y \in [0, \dots 9]$ such that $3^{x} \equiv 3^{y} (\mod 11)$ again without loss of generality assume that $x > y$ and therefore we have $11 | 3^{x} - 3^{y} = 3^{y} (3^{x - y} - 1)$ since $11$ is prime then it divides one of the factors, but as just noted the factor it divides must be $3^{x - y} - 1$ by looking at $3$ 's power sequence modulo $11$ we get some insight $3, 9, 5, 4, 1, 3, 9, 5, 4, 1, \dots$ so if $x - y = 5$ then $11 | 3^{x - y} - 1$ so let $y = 1$ and $x = 6$ therefore $3^{6} \equiv 3^{1} (\mod 11)$ and we've proven that the latter is not a complete system of residues.

A Complete System of Residues Modulo n Hits all Possible Residues

Suppose that

r_{1}, r_{2}, \dots, r_{n}

is a complete system of residues modulo

n

, then prove that for each

r \in [0, \dots, n - 1]

there exists some

i \in [1, \dots n]

such that

r_{i} \equiv r (\mod n)

Moreover this mapping

f : R \to [0, \dots, n - 1]

is a bijection.

Suppose that for the sake of contradiction that there exists some

r \in [0, \dots, n - 1]

such that no

r_{i}

was congruent to, then:

X = {r_{i} % n : i \in [1, \dots, n]} \subset [0, \dots, n - 1]

therefore we deduce that

| X | < n

therefore there must exist some

i, j \in [1, \dots, n]

such that

i \neq j

and

r_{i} % n = r_{j} % n

but that's a contradiction since the

r_{i}

's are pairwise incongruent therefore it must be that

X = [0, \dots, n - 1]

therefore for any

r \in [0, \dots, n - 1]

there exists some

r_{j} \in X

such that

r_{j} \equiv r (\mod n)

As per the statement the above mapping is denoted by $f : R \to [0, \dots, n]$ what we've shown is that $im (f) = [0, \dots, n - 1]$ and since $| dom (f) | = | im (f) | = | ran (f) |$ then $f$ is a bijection.

Note the mapping $f (r_{i})$ is simply $r_{i} % n$ .

The Multiples of a Complete System of Residues Mod

n

is still a Complete System of Residues Mod

n

Suppose that

R = {r_{1}, r_{2}, \dots r_{n}}

is a complete system of residues modulo

n

and

a \in ℤ

such that

\gcd (a, n) = 1

then

A = {a r_{1}, a r_{2}, \dots, a r_{n}}

is a complete system of residues modulo

n

Let

a r_{i}, a r_{j} \in A

such that

i \neq j

, since

R

is a complete system of residues, we know that

r_{i} \equiv̸ r_{j} (\mod n)

, now suppose for the sake of contradiction that

a r_{i} \equiv a r_{j} (\mod n)

, then since

\gcd (a, n) = 1

we have

r_{i} \equiv r_{j} (\mod \frac{n}{1})

which is a contradiction, therefore we must have

a r_{i} \equiv̸ a r_{j} (\mod n)

as needed.

Product of Non-Zero Residues Yields Factorial

Suppose that

R = {r_{1}, r_{2}, \dots r_{n}}

is a complete system of residues modulo

n

such that

r_{n} % n = 0

, then

\prod_{i = 1}^{n - 1} r_{i} \equiv (n - 1)! (\mod n)

Recall that there is a unique

r \in [0, \dots, n - 1]

for each

r_{i}

such that

r_{i} \equiv r

. In this case since we've removed

r_{n}

then there is a unique

r \in [1, \dots, n - 1]

, let this mapping be denoted as

f : R \to [1, \dots, n]

since it is a bijection then we note that

\begin{matrix} \prod_{i = 1}^{n - 1} r_{i} & a m p; \equiv \prod_{i = 1}^{n - 1} f (r_{i}) \\ a m p; \equiv \prod_{i = 1}^{n - 1} i \\ a m p; \equiv (n - 1)! \end{matrix}

as needed.

There are 22 Possibilities for the Last Two Digits of a Square

As per title.

We compute

\begin{matrix} 0^{2} = 0 & a m p; \equiv 0 (\mod 100) \\ 1^{2} = 1 & a m p; \equiv 1 (\mod 100) \\ 2^{2} = 4 & a m p; \equiv 4 (\mod 100) \\ 3^{2} = 9 & a m p; \equiv 9 (\mod 100) \\ 4^{2} = 16 & a m p; \equiv 16 (\mod 100) \\ 5^{2} = 25 & a m p; \equiv 25 (\mod 100) \\ 6^{2} = 36 & a m p; \equiv 36 (\mod 100) \\ 7^{2} = 49 & a m p; \equiv 49 (\mod 100) \\ 8^{2} = 64 & a m p; \equiv 64 (\mod 100) \\ 9^{2} = 81 & a m p; \equiv 81 (\mod 100) \\ 10^{2} = 100 & a m p; \equiv 0 (\mod 100) \\ 11^{2} = 121 & a m p; \equiv 21 (\mod 100) \\ 12^{2} = 144 & a m p; \equiv 44 (\mod 100) \\ 13^{2} = 169 & a m p; \equiv 69 (\mod 100) \\ 14^{2} = 196 & a m p; \equiv 96 (\mod 100) \\ 15^{2} = 225 & a m p; \equiv 25 (\mod 100) \\ 16^{2} = 256 & a m p; \equiv 56 (\mod 100) \\ 17^{2} = 289 & a m p; \equiv 89 (\mod 100) \\ 18^{2} = 324 & a m p; \equiv 24 (\mod 100) \\ 19^{2} = 361 & a m p; \equiv 61 (\mod 100) \\ 20^{2} = 400 & a m p; \equiv 0 (\mod 100) \\ 21^{2} = 441 & a m p; \equiv 41 (\mod 100) \\ 22^{2} = 484 & a m p; \equiv 84 (\mod 100) \\ 23^{2} = 529 & a m p; \equiv 29 (\mod 100) \\ 24^{2} = 576 & a m p; \equiv 76 (\mod 100) \end{matrix}

this shows that there are in total there are

25

elements in the list above, 0 is counted two times two many, and 25 is counted once too many therefore there are exactly

22

unique endings in the above, and lets denote the collection of unique last two digits as

L D

Notice that if we continued we would have

\begin{matrix} 25^{2} = 625 & a m p; \equiv 25 (\mod 100) \\ 26^{2} = 676 & a m p; \equiv 76 (\mod 100) \\ 27^{2} = 729 & a m p; \equiv 29 (\mod 100) \\ 28^{2} = 784 & a m p; \equiv 84 (\mod 100) \\ 29^{2} = 841 & a m p; \equiv 41 (\mod 100) \end{matrix}

notice that after

25

the order in which the endings arrive is in a mirrored fashion. Notice that every time a multiple of 25 is reached some special is happening. Specifically we claim that for any

n \in ℕ_{1}

and

k \in [1, \dots, 24]

we have

{(25 n + k)}^{2} \equiv {(25 n - k)}^{2} (\mod 100)

this is clear because

{(25 n + k)}^{2} = 25^{2} n^{2} + 50 k n + k^{2}

whereas

{(25 n - k)}^{2} = 25^{2} n^{2} - 50 k n + k^{2}

therefore

{(25 n + k)}^{2} - {(25 n - k)}^{2} = 100 k n \equiv 0 (\mod 100)

this fact allows us to show that given any

k \geq 25

that

k^{2} % 100 \in L D

, we do it by induction based on where it lies with respect to consecutive multiples of

25

We use the predicate : $P (k) : \forall n \in [25 k, \dots, 25 k + 24], n^{2} % 100 \in L D$ and show it holds true for all $k \in ℕ_{1}$

For the base case $k = 0$ then as verified in the huge table we know that for any $n \in [0, \dots 24]$ that $n^{2} % 100 \in L D$ . Now onto the induction step where we assume that $P (k)$ holds true for some $k \in ℕ_{1}$ and then we prove that $P (k + 1)$ hold true, so suppose that $n \in [25 (k + 1), \dots, 25 (k + 1) + 24]$ , in other words $n = 25 (k + 1) + j$ where $j \in [0, \dots, 24]$ if it so happens that $j = 0$ then $n = 25 (k + 1)$ and so when you square it it ends in $25$ , on the other hand if $j \in [1, \dots, 24]$ then we know that ${(25 (k + 1) + j)}^{2} \equiv {(25 (k + 1) - j)}^{2}$ but $25 (k + 1) - j = 25 k + 25 - j$ and since $j \geq 1$ then by the induction hypothesis $25 (k + 1) - j % 100 \in L D$ so therefore so is $25 (k + 1) + j$ as needed.