Ch 2 Intro to Number Theory

2.1 Divisibility and the Division Algorithm

• b divides a if a = mb for some m where all are integers

2.2 The Euclidean Algorithm

• Finds GCD easily

  

2.3 Modular Arithmetic

• a mod n finds the remainder of a when divided by n. The int n is called the modulus

• two ints a and b are said to be congruent modulo n if (a mod n) = (b mod n)

• Rules of arithmetic apply to modular arithmetic

2.4 Prime Numbers

• A number p is prime if its divisors are +-1 and +-p

• All non prime numbers are called composite

2.5 Fermat’s and Euler’s Theorems - wtf

• Fermat’s Theorem: If p is prime and a is a positive integer not divisible by p then a^p-1 K 1 (mod p)

2.6 Testing for Primality

2.7 Chinese Remainder Theorem

2.8 Discrete Logarithms