- Divisibility
- let a and b be integers with a ≠ 0. a divides b if there is an integer k such that b = ak, or that b is a multiple of a. This is denoted by a|b
- 3|15, -15|60
- Proposition
- for every a ≠ 0, a|0 and a|a. Also, 1|b for every b
- if a|b and b|c, then a|c
- if a|b and a|c then a|(sb + tc) for all integers s and t
- Prime Numbers
- A number p > 1 that is divisible by only 1 and itself is a prime number, any number that is not prime is called composite
- Prime Number Theorem
- Let π(x) ~ x/(ln x) where π(x) is the number of primes less than x in the sense that π(x)/x/(ln x) ->1 as x->
- Example
- 100 digit primes
- π(10
^{100}) - π(10^{99}) ~ 10^{100}/(ln 10^{100}) - 10^{99}/(ln 10^{99}) ~ 3.9 x 10^{97} - Theorem - Every Positive Integer is a product of primes, and this factorization is unique up to a reordering of the factors
- Lemma - If p is a prime and p divides a product of integers ab, then either p|a or p|b. More generally if a prime p divides a product ab...z then p must divide one of the factors a,b,...z
- Therefore an integer can be written as the product of its prime factors to a given power
- Greatest Common Divisor
- GCD is the largest positive integer dividing both a and b
- example gcd(6,4)=2; gcd(24,60) = 12
- Factor both numbers into primes, and take the smallest of the common divisors and multiply them together
- Euclidean algorithm
- Example gcd(482,1180)
- 1180 = 2 * 482 +216
- 482 = 2 * 216 + 50
- 216 = 4 * 50 + 16
- 50 = 3 * 16 + 2
- 16 = 8 * 2 + 0
- Since 2 was the last nonzero remainder, the gcd is 2
- divide a by b in the form
- a = q
_{1}b + r_{1} - if r = 0 then b divides a and the greatest common divisor is b if r ≠ 0 then continue with
- b = q
_{2}r_{1}+ r_{2} - r
_{k-2}= q_{k}r_{k-1 }+ r_{k} - r
_{k-1}= q_{k+1}r_{k} - gcd(a,b) = r
_{k} - Theorem - Let a and b be two integers with at least one of a,b nonzero, and let d = gcd(a,b). Then there exist integers x, y such that ax + by = d. In particular, if a and b are relatively prime, then there exist integers x,y with ax + by = 1.
- Corollary - If p is a prime and p divides a product of integers ab,then either p|a or p|b. More generally if a prime p divides a product ab,...z then p must divide one of the factors a,b,...z

## Wednesday, September 11, 2013

### Notes - Basic Notions

The following are notes from Introduction to Cryptography with Coding Theory.

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment