CMPS 2120 Lecture Notes - Integer Number System, Division and Primes
resources:
2011 prime year
code.cpp
RSA DES challenge
Great Internet Primes Search GIMPS
List of Mersenne Primes (48 total)
N = {0,1,2,...} = set of natural numbers
N can be defined with a single number called 'zero' and a successor
function s: N->N, where zero is not the successor of any number and two
different numbers n and m cannot have the same successor: s(n) != s(m).
Predecessor function p: N->N, where p(n) = m and s(m) = n.
Addition: n + m = { n if m=0, s(n) + p(m) otherwise }
Multiplication: n * m = { 0, if m or n = 0, n + n * p(m) )
Ordering: n >= m means { m = 0, or p(n) >= p(m) }
---------------------
| Divides Operator |
---------------------
Let d and n be integers, d!=0. Then d | n, read "d divides n", is true if
d is a factor of n. It also means that n % d = 0. 1 is a trivial divisor
for all n; n divides itself; d != n are proper divisors.
----------
| Primes |
----------
http://primes.utm.edu
list of primes
An integer n >= 2 is prime if n has no nontrivial proper divisors, and
composite otherwise. (1 is not considered a prime number.)
There are infinitely many prime numbers. (Euclid)
The distribution of prime numbers among regular numbers is "random."
(A top 10 unsolved problem for the 21st century is to prove the Riemann
Hypothesis - that the distribution of primes closely follows the behavior of
the Riemann zeta function. Interesting solutions to Z(s) = 0 lie
on a vertical straight line.)
// algorithm to determine if n is prime
stop <- floor(srt(n))
for i <- all primes between 2 and stop
if n mod i = 0
flag <- prime
break
Ex. is 731 prime?
floor(sqrt(731)) = 27.
731 mod 2
731 mod 3
731 mod 5
731 mod 7
731 mod 11
731 mod 13
731 mod 17 = 0; 731 = 17 * 43, thus NOT PRIME
quick and dirty way to compute sqrt(n).
factor n into (2^x)(2^x)
731 ~= 2^10
2^10 = (2^5)(2^5)
sqrt(731) ~= 2^5
~= 32. close enough
Fundamental Theorem of Arithmetic.
Every positive integer can be written uniquely as the product of nondecreasing
primes. Ex.
5100 = 2^2 * 5^2 * 51 <= a prime power factorization is unique
Since all integers have a unique prime factorization, that factorization
provides insights into the number. What is the factorization of 162? One method
is to create a factor tree:
162
/ \
81 2
/ \
9 9
/ \ / \
3 3 3 3 = 2*3*3*3*3
-------------------
| Mersenne Primes |
-------------------
Reasoning about primes of the form 2^p - 1, where p is a positive integer.
Proposition P: If p is composite then 2^p - 1 is composite. TRUE.
The contrapositive of P is also TRUE:
If 2^p - 1 is not composite (i.e.,prime) then p is not composite (i.e.,prime.)
2^4 - 1 = 15 composite p and composite M
2^6 - 1 = 63 composite p and composite M
2^9 - 1 = 511 composite p and composite M
31 = 2^5 - 1 prime M and prime p
127 = 2^7 - 1 prime M and prime p
....
HOWEVER-
Inverse: If p is prime then 2^p -1 is prime. OFTEN TRUE.
Converse: If 2^p - 1 is composite then p is composite. NOT NECESSARILY TRUE.
A few examples:
2^5 - 1 = 31. prime p and prime M
2^11 - 1= 2047. prime p and NOT prime M
15 = 2^4 - 1. composite M and composite p
2047 = 2^11 -1. composite M and NOT composite p
Mersenne proved that if p = mn, where m,n > 1, then 2^p -1 is not prime.
Simple example.
Recall: 2(2^m) = 2^(m+1) and 2^(m(n-1)) * 2^m = 2^(mn)
Let m = 4 and n = 3.
Show that we can factor 2^(mn) - 1, which is 2^12 - 1 (4095).
The first factor is shown below (note the pattern of the exponents).
2^(4(3-1)) + 2^(4(3-2)) + 2^(4(3-3))
= 2^(4(2)) + 2^(4(1)) + 2^(4(0))
= 2^8 + 2^4 + 2^0.
The second factor is 2^4 - 1.
Multiply the two factors:
sanity check.
2^8 + 2^4 + 1 256 + 16 + 1 = 273
* 2^4 - 1 2^4 - 1 = 15
------------------
2^12 + 2^8 + 2^4 273 * 15 = 4095. 2^12 - 1 = 4095.
- 2^8 - 2^4 - 1
----------------------
2^12 - 1. bingo.
Mersenne generalized on the above two factors to provide a formal proof that
if p = mn, where m,n > 1, then 2^p -1 is not prime.
2^(mn) - 1 can be factored as follows, where the first factor is:
n
Σ 2^(m(n-i))=2^(m(n-1))+2^(m(n-2))+2^(m(n-3))+...+2^m(n-(n-1))+2^m(n-n)
i=1
Simplified, the above expression looks like this:
2^(m(n-1)) + 2^(m(n-2)) + 2^(m(n-3)) +...+ 2^3m + 2^2m + 2^m + 1.
The second factor that Mersenne used is 2^m - 1.
If you multiply the two factors together and you get 2^(mn) - 1 then you
know that 2^(mn) - 1 is NOT prime. Proof:
2^(m(n-1)) + 2^(m(n-2)) + 2^(m(n-3)) + . . . + 2^3m + 2^2m + 2^m + 1
2^m - 1
---------------------------------------------------------------------------
2^(mn) + 2^(m(n-1)) + 2^(m(n-2)) + .. . + 2^(4m) + 2^(3m) + 2^(2m) + 2^m
-2^(m(n-1)) -2^(m(n-2)) . . . - 2^(4m) - 2^(3m) - 2^(2m) - 2^m - 1
---------------------------------------------------------------------------
2^(mn) + 0 + 0 + 0 + 0 + 0 + 0 - 1
= 2^(mn) - 1. bingo.
Conclusion: Since 2^(mn)-1 can be factored it cannot be prime.
The contrapositive of P is:
If 2^p - 1 is prime then p is prime; i.e., p != mn, where m,n > 1.
What about the converse of P (which Mersenne mistakenly thought was true)?
If p is prime, then 2^p - 1 is prime. TRUE?
The converse is not true (2^11 - 1 is not prime), but OFTEN is. A Mersenne
prime is a prime number of the form 2^p - 1, where p is prime. The largest
known prime numbers today are Mersenne primes since there is a fast algorithm
for determining whether a number of the form 2^k - 1 is prime.
There are 40 known Mersenne primes, and it is conjectured though unproven
that there are an infinite number of Mersenne primes.
Here is a complete list of all known exponents for Mersenne primes:
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281,
3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243,
110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377,
6972593, 13466917, 20996011
There is a relatively easy way to determine if an integer of the form
2^p - 1 is prime using this theorem :
Let p and q be primes. If q divides 2^p -1, then q = 2kp + 1.
Verify that 2^11 - 1 is NOT prime by using the above theorem. 2^11 - 1 = 1047.
Start by setting k=1.Then q=2(1)11 + 1 = 23. 2047 mod 23 = 0. BINGO.
Verify that 2^7 - 1 IS prime by using the above theorem but in this case
stopping when you do not find a factor (i.e., MOD will give you a remainder).
2^7 -1 = 127. Start by setting k=1.Then q=2(1)7+1 = 15. 127 mod 15 = 7.
We do not need to try another k since 15 is larger than sqrt(127).
Lemma.
If a prime number p divides a product mn of integers, then p divides either m
or n. Ex.
If 2 | 510 then 2 | 10 or 2 | 51.
---------------------------
| Greatest Common Divisor |
---------------------------
GCD: Let a and b be integers, not both zero. The largest integer d, such that
d | a and d | b is the greatest common divisor of a and b. Note that d may or
may not be prime. Example,
Let gcd(a,b) return the greatest common divisor of a and b.
gcd(24,36)?
24= 2*2*2*3
36= 2*2*3*3
gcd = 2*2*3=12. GCD is the intersection of the two sets of factors.
gcd(17,22) = 1. 17 and 22 are relatively prime.
Integers a and b are relatively prime (coprime) if gcd(a,b) = 1 ; i.e.,
a and b share no common factors other than 1. Notation:
m _|_ n (motivated by orthogonal vectors; e.g. nothing in common)
ex. 25 and 12
Which positive integers less than 12 are relatively prime to 12? 5,7,11
Integers a_1,a_2,...a_n are pairwise relatively prime if gcd(a_i,a_j) = 1 for
all 1 <= i < j <= n. Ex.
{ 2, 5, 7 }?
gcd(2,5) = 1.
gcd(2,7) = 1.
gcd(5,7) = 1.
The set { 2, 5, 7 } is pairwise relatively prime.
-------------------------
| Least Common Multiple |
-------------------------
The LCM of positive integers a and b is the smallest positive integer that is
divisible by both a and b: lcm(a,b). Ex.
lcm(2^3*3^5*7^2, 2^4*3^3) = 2^4*3^5*7^2.
Theorem:
Let a and b be positive integers. Then ab = gcd(a,b) * lcm(a,b). Ex.
24= 2*2*2*3
36= 2*2*3*3
// gcd is the *intersection* of the prime factors in both numbers
gcd(24,36) = 2*2*3 = 12
// lcm is a *union* of the prime factors in both numbers
lcm(24,36) = 2^3*3^2 = 8*9 = 72
24 * 36 = 864
12 * 72 = 864
Observation: Once you pick the factors in the GCD, the LCM is the GCD plus
the factors that are left behind.
Quick and Dirty method to determine gcd and lcm:
m = 60 factor m: 2 * 2 * 3 * 5
n = 45 factor n: 3 * 3 * 5
the gcd is those factors that appear in BOTH lists: 3*5=15
the lcm is those factors left after you take the gcd out: 2*2*3*3*5=180
confirm:
gcd(m,n) = 15
lcm(60,45) = 180
check:
m*n = gcd*lcm
60*45 = 15*180
2700 = 2700.
--------------------
| Integer Division |
--------------------
Let n be an integer and d a positive integer. Then there are unique integers
q and r, such that n = qd + r, with 0 < r < d.(Terminology: n=dividend,
q=quotient, d=divisor, r=remainder). Ex.
Find q and r for 100 divided by 7.
n=100, d=7
100 = 7*14 + 2, where q=14 and r=2
Find q and r for -100 divided by 7.
n=-100, d=7
100 = 7*-15 + 5, where q = -15 and r=5
Ex. -15 divided by 7 is -3 + 6.
-21 -15 -10 -5
-------|-------|----|----|----0--------------------------
^
----------------------
| Modular Arithmetic |
----------------------
Let n and m > 0 be integers. The residue of dividing n by m is, if n >= 0, the
remainder, or for n < 0, the smallest nonnegative number obtained by adding an
integral multiple of m. The residue of dividing n by m is n mod m. Ex.
7 mod 8 = 7
19 mod 7 = 5
-17 mod 5 = 3
-19 mod 7 = 2
For integers n and m > 0, n - (n mod m) is a multiple of m. Ex.
n=19 m=7
19 mod 7 = 5; 19 - 5 = 14 (a multiple of 7)
---------------
| Congruences |
---------------
Notation: a ≡ b(mod m) means a is congruent to b modulo m.
The next four statements express congruences:
For integers a, b and m > 0,
a ≡ b(mod m) iff a mod m = b mod m.
For integers a, b and m > 0,
a is congruent to b modulo m if m divides a - b. Ex.
22 ≡ 17 mod 5; 5 | 22-17
For integers a, b and m > 0,
a and b are congruent modulo m iff there is an integer k such that a = b + km.
This property shown on the number line.
If a is congruent to b mod m, then a and b have the same residue r with respect
to mod m:
m m m m m m r
-------|-------|-------|-------|-------|-------|----| << a >>
m m m m r
-------|-------|-------|-------|----| << b >>
Thus,
a = xm + r, for some integer x.
b = ym + r, for some integer y.
a - xm = r and b - ym = r.
Combine and simplify the two equations:
a - xm = b - ym
a = xm + b - ym
a = b + xm - ym
a = b + m(x - y)
a = b + km, for some integer k.
------------
| Theorems |
------------
For integers a, b, c, d, and m>0, if a ≡ b mod m and c ≡ d mod m then
a + c ≡ b + d mod m and ac ≡ bd mod m.
For integers a,b,and m >0, if a ≡ b(mod m) and c ≡ d(mod m) then
a + c ≡ b + d(mod m) and ac ≡ bd(mod m).
** Show that if a, b, and c are integers such that a | b and a | c, then
a | b+c.
If a | b then b = pa. If a | c then c = qa. Then b+c = pa + qa. Thus, show
a | (pa + qa). pa + qa = a(p + q).