Notes - Basic Notions

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

• 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¹⁰⁰) - π(10⁹⁹) ~ 10¹⁰⁰/(ln 10¹⁰⁰) - 10⁹⁹/(ln 10⁹⁹) ~ 3.9 x 10⁹⁷
• 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₁ b + r₁
• if r = 0 then b divides a and the greatest common divisor is b if r ≠ 0 then continue with
• b = q₂ r₁+ r₂
• 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

Back to ToC