1. E. Prime numbers

62
NUMBER THEORY (Chapter 1)
E
PRIME NUMBERS
An integer p is a prime number (or prime) if p > 1, and if the only
positive numbers which divide p are 1 and p itself.
1 is neither prime
nor composite.
An integer greater than 1 that is not prime is said to be composite.
We have already proven that there are an infinite number of primes, but
they appear to not follow any pattern. It would be very useful to discover
an efficient method for finding prime numbers, because at present no
such method exists. This is in fact the basis of the RSA encription
system by which international financial and security transactions are
protected. The study of number theory is therefore a highly important
and applicable area of study. The basis of the RSA encryption system
is a suitable topic for an Extended Essay in Mathematics.
E
Euclid’s Lemma for primes
SA
M
PL
For integers a and b and prime p, if p j ab then either p j a or p j b.
If p j a the proof is complete, so suppose p =j a.
Proof:
Since p =j a and p is prime, gcd(a, p) = 1.
) there exist integers r and s such that ar + ps = 1.
It is possible that
p j a and p j b.
) b = b £ 1 = b(ar + ps) = abr + bps
But p j ab, so ab = kp for some integer k
) b = kpr + bps = p(kr + bs)
) p j b.
So, either p j a or p j b.
If p is a prime and p j a1 a2 a3 ::::an for a1 , a2 , a3 , ...., an 2 Z
then there exists i where 1 6 i 6 n such that p j ai .
Lemma:
For example, if p j 6 £ 11 £ 24 then p j 6 or p j 11 or p j 24. At least one of 6, 11, and 24 must
be a multiple of p.
Proof: (By Induction)
(1) If n = 1 then p j a1 . ) P1 is true.
(2) If Pk is true, then p j a1 a2 a3 ::::ak ) p j ai for some i where 1 6 i 6 k.
Now if p j a1 a2 a3 ::::ak ak+1 then p j (a1 a2 a3 ::::ak )ak+1
) p j a1 a2 a3 ::::ak or p j ak+1
fusing Euclid’s Lemma for primesg
) p j ai for some i in 1 6 i 6 k, or p j ak+1
) p j ai for some i in 1 6 i 6 k + 1
cyan
magenta
yellow
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
Thus P1 is true, and Pk+1 is true whenever Pk is true.
) Pn is true. fPrinciple of Mathematical Inductiong
black
IB HL OPT
Discrete Mathematics
Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\062IB_HL_OPT-DM_01.cdr Friday, 29 November 2013 2:47:52 PM BRIAN
NUMBER THEORY (Chapter 1)
63
THE FUNDAMENTAL THEOREM OF ARITHMETIC
Every positive integer greater than 1 is either prime, or is expressible uniquely (up to the ordering) as
a product of primes.
Proof:
Let S be the set of positive integers which cannot be written as a product of primes,
and suppose S is non-empty.
Existence:
By the Well Ordered Principle, S has a smallest number, which we will call a.
If the only factors of a are a and 1 then a is a prime, which is a contradiction.
) we can write a as the product of factors a = a1 a2 where 1 < a1 < a, 1 < a2 < a.
Neither a1 nor a2 are in S, since a is the smallest member of S.
) a1 and a2 can be factorised into primes: a1 = p1 p2 p3 ::::pr and a2 = q1 q2 q3 ::::qs .
) a = a1 a2 = (p1 p2 p3 ::::pr )(q1 q2 q3 ::::qs )
E
) a2
= S, which is a contradiction. Therefore S is empty, and every positive integer
greater than 1 is either prime, or is expressible as a product of primes.
SA
M
PL
Uniqueness: Suppose an integer n > 2 has two different factorisations
n = p1 p2 p3 ::::ps = q1 q2 q3 ::::qt where pi 6= qj for all i, j.
By Euclid’s Lemma for primes, p1 j qj for some j.
) p1 = qj fas these are primesg
Relabelling qj as q1 if necessary, we can instead write p1 = q1
)
n
= p2 p3 p4 ::::ps = q2 q3 q4 ::::qt
p1
By the same reasoning, relabelling if necessary, p2 = q2 and
n
= p3 p4 ::::ps = q3 q4 ::::qt
p1 q 1
This can be done for all pj , showing that s 6 t.
The same argument could be made swapping ps and qs, so t 6 s also.
) s = t, the pi s are a rearrangement of the qj s, and the prime factorisation is unique
up to the ordering of the primes.
Example 27
Discuss the prime factorisation of 360, including how many factors 360 has.
magenta
yellow
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
cyan
360 = 23 £ 32 £ 51 and this factorisation is unique up to the ordering of the
factors.
The only prime factors of 360
are 2, 3, and 5.
Check this result by listing
Including 1 and 360, 360 has
all 24 factors in a systematic
way. For example:
(3 + 1)(2 + 1)(1 + 1)
20 £ 30 £ 50,
=4£3£2
22 £ 31 £ 50, ....
= 24 factors.
360
180
90
45
15
5
2
2
2
3
3
black
Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\063IB_HL_OPT-DM_01.cdr Monday, 20 January 2014 1:18:54 PM BRIAN
IB HL OPT
Discrete Mathematics
64
NUMBER THEORY (Chapter 1)
Finally, we present a theorem that can be used to reduce the work in identifying whether a given integer, n,
p
is prime. In it we show that we need only attempt to divide n by all the primes p 6 n. If none of
these is a divisor, then n must itself be prime.
Theorem:
If n 2 Z + is composite, then n has a prime divisor p such that p 6
p
n.
Proof:
Let n 2 Z + be composite.
) n = ab where a, b 2 Z + such that n > a > 1 and n > b > 1.
p
p
If a > n and b > n, then ab > n, which is a contradiction.
p
) at least one of a or b must be 6 n.
p
Without loss of generality, suppose a 6 n.
E
Since a > 1, there exists a prime p such that p j a. fFundamental Theorem of Arithmeticg
EXERCISE 1E
SA
M
PL
But a j n, so p j n. fp j a and a j n ) p j ng
p
p
Since p 6 a 6 n, n has a prime divisor p such that p 6 n.
1 Determine which of the following are primes:
a 143
b 221
c 199
d 223
c 1111
d 11 111
2 Prove that 2 is the only even prime.
3 Which of the following repunits is prime?
a 11
b 111
4 Show that if p and q are primes and p j q, then p = q.
5 28 £ 34 £ 72 is a perfect square. It equals (24 £ 32 £ 7)2 .
a Prove that:
i all the powers in the prime-power factorisation of n 2 Z + are even , n is a square
ii given n 2 Z + , the number of factors of n is odd , n is a square.
p
b Hence prove that 2 is irrational.
cyan
magenta
yellow
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
50
75
25
0
5
100
a Prove that if a, n 2 Z + , n > 2 and an ¡ 1 is prime,
then a = 2.
Hint: Consider 1 + a + a2 + :::: + an¡1 and its sum.
b It is claimed that 2n ¡ 1 is always prime for n > 2.
Is the claim true?
c It is claimed that 2n ¡ 1 is always composite for n > 2.
Is the claim true?
d If n is prime, is 2n ¡1 always prime? Explain your answer.
6
black
Primes of the form 2n - 1
are called Mersenne primes.
IB HL OPT
Discrete Mathematics
Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\064IB_HL_OPT-DM_01.cdr Friday, 14 February 2014 11:27:49 AM BRIAN
NUMBER THEORY (Chapter 1)
65
7 Find the prime factorisation of:
a 9555
b 989
c 9999
d 111 111
8 Which positive integers have exactly:
a three positive divisors
9
b four positive divisors?
a Find all prime numbers which divide 50!
b How many zeros are at the end of 50! when written as an integer?
c Find all n 2 Z such that n! ends in exactly 74 zeros.
10 Given that p is prime, prove that:
a p j an ) pn j an
b p j a2 ) p j a
c p j an ) p j a
11 There are infinitely many primes, and 2 is the only even prime.
a Explain why the form of odd primes can be 4n + 1 or 4n + 3.
b Prove that there are infinitely many primes of the form 4n + 3.
SA
M
PL
E
There are also infinitely many
primes of the form 4n + 1,
but the proof is beyond the
scope of this course.
n
12 The Fermat primes are primes of the form 22 + 1.
a Find the first four Fermat primes.
b Fermat conjectured that all such numbers were prime whenever n was prime. By examining
the case n = 5, show that Fermat was incorrect.
RESEARCH
cyan
magenta
yellow
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
95
100
50
75
25
0
5
² The first two perfect numbers are 6 and 28. Research how these numbers are connected to the
Mersenne primes of the form 2n ¡ 1.
² The repunits Rk are prime only if k is prime, and even then only rarely. Thus far, the only
prime repunits discovered are R2 , R19 , R23 , R317 , and R1031 .
Research a proof that a repunit Rk may only be prime if k is prime.
black
IB HL OPT
Discrete Mathematics
Y:\HAESE\IB_HL_OPT-DM\IB_HL_OPT-DM_01\065IB_HL_OPT-DM_01.cdr Friday, 14 February 2014 11:58:53 AM BRIAN

Download Report