 mersenneforum.org > Math Basic Number Theory 4: a first look at prime numbers
 Register FAQ Search Today's Posts Mark Forums Read 2016-10-14, 15:56 #1 Nick   Dec 2012 The Netherlands 2·32·83 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: property (A): $$p>1$$ and $$p$$ has no positive factors except 1 and $$p$$ itself; property (B): $$p>1$$ and, for any integers $$a$$ and $$b$$, if $$p|ab$$ then $$p|a$$ or $$p|b$$ (or both). (Note: from now on, we shall omit the "or both" in statements like that above. In mathematics, if we say "X is true or Y is true" (for some claims X and Y), we always mean "or both" unless explicitly stated otherwise.) 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 $$a|p$$ so $$ab=p$$ for some integer $$b$$, and $$p$$ & $$a$$ are both positive, so $$b>0$$ too. Now $$p|p=ab$$ so (by property (B)) $$p|a$$ or $$p|b$$. If $$p|a$$ 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 $$p|b$$ 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 $$p|ab$$ 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 $$p|ab$$ so $$pt=ab$$ for some integer $$t$$. Thus $$b=(mp+na)b=mpb+npt=p(mb+nt)$$ from which we have $$p|b$$. 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 $$r|q$$ and $$q|c$$ so $$r|c$$ (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 $$p|a_1a_2a_3\ldots a_n$$. Then there exists $$i\in\{1,2,3,\ldots,n\}$$ such that $$p|a_i$$. proof Induction on $$n$$. In the case $$n=1$$, we already have $$p|a_1$$ so $$i=1$$ suffices. Take any integer $$N>1$$ and suppose the lemma holds for all positive integers $$n$$ with $$n1$$ and suppose all positive integers $$a$$ with $$a1$$) $$a$$ has a positive factor other than 1 and $$a$$ itself, so $$a=bc$$ for some integers $$b,c$$ with $$10$$ and suppose the claim holds for all integers $$n$$ with $$0\leq n0$$ and $$p_1p_2\ldots p_n=q_1q_2\ldots q_m$$ so $$m>0$$ and $$p_n|q_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_n|q_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_{n-1}=q_1\ldots q_{k-1}q_{k+1}\ldots q_m$$. If $$k1$$, $$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^n-1$$. For example, $$2^{15}+1$$ is not prime since $2^{15}+1=(2^3+1)(2^{12}-2^9+2^6-2^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^{(2r-1)s}+2^{(2r-2)s}-2^{(2r-3)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^m-1$$ is prime. Then $$m$$ is also prime. proof Suppose $$m$$ is not prime. If $$m=1$$ then $$2^m-1=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^m-1=(2^r-1)(2^{m-r}+2^{m-2r}+2^{m-3r}+\ldots +2^r+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$$ must also be prime. ∎ For each prime number $$p$$, we call $$2^p-1$$ 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. List the 6 positive divisors of $$4q$$ and show that their sum is $$7(q+1)$$. Show that, for any positive integer $$n$$, the sum of the positive divisors of $$2^{n-1}q$$ (including $$2^{n-1}q$$ itself) is $$(2^n-1)(q+1)$$. Let $$p$$ be a prime number for which $$2^p-1$$ is also prime. Show that $$2^{p-1}(2^p-1)$$ is a perfect number. Last fiddled with by Nick on 2016-10-14 at 16:12 Reason: Small typo in exercise 18.   2016-10-14, 16:28 #2 Dubslow Basketry That Evening!   "Bunslow the Bold" Jun 2011 40 2016-10-14, 16:35   #3
CRGreathouse

Aug 2006

2·2,969 Posts Quote:
 Originally Posted by Nick Let $$p$$ be an integer, and consider the following two properties which $$p$$ may have: property (A): $$p>1$$ and $$p$$ has no positive factors except 1 and $$p$$ itself; property (B): $$p>1$$ and, for any integers $$a$$ and $$b$$, if $$p|ab$$ then $$p|a$$ or $$p|b$$ (or both). (Note: from now on, we shall omit the "or both" in statements like that above. In mathematics, if we say "X is true or Y is true" (for some claims X and Y), we always mean "or both" unless explicitly stated otherwise.) 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.

Quote:
 Originally Posted by Dubslow 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?
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.   2016-10-14, 16:46   #4
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

719710 Posts Quote:
 Originally Posted by CRGreathouse 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.
Quote:
 Originally Posted by Dubslow Err... this will surely be one of the stupidest posts I've ever made (which sadly isn't particularly easy), but...
Hypothesis confirmed I swear I've passed a number theory course (and several other maths courses besides)

Last fiddled with by Dubslow on 2016-10-14 at 16:46   2016-10-14, 17:12 #5 Nick   Dec 2012 The Netherlands 27268 Posts My use of the word "any" evidently made the intended meaning less clear. I'll try to avoid it in the future!   2016-10-14, 17:34   #6
CRGreathouse

Aug 2006

134628 Posts Quote:
 Originally Posted by Dubslow Hypothesis confirmed No worries, I'd much rather have a student making a mistake like that than a student who doesn't ask because (s)he doesn't think about it.   2016-10-14, 19:38   #7
Dubslow

"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×2,399 Posts Quote:
 Originally Posted by Nick My use of the word "any" evidently made the intended meaning less clear. I'll try to avoid it in the future!
Yes that was one of my thoughts afterwards, is that this particular English word isn't a particularly great one.

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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 17 2017-12-23 20:10 Nick Number Theory Discussion Group 5 2017-04-25 14:32 Nick Number Theory Discussion Group 0 2016-12-29 13:47 Nick Number Theory Discussion Group 8 2016-12-07 01:16 Nick Number Theory Discussion Group 0 2016-12-03 11:42

All times are UTC. The time now is 06:19.

Tue Nov 24 06:19:39 UTC 2020 up 75 days, 3:30, 4 users, load averages: 2.47, 2.13, 2.11