20161014, 15:56  #1 
Dec 2012
The Netherlands
1,621 Posts 
Basic Number Theory 4: a first look at prime numbers
Let \(p\) be an integer, and consider the following two properties which \(p\) may have:
Any integer \(p\) with property (B) has property (A)  we can show that quite easily. What is remarkable is that any integer \(p\) with property (A) has property (B) as well. To prove that, we shall need the propositions about greatest common divisors that we proved last time. Proposition 12 Let \(p\) be an integer. Then \(p\) has property (A) if and only if \(p\) has property (B). proof Suppose \(p\) has property (B). Then, in particular, \(p>1\). Take any positive factor \(a\) of \(p\). Then \(ap\) so \(ab=p\) for some integer \(b\), and \(p\) & \(a\) are both positive, so \(b>0\) too. Now \(pp=ab\) so (by property (B)) \(pa\) or \(pb\). If \(pa\) then \(pc=a\) for some integer \(c\) and therefore \(pcb=ab=p\). As \(p\neq 0\), we have \(cb=1\) (and \(b>0\)) so \(b=1\) and hence \(a=p\). If instead \(pb\) then \(pd=b\) for some integer \(d\), so \(pda=ab=p\) and therefore \(da=1\) (with \(a>0\)) hence \(a=1\). Thus any positive factor of \(p\) is equal to \(p\) or 1, so \(p\) has property (A). Suppose now that \(p\) has property (A). Then, in particular, \(p>1\). Take any integers \(a\) and \(b\) and suppose that \(pab\) but that \(p\) does not divide \(a\). As \(p\) has property (A), the only positive common divisor of \(p\) and \(a\) is 1, so \(\gcd(p,a)=1\). By corollary 10, there exist integers \(m\) and \(n\) such that \(mp+na=1\), and therefore \(mpb+nab=b\). But \(pab\) so \(pt=ab\) for some integer \(t\). Thus \(b=(mp+na)b=mpb+npt=p(mb+nt)\) from which we have \(pb\). Hence \(p\) has property (B). ∎ We have proved that the integers \(p\) with property (A) are precisely the same as the integers \(p\) with property (B). We call them the prime numbers. An integer greater than 1 which is not a prime number is called composite. Example The set of all prime numbers less than 100 is: \[\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97\}.\] Notation If we want to work with an ordered list of unspecified numbers, we could call them \(a,b,c\) etc.  but then the length of the list would be limited to 26, so we prefer to pick just one letter and use subscripts with it instead, e.g. \(a_1,a_2,a_3\) etc. Often, we prefer to leave the length of the list unspecified too. We then have a variable \(n\) (say) for the length of the list, and variables \(a_1,a_2,a_3,\ldots,a_n\) for the numbers in the list. We may write the sum of all these numbers as \(a_1+a_2+a_3+\ldots +a_n\) or as \[\sum_{i=1}^na_i \] (where \(\Sigma\) is the capital version of the Greek letter sigma). Similarly, we may write their product as \(a_1a_2a_3\ldots a_n\) or as \[\prod_{i=1}^na_i \] (where \(\Pi\) is the capital version of the Greek letter pi). The sum \(a_1+a_2+a_3+\ldots +a_n\) simply equals \(a_1\) in the case \(n=1\) and is defined to be 0 in the case \(n=0\) ("the sum of no numbers is 0"). The product \(a_1a_2a_3\ldots a_n\) simply equals \(a_1\) in the case \(n=1\) and is defined to be 1 in the case \(n=0\) ("the product of no numbers is 1"). Proposition 13 There are infinitely many prime numbers. proof Suppose not. Then there are only finitely many prime numbers. Let \(n\) be the number of distinct prime numbers which exist, and \(p_1,p_2,p_3,\ldots,p_n\) the prime numbers themselves. Let \(c=p_1p_2p_3\ldots p_n+1\) (i.e. multiply all the prime numbers together and then add 1). Then \(c\) has factors greater than 1 (\(c\) itself, for example). Let \(q\) be the smallest out of all the factors of \(c\) that are greater than 1. Take any positive factor \(r\) of \(q\). As \(q>0\), we have \(r\leq q\) by proposition 1. But \(rq\) and \(qc\) so \(rc\) (exercise 5), i.e. \(r\) is a factor of \(c\), and \(q\) is the smallest factor of \(c\) that is greater than 1, so either \(r=1\) or \(r=q\). This holds for all positive factors \(r\) of \(q\), so \(q\) is a prime number. However, dividing \(c\) by any of \(p_1,p_2,p_3,\ldots,p_n\) leaves a remainder of 1, and these are all the prime numbers, so no prime number divides \(c\). As \(q\) divides \(c\), it follows that \(q\) is not a prime number, and this is a contradiction (\(q\) is both prime and not prime). Hence there are infinitely many prime numbers. ∎ In the above proof, we show that if there are only finitely many prime numbers then there exists a number which is both prime and not prime, which is impossible. So it is impossible for there to be only finitely many prime numbers, and hence there are infinitely many. This proof technique is called proof by contradiction: start by assuming that what you want to prove is false, and show that this leads to a contradiction (i.e. some statement being both true and false). As that is impossible, you have shown that what you want to prove cannot be false, and hence it must be true. Lemma 14 Let \(n\) be a positive integer and \(a_1,a_2,a_3,\ldots,a_n\) integers. Let \(p\) be a prime number such that \(pa_1a_2a_3\ldots a_n\). Then there exists \(i\in\{1,2,3,\ldots,n\}\) such that \(pa_i\). proof Induction on \(n\). In the case \(n=1\), we already have \(pa_1\) so \(i=1\) suffices. Take any integer \(N>1\) and suppose the lemma holds for all positive integers \(n\) with \(n<N\). In the case \(n=N\), let \(b=a_1a_2a_3\ldots a_{n1}\). Then \(pba_n\) and \(p\) is a prime number so, by property (B), \(pb\) or \(pa_n\). If \(pb\) then \(pa_1a_2a_3\ldots a_{n1}\) and, by our assumption, there exists \(i\in\{1,2,3,\ldots,n1\}\) such that \(pa_i\). If instead \(pa_n\) then \(i=n\) suffices. Thus the lemma also holds in the case \(n=N\) and, by induction, it follows that the lemma holds for all positive integers \(n\). ∎ We now come to the major theorem that any positive integer can be expressed as a product of prime numbers in a unique way (we can write the primes out in a different order, but that is all). In the proof, we use property (A) to show that the product of primes exists and property (B) to show that it is unique. Theorem 15 (The fundamental theorem of arithmetic) Let \(a\) be a positive integer. Then there exist a unique nonnegative integer \(n\) and unique prime numbers \(p_1,p_2,p_3,\ldots,p_n\) with \(p_1\leq p_2\leq p_3\leq\ldots\leq p_n\) such that \(a=p_1p_2p_3\ldots p_n\). proof EXISTENCE Induction on \(a\). In the case \(a=1\), we may take \(n=0\). Take any integer \(N>1\) and suppose all positive integers \(a\) with \(a<N\) can be expressed in the required form. In the case \(a=N\), if \(a\) is itself a prime number then we may set \(n=1\) and \(p_1=a\). Otherwise (as \(a>1\)) \(a\) has a positive factor other than 1 and \(a\) itself, so \(a=bc\) for some integers \(b,c\) with \(1<b<a\) and therefore \(1<c<a\). By our assumption, \(b=p_1p_2p_3\ldots p_m\) for some integer \(m\geq 0\) and prime numbers \(p_1,p_2,p_3,\ldots,p_m\). And similarly, \(c=p_{m+1}p_{m+2}p_{m+3}\ldots p_n\) for some integer \(n\geq m\) and prime numbers \(p_{m+1},p_{m+2},p_{m+3},\ldots,p_n\). Hence \(a=bc=p_1p_2p_3\ldots p_n\), and we may renumber the factors so that \(p_1\leq p_2\leq p_3\leq\ldots\leq p_n\). By induction, any positive integer \(a\) can be expressed in the required form. UNIQUENESS Take any integers \(m\geq 0\), \(n\geq 0\) and any prime numbers \(p_1,p_2,\ldots,p_n,q_1,q_2,\ldots,q_m\) with \(p_1\leq p_2\leq\ldots\leq p_n\) and \(q_1\leq q_2\leq\ldots\leq q_m\), and suppose that \(p_2p_2\ldots p_n=q_1q_2\ldots q_m\). We claim that \(m=n\) and \(p_i=q_i\) for each \(i\in\{1,2,\ldots,n\}\). Induction on \(n\). In the case \(n=0\), we have \(p_1p_2\ldots p_n=1\) so \(q_1q_2\ldots q_m=1\) and therefore \(m=0=n\). Take any integer \(N>0\) and suppose the claim holds for all integers \(n\) with \(0\leq n<N\). In the case \(n=N\), we have \(n>0\) and \(p_1p_2\ldots p_n=q_1q_2\ldots q_m\) so \(m>0\) and \(p_nq_1q_2\ldots q_m\). By lemma 14, \(p_n\) divides at least one of \(q_1,q_2,\ldots,q_m\). Let \(k\in\{1,2,\ldots,m\}\) be the largest index for which \(p_nq_k\). As \(q_k\) is prime, its only positive divisors are 1 and \(q_k\) itself, and \(p_n>1\) (since \(p_n\) is prime too) so \(p_n=q_k\), and therefore \(p_1p_2\ldots p_{n1}=q_1\ldots q_{k1}q_{k+1}\ldots q_m\). If \(k<m\) then, by our assumption, \(m1=n1\) and \(p_1=q_1\), \(p_2=q_2\) etc. up to and including \(p_{n1}=q_m\) (missing out \(p_n\) and \(q_k\)). But then \(p_{n1}\leq p_n=q_k\leq q_m=p_{n1}\) so \(q_k=q_m\), which is impossible (we chose \(k\) to be as large as possible). Thus \(k=m\) giving \(p_n=q_m\) and, by our assumption again, \(m1=n1\) and \(p_i=q_i\) for all integers \(i\) with \(1\leq i\leq n1\). Hence \(m=n\) and \(p_i=q_i\) for all \(i\in\{1,2,\ldots,n\}\). By induction, the claim holds for all integers \(n\geq 0\). ∎ For any integer \(n>1\), \(2^n\) is not prime, of course, but it is worth considering the integers on either side of it, i.e. \(2^n+1\) and \(2^n1\). For example, \(2^{15}+1\) is not prime since \[ 2^{15}+1=(2^3+1)(2^{12}2^9+2^62^3+1) \] (multiply out the brackets and all terms cancel except the first and last). We generalize this in the following proposition. Proposition 16 Let \(m\) be a positive integer and suppose that \(2^m+1\) is prime. Then \(m=2^n\) for some integer \(n\geq 0\). proof Suppose \(m\) has an odd factor. greater than 1 Then \(m=(2r+1)s\) for some positive integers \(r\) and \(s\). So \[ 2^m+1 = (2^s+1)(2^{2rs}2^{(2r1)s}+2^{(2r2)s}2^{(2r3)s}+\ldots +2^{2s}2^s+1) \] and both factors on the right are greater than 1 so \(2^m+1\) is not prime. Thus if \(2^m+1\) is prime, then \(m\) cannot have any odd factors greater than 1, hence \(m=2^n\) for some integer \(n\geq 0\). ∎ Notation If we write \(x^{y^z}\) then, by definition, this means \(x\) raised to the power \(y^z\), not \(x^y\) raised to the power \(z\) (which we would write as \((x^y)^z\) or simply \(x^{yz}\)). For each integer \(n\geq 0\), we call \(2^{2^n}+1\) the \(n\)th Fermat number, sometimes denoted \(F_n\). A Fermat prime is a Fermat number which is also a prime number. Examples \(F_0=3\), \(F_1=5\), \(F_2=17\), \(F_3=257\) and \(F_4=65537\) are all Fermat primes. No other Fermat primes are currently known. We call a positive integer \(n\) a perfect number if it is equal to the sum of all its positive divisors (except \(n\) itself). Examples The positive divisors of 6 are 1,2 and 3 (and 6 itself) with 1+2+3=6 so 6 is a perfect number. The positive divisors of 28 are 1,2,4,7 and 14 (and 28 itself) with 1+2+4+7+14=28 so 28 is a perfect number. Proposition 17 Let \(m\) be a positive integer and suppose that \(2^m1\) is prime. Then \(m\) is also prime. proof Suppose \(m\) is not prime. If \(m=1\) then \(2^m1=1\) which is not prime, either. If instead \(m>1\) then (as \(m\) is not prime) \(m=rs\) for some integers \(r>1\) and \(s>1\) so \[ 2^m1=(2^r1)(2^{mr}+2^{m2r}+2^{m3r}+\ldots +2^r+1) \] and both factors on the right are greater than 1 so \(2^m1\) is not prime. Thus if \(2^m1\) is prime then \(m\) must also be prime. ∎ For each prime number \(p\), we call \(2^p1\) the Mersenne number with exponent \(p\). A Mersenne prime is a Mersenne number which is also a prime number. Examples \(M_2=3\) and \(M_3=7\) are Mersenne primes, as is \(M_{74207281}=2^{74207281}1\). \(M_{11}=2047\) is a Mersenne number but not a Mersenne prime. Far more details on Mersenne primes, perfect numbers and Fermat numbers can be found elsewhere on this forum, on the GIMPS website http://www.mersenne.org/ or on Chris Caldwell's Prime Pages https://primes.utm.edu/ . I'm sure other members will also suggest additional resources! Exercises 18. Let \(n\) be a positive integer and \(m\) the greatest integer such that \(m\leq\sqrt{n}\). Show that if 1 is the only factor of \(n\) that is less than or equal to \(m\) then \(n\) is prime. 19. Find positive integers \(k\),\(m\) & \(n\) for which \(12^k\times 22^m\times 33^n=27599616\). 20. Prove that there are infinitely many prime numbers which leave a remainder of 3 on division by 4. 21. Let \(q\) be a prime number greater than 2.
Last fiddled with by Nick on 20161014 at 16:12 Reason: Small typo in exercise 18. 
20161014, 16:28  #2 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Err... this will surely be one of the stupidest posts I've ever made (which sadly isn't particularly easy), but...
Let p=p be composite, a=p, and b greater than zero. (For instance p=a=6, b=2.) Then by construction, p  ab and p  a, despite p being composite. ? Is there some condition I'm missing that implicitly holds that p != a and p != b? 
20161014, 16:35  #3  
Aug 2006
13526_{8} Posts 
Quote:
The requirement is that for all a and b with p  ab, you have p  a or p  b. But if p = 6 then a = 3 and b = 4 have p  ab but neither p  a nor p  b. It's not enough to have one pair (a, b) with p  ab and p  a. 

20161014, 16:46  #4  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:
Last fiddled with by Dubslow on 20161014 at 16:46 

20161014, 17:12  #5 
Dec 2012
The Netherlands
1,621 Posts 
My use of the word "any" evidently made the intended meaning less clear.
I'll try to avoid it in the future! 
20161014, 17:34  #6 
Aug 2006
13526_{8} Posts 

20161014, 19:38  #7  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
7221_{10} Posts 
Quote:
On the other hand it's also clear that my math is a bit rusty, I think were I an active student I would have had no problems with getting the right interpretation. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Basic Number Theory 1 & 2  Nick  Number Theory Discussion Group  17  20171223 20:10 
Basic Number Theory 20: polynomials  Nick  Number Theory Discussion Group  5  20170425 14:32 
Basic Number Theory 14: a first look at groups  Nick  Number Theory Discussion Group  0  20161229 13:47 
Basic Number Theory 10: complex numbers and Gaussian integers  Nick  Number Theory Discussion Group  8  20161207 01:16 
Basic Number Theory 11: Gaussian primes  Nick  Number Theory Discussion Group  0  20161203 11:42 