# MATH 135: Algebra for Honour's Mathematics

Back to UWaterloo

### Divisibility

#### Transitivity of Divisibility (TD)

Shows that divisibility is transitive: `If a|b and b|c, a|c`

#### Divisibility of Integer Combination (DIC)

`If a|b and a|c, then a|(bx + cy)`

#### Bounds by Divisibilty (BBD)

The denominator must be smaller if divisible: `If a|b and b≠0, then |a|≤|b|`

#### Divison Algorithm

There exists q and r s.t. b = aq + r, where 0 ≤ r < a

### Greatest Common Divisors

Bezout's Lemma (Extended Euclidean Algorithm)

### RSA

For proofs, try contradictions, contra-positives or direct proofs. For induction, find a statement P(n) that is true or false. Show that P(1) is true. Assume P(k) is true. Show that P(k+1) is true.

GCD, LDE, Congruences, linear congruences, Simultaneous Congruences, FlT, CRT, SM, RSA, Complex Numbers, Fields

Congruences can add, subtract, multiply. To divide, apply CD. To simplify exponents, apply FlT.

For simultaneous congruences, use chinese remainder theorem.

For Linear congruences, apply knowledge of Linear Diophantine Equations.