﻿ MAT 312: Applied Algebra

# MAT 312 : Applied Algebra

### Section 1.1 : The division algorithm and greatest common divisors

Find GCD(20,24). Express it as 20s + 24t.
 1 0 20 0 1 24
 1 0 20 -1 1 4
 6 -5 0 -1 1 4
20(-1) + 24(1) = 4 = GCD(20,24)

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)

### Section 1.4 : Congruence Classes

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 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])

Corollary 1.4.4: ( n⊥c ∧ ac≡bc mod n ) → a ≡ b mod n

Definition: Gn is the set of elements in Zn, that have a multiplicative inverse.

### Section 1.5 : Solving Linear Congruences

Solve 3x = 4 mod 5.

Multiply both sides by 5-1 which is 2.

2 * 3x = 2 * 4 mod 5
6x = 8 mod 5
1x = 3 mod 5
x = 3 mod 5

Find inverse of 5.
 1 0 3 0 1 5
 1 0 3 -2 1 -1
-2(3) + 1(5) = -1
2(3) - 1(5) = 1
The inverse of 3 is 2.

### Section 1.6 : Euler's Theorem and public key codes

Definition The number of elements in Gn is denoted by φ(n).

Theorem 1.6.2: (a has order k mod n) → ( aʳ≡aˢ mod n ⬄ r≡s mod k)

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) = Blocka mod n
β = Block = Decode(m) = mx mod n

### Section 2.2 : Functions

Surjective means onto.
Injective means 1-1.
Bijective means 1-1 & onto.

### Section 4.1 : Permutations

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.

### Section 4.2 : The order and sign of a permutation

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.

### Section 4.3 : Definition and examples of groups

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

### Section 5.1 : Preliminaries

Theorem 5.1.7 :

<g> = {gn: n ∈ Z}
O(<g>) = O(g)

### Section 5.2 : Cosets and Lagrange's Theorem

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.

### Section 5.3 : Groups of small order

Isomorphic groups have the same multiplication table.

Cn = Cyclic Group with n elements
Cn ≅ Zn

G x H = Direct Product
G x H = The set of all ordered pairs (g,h) with g ∈ G and h ∈ H
(g1,h1)·(g2,h2) = (g1·g2,h1·h2)

Theorem 5.3.2 : O(G x H) = O(G) x O(H)

### Section 5.4 : Error-detecting and error-correcting codes

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.