# Discussion 3B

# Bijections

Consider two sets and , and a function that maps elements from to the elements of .

- is
**injective**if each element in has at most one element in that maps to it - is
**surjective**if each element in has at least one element in that maps to it - is
**bijective**if it is both injective and surjective- is bijective if and only if it has an inverse

# Chinese Remainder Theorem

## Goal

Given a list of congruences , , , , find an that satisfies all congruences.

## Theorem

Let . If all the are relatively prime () then there is exactly one value of in the set that satisfies all the congruences.

## Finding

For and , we want to find a number that is a multiple of and , and similarly a number that is a multiple of and . Then is a solution because and .