Prime Numbers

We are all aware of the prime numbers, 2, 3, 5, 7, 11, etc. It is a concept we learn about very early on in school but what does it actually mean for a number to be prime? Definition: An integer p > 1 is said to be prime if the only positive divisors of p are 1 and p itself. We must note that 1 itself is not prime. All of the prime numbers are odd, and the smallest prime is 2. Lemma: Let p be prime, and let a and b be any integers. Then a) Either p divides a, or a and p are coprime; b) If p divides ab, then either p divides a or p divides b. Proof a) By the definition of coprime numbers, gcd(a, p) is a positive divisor of p, so it must take the value 1 or p since p is prime. If gcd(a, p) = p, then since gcd(a, p) divides a we have p divides a; if gcd(a, p) = 1 the a and p are coprime. b) Let p divide ab. If p does not divide a then part (a) implies that gcd(a, p) = 1. By Bezout’s identity, 1 = ax + py for some integers x and y, so b = axb + pyb. By our initial assumption, p divides ab and hence divides both axb and pyb. Therefore, p divides b, as required. ■ Prime numbers are the building blocks for all possible integers, so they are an extremely important mathematical concept. This can be explained by our next theorem, the Fundamental Theorem of Arithmetic. Theorem: Each integer n > 1 has a unique prime factorisation as a product of prime numbers

where p₁,…,p_k are distinct primes and e₁,…,e_k are positive integers. To prove this theorem, we have to prove both existence and uniqueness: 1. Existence Using induction on n; n > 1 so n = 2, 3,… and p(n) means n has a prime factorisation. Base Case: p(2) = 2 which is prime so true for n = 2. Suppose p(m) is true for all m < n. Consider n; If n = prime, n has the required prime factorisation. If n ≠ prime, we can assume that n is composite, i.e. divisor(n) = {1, d, n} where d ≠ 1 or n. This implies n = d x (n/d). p(d), p(n/d) are true since d, n/d < n. Let d = p₁^e1…p_r^er and n/d = q₁^f1…q_f^fs so, which is a product of primes. 2. Uniqueness Suppose n = p₁… p_r where there could be repetition of primes. Induction on r: p(r) If a product of primes p₁… p_r= q₁… q_s, then r=s and p_i, q_i are the same. Base Case: p(1) If p = q₁… q_s, this implies that p divides q_j for some j. Therefore p = q_j 1 = q₁…q̂_i…q_s is false is s > 1 so p(1) is true (i.e. not a product of primes.) p(r) : Suppose p₁…p_r= q₁…q_s. p_r divides q₁…q_s implies that p_r divides q_j for some j so p₁…p_r-1= q₁…q̂_i…q_s By induction, p(r – 1) is true, implying s – 1 = r – 1 and the powers are unique. ■ For example, 200 has the prime factorisation 2³ x 5². A way of finding all the prime numbers is to use the Sieve of Eratosthenes. This is a systematic way to eliminate numbers that are not prime. For example, if we write out all number 1-100, start by circling the prime number 2 then score out all numbers that are factors of 2. 3 is our next prime number so we circle it and score out all numbers that are a multiple of 3. This process continues until we are only left with the prime numbers. However, we have made your life easier by creating this prime number calculator.

Positive Number:

Check if number is Prime

Written by JaneW