Basic Number Theory 4: a first look at prime numbers

[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. 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 \(n<N\).
In the case \(n=N\), let \(b=a_1a_2a_3\ldots a_{n-1}\).
Then \(p|ba_n\) and \(p\) is a prime number so, by property (B), \(p|b\) or \(p|a_n\).
If \(p|b\) then \(p|a_1a_2a_3\ldots a_{n-1}\) and, by our assumption, there exists \(i\in\{1,2,3,\ldots,n-1\}\) such that \(p|a_i\).
If instead \(p|a_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 non-negative 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_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 \(k<m\) then, by our assumption, \(m-1=n-1\) and \(p_1=q_1\), \(p_2=q_2\) etc. up to and including \(p_{n-1}=q_m\) (missing out \(p_n\) and \(q_k\)).
But then \(p_{n-1}\leq p_n=q_k\leq q_m=p_{n-1}\) 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, \(m-1=n-1\) and \(p_i=q_i\) for all integers \(i\) with \(1\leq i\leq n-1\).
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^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.

1. List the 6 positive divisors of \(4q\) and show that their sum is \(7(q+1)\).
2. 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)\).
3. 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.

[Dubslow]

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?

[CRGreathouse]

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.

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.

[Dubslow]

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.

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)

[Nick]

My use of the word "any" evidently made the intended meaning less clear.
I'll try to avoid it in the future!

[CRGreathouse]

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.

[Dubslow]

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.