Discussion 3B

Bijections

Consider two sets

A

and

B

, and a function

f : A \mapsto B

that maps elements from

A

to the elements of

B

.

$f$ is injective if each element in $B$ has at most one element in $A$ that maps to it

$f$ is surjective if each element in $B$ has at least one element in $A$ that maps to it

$f$ is bijective if it is both injective and surjective

$f$ is bijective if and only if it has an inverse $f^{-1}$

Chinese Remainder Theorem

Goal

Given a list of congruences

x \equiv a_1 \mod m_1

,

x \equiv a_2 \mod m_2

,

\cdots

,

x \equiv a_n \mod m_n

, find an

x

that satisfies all congruences.

Theorem

Let

N = m_1 m_2 \cdots m_n

. If all the

m_i

are relatively prime (

\gcd(m_i, m_j) = 1

) then there is exactly one value of

x

in the set

\{ 0, 1, \cdots, N-1 \}

that satisfies all the congruences.

Finding $x$

For

x \equiv a_1 \mod m_1

and

x \equiv a_2 \mod m_2

, we want to find a number

k_1

that is a multiple of

m_2

and

k_1 \equiv 1 \mod m_1

, and similarly a number

k_2

that is a multiple of

m_1

and

k_2 \equiv 1 \mod m_2

. Then

x = a_1 k_1 + a_2 k_2

is a solution because

x \equiv a_1 k_1 + 0 \equiv a_1 \mod m_1

and

x \equiv 0 + a_2 k_2 \equiv a_2 \mod m_2

.

​​Bijections

​​Chinese Remainder Theorem

​​Goal

​​Theorem

​​Finding ​​xxx​

Bijections

Chinese Remainder Theorem

Goal

Theorem

Finding $x$