Chapter 24 More conjectures II: Prime numbers
The primes are a fascinating family of numbers. They are the building blocks of the integers, because every number is either prime or is the product of primes. For that reason, this chapter presents a whole set of conjectures on the primes.
Remember, the first few primes are \(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\), \(101\), \(103\), \(107\), \(109\), \(113\)….
The first \(10,000\) primes are listed here: https://primes.utm.edu/lists/small/10000.txt.
And remember that non-prime positive integers, such as \(1, 4, 6, 8, 9, 10, 12, 14, 15, ...\) are called composite numbers.56
24.1 Work through in order, building on your earlier work
It is recommended that you work through the conjectures below in order, not because they get more difficult, but because later conjectures build on earlier ones. For example, proving the conjecture
Conjecture 24.1 : Every prime number, except \(2\) and \(3\), is either one more or one less than a multiple of \(6\).
will help you in proving the conjecture
Conjecture 24.2 : Doubling any prime number (except 2) then adding two creates a number divisible by four.
First, try to the prove Conjecture 24.1. (Hint: You might want to try writing the positive integers greater than \(3\) in a rectangular grid, in such a way that all the primes are in only one or two columns.).
Once you’ve done that, see how your work on Conjecture 24.1 can help you in proving Conjecture 24.2:
Proof. As conjecture 24.1 is known to be true, we know that every prime \(p\), \(p \neq 2, 3\), can be written in the form
\[\begin{align} p &= 6k + 1 \end{align}\]
or
\[\begin{align} p &= 6k - 1 \end{align}\]
with \(k \in \mathbb Z\).
Let’s deal with these one-by-one:
Case 1: If
\[\begin{align} p &= 6k + 1 \end{align}\]
then doubling it and adding two gives
\[\begin{align} 2p + 2 &= 2(6k + 1) + 2 \\ &= 12p + 2 + 2 \\ &= 12p + 4 \\ &= 4(3p + 1) \end{align}\]
which is a multiple of 4.
Case 2: If
\[\begin{align} p &= 6k - 1 \end{align}\]
then doubling it and adding two gives
\[\begin{align} 2p + 2 &= 2(6k - 1) + 2 \\ &= 12p - 2 + 2 \\ &= 12p \\ &= 4(3p) \end{align}\]
which is a multiple of 4.
As noted in the first line of the proof, this proof covers all primes except \(2\) and \(3\). However, conjecture 24.2 covers all primes except \(2\), so we should also check that the conjecture holds for \(3\).
Case 3: If \(p=3\), then \(2p+2 = 2 \cdot 3 + 2 = 6 + 2 = 8\), which is a multiple of \(4\).
Therefore the conjecture is true.
24.2 Conjectures
As always, be aware that some of these conjectures are false, and should be disproved using a counterexample or a disproof.
Conjecture 24.3 : There are an infinite amount of prime numbers.
Hint: See 12:30-14:45 of https://www.youtube.com/watch?v=OihQPf4mJH4.
Look back to Conjecture 13.15. Now attempt these two conjectures:
Conjecture 24.4 : \(a^2 - a + 41\) is always prime for all positive integers \(a\).
Conjecture 24.5 : \(a^2 - a + 41\) is always prime for all nonpositive integers \(a\).
Conjecture 24.6 : All primes are odd.
Conjecture 24.7 : There are no positive integers \(a\) and \(b\) with \(a\) prime and \(a = 6b + 3\).
Conjecture 24.8 : There are no positive integers \(a\) and \(b\) with \(a\) prime and \(a = 6b + 5\).
Conjecture 24.9 : For every positive composite integer \(b\), if some prime number \(a\) divides \(b\), then some other prime \(c\) (with \(c\) able to be the same as \(a\)) also divides \(b\).
Conjecture 24.10 : For every positive composite integer \(b\), if some prime number \(a\) divides \(b\), then some other prime \(c\) (with \(c\) \(\neq\) \(a\)) also divides \(b\).
Conjecture 24.11 : For any positive integers \(a\) and \(b\), where \(a \neq 1\), if \((a^b + 1)\) is prime then \(a\) is even.
Conjecture 24.12 : If \(a\) is a prime number and \(a\) | \(b\), then \(a\nmid (b+1)\).
Conjecture 24.13 : Every positive integer can be written as the sum of two composite integers.
Conjecture 24.14 : Every integer greater than 11 can be written as the sum of two composite integers.
Large primes are essential for online security, banking and encryption. There’s a search for larger and larger primes to keep the Internet private. One method of finding possible primes is \(2^{a} - 1\), where \(a\) is a positive integer.
Conjecture 24.15 : Let \(a\) be a positive integer. \(2^{a} - 1\) is always prime.
Conjecture 24.16 : Let \(a\) be a positive composite integer. \(2^a - 1\) is always prime.
Conjecture 24.17 : Let \(a\) be a prime number. \(2^a - 1\) is always prime.
Conjecture 24.18 : If \(2^a - 1\) is prime, then \(a\) is prime.
Hint: Try a proof by contrapositive.
Hint: For integers \(x,y\), \(x^n + y^n = (x-y)(x^{n-1} + x^{n-2}y + x^{n-3}y^2 + ... xy^{n-2} + y^{n-1})\).
Conjecture 24.19 : For a positive integer \(a\), at least one of \(2^{a}-1\) and \(2^{a}+1\) isn’t prime.
Conjecture 24.20 : For a positive integer \(a\), at least one of \(2^{a}-1\) and \(2^{a}+1\) is prime.
Conjecture 24.21 : For a positive integer \(a\), exactly one of \(2^{a}-1\) and \(2^{a}+1\) is prime.
Conjecture 24.22 : If the greatest common divisor of two positive integers, \(a\) and \(b\), is \(> 1\), then either \(b\) | \(a\) or \(b\) is composite.
Conjecture 24.23 : If \(a\) is an integer greater than \(1\), then none of the numbers \(a!+2\), \(a!+3\), \(a!+4\), \(a!+5\), …, \(a!+ a\) are prime.
Hint: This conjecture could be expressed as: “If \(a \in \mathbb{Z}\) and \(a \geq 2\), there exists \(a-1\) consecutive composite numbers.”
Conjecture 24.24 : Every integer greater than \(1\) has at least one prime divisor.
WARNING: This one’s tough!