Find GCD(20,24). Express it as 20s + 24t.

20(-1) + 24(1) = 4 = GCD(20,24)

1 | 0 | 20 |

0 | 1 | 24 |

1 | 0 | 20 |

-1 | 1 | 4 |

6 | -5 | 0 |

-1 | 1 | 4 |

**Corollary 1.1.3** : *Let a and b be positive integers. Then the greatest common divisor, d, of a and b is the smallest positive integral linear combination of a and b. (By an integral linear combination of a and b we mean an integer of the form as+bt where s and t are integers.) That is, d = as + bt for some integers s and t.*

Using Corollary 1.1.3 we can show that if as+bt = 1 then (a,b)=1.

1 is an integral linear combination of a and b.

1 is the smallest positive integer.

By Corollary 1.1.3, the GCD(a,b) is the smallest positive integral linear combination of a and b.

∴ GCD(a,b) = 1

**Lemma 1.1.4** : a ≡ b mod n → (a,n)=(b,n)

Theorem 1.4.3

*Let n be an integer greater than or equal to 2, and let a be an integer. Then [a] _{n} has an inverse iff. (a,n) = 1. In fact, if r and s are intergers s.t. ar + ns = 1 then the inverse of [a]_{n} is [r]_{n}.*

Find inverse of [5]_{7}.

1 | 0 | 5 |

0 | 1 | 7 |

1 | 0 | 5 |

-1 | 1 | 2 |

3 | -2 | 1 |

-1 | 1 | 2 |

5(3) + 7(-2) = 1

The inverse of 5 is 3. (Note: By symmetry, also 3⁻¹=5 [And 7 and -2 are inverses mod either 5 or 3])

**Definition**: G_{n} is the set of elements in Z_{n}, that have a multiplicative inverse.

Solve 3x = 4 mod 5.

Multiply both sides by [3] 2 * 3x = 2 * 4 mod 5 |
Find inverse of [3]_{5}.
2(3) - 1(5) = 1 The inverse of 3 is 2. |

**Definition** The number of elements in G_{n} is denoted by φ(n).

Choose two primes p & q

n = p * q

Choose *a* relatively prime to φ(n)

x = a^{-1} mod φ(n)

Publish (base,exponent) = (n,a)

*m* = message = Encode(Block) = Block^{a} mod n

β = Block = Decode(m) = m^{x} mod n

Surjective means onto.

Injective means 1-1.

Bijective means 1-1 & onto.

Injective means 1-1.

Bijective means 1-1 & onto.

A **permutation** is a rearrangement of a set.

**S(n)** = The **Symmetric Group**

**S(n)** = The set of all **permutations** of {1,2,...,n}

**Theorem 4.1.1: S(n)** has n! elements.

**Theorem 4.1.3:** Any permutation may be expressed as a product of disjoint cycles.

**Lemma 4.2.5 : ** O(πσ) = lcm(O(π),O(σ)) for disjoint π,σ ∈ S(n).

**Theorem 4.2.11**

If n ≥ 2 then

1) Every permutation in is a product of transpositions.

2) Although there are many ways of writing a given permutation π as a product of transpositions, the number of terms occurring will always be either even or odd according as π is even or odd.

Exercise 4.2.13: For the 15 Puzzle, getting the space back to the same square requires an even number of transitions. Swapping 2 pieces requires an odd number. You can't do both.

A **Group** is a set with an operator * s.t.

1) * is closed

2) * is associative

3) * has an identity

4) * has an inverse

**A(n)** = The **Alternating Group**

**A(n)** = The set of all even **permutations** of {1,2,...,n}

**A(n)** is a subgroup of .

**D(n)** = The **Dihedral Group**

**D(n)** = The set of all **Symmetries** of an n-sided polygon

|**D(n)**| = 2n

**Theorem 5.1.7 : **

<g>= {g^{n}: n ∈ Z}

O(<g>) = O(g)

**Theorem 5.2.3 : Lagrange’s Theorem**

O(G) = O(H) * m

G is a .

H is a subgroup of G.

m is the number of distinct cosets of H in G.

C_{n} = **Cyclic Group** with n elements

C_{n} ≅ Z_{n}

G x H = **Direct Product**

G x H = The set of all ordered pairs (g,h) with g ∈ G and h ∈ H

(g_{1},h_{1})·(g_{2},h_{2}) = (g_{1}·g_{2},h_{1}·h_{2})

**Definition** : **Group Code**, the sum of 2 codewords is a codeword.

**Theorem 5.4.3** : In a **Group Code**, the min distance between codewords = the min weight codeword.