Primes & Proof

MAT syllabus

[There is no content on primes or proof explicitly on the MAT syllabus, but candidates are expected to know material from GCSE or equivalent.]

Revision

A whole number $d$ is a "factor" (or "divisor") of another whole number $n$ if there exists a whole number $k$ with $n=dk.$ If this is the case, then we say that "$d$ divides $n$".
A prime number is a whole number greater than 1 which has no factors except for 1 and itself.
A rational number is a number that can be written as $p/q$ where $p$ and $q$ are whole numbers. An irrational number is a number that is not rational.
It's sometimes a good idea to prove a statement by showing that if it's not true then nonsense follows as a result. For example, here is a proof that $\displaystyle \frac{\ln 2}{\ln 3}$ is irrational.
- Suppose that $\displaystyle \frac{\ln 2}{\ln 3}$ is a rational number.
- Then $\displaystyle \frac{\ln 2}{\ln 3}=\frac{p}{q}$ for some whole numbers $p>0$ and $q>0$.
- This rearranges to $q\ln2=p\ln 3$ so $2^p=3^q$.
- But the left-hand side is even and the right-hand side is odd.
- So the supposition in the first line is false, and $\displaystyle \frac{\ln 2}{\ln 3}$ is not a rational number.
If a whole number $n$ is even, then we can write it as $n=2m$ for some whole number $m$. If $n$ is odd, then we can write it as $n=2m+1$. Similarly, all numbers can either be written as $3m$ or $3m+1$ or $3m+2$ for some whole number $m$. Sometimes checking these different cases can help us to prove something.
A "counterexample" to a claim is an example that demonstrates that the claim is not true. For example, if I make the claim "all square numbers are odd" then you could give $4^2=16$ as a counter-example to prove me wrong, but $5^2=25$ and $\sin(30^\circ)=\frac{1}{2}$ are not counter-examples.
Sometimes we're asked to show that something (call it $P$) is "sufficient" for something else (call it $Q$). We can show that $P$ is sufficient by showing that if $P$ is true then $Q$ is also true.
Sometimes we're asked to show that something (call it $P$) is "necessary" for something else (call it $Q$). We can show that $P$ is necessary for $Q$ by showing that if $Q$ is true, then $P$ is also true.

Warm-up

Are there any primes of the form $n^2-1$ where $n$ is a whole number?
Are there any primes of the form $n^4-16$ where $n$ is a whole number?
Suppose that $\sqrt[3]{3}$ is a rational number. Prove that if $\sqrt[3]{3}=p/q$ with $p$ and $q$ both whole numbers, then both $p$ and $q$ are multiples of 3.
[Hint: you'll need to consider cases for what happens when you cube different numbers.]
(if this were the case, then we could divide both of $p$ and $q$ by 3 and repeat the argument, again and again, making $p$ smaller every time, which is eventually impossible. So $\sqrt[3]{3}$ is irrational.)
Prove that $\sqrt[n]{2}$ is irrational for $n> 1 $ a whole number.
Find a counter-example to the claim "in any triangle, the difference between the biggest angle and the smallest angle is at most $90^\circ$".
Find a counter-example to the claim "$n^2+n+41$ is prime for every positive whole number $n$".
Find a counter-example to the claim "Every country's flag has either got some red or some white or some blue on it".
Prove that for any prime $p$ that's bigger than four, $p^2-1$ is a multiple of 24.
We can write a number in binary by writing it as a sum of powers of $2$, and recording with 1s or 0s which powers of 2 we've used. This is a bit like writing a number in decimal, but the place values are powers of 2 rather than powers of 10. So the number 110 in binary means $1\times2^2+1\times2^1+0\times 2^0$ which in decimal we would write as $6$. The number 23 in decimal is $16+4+2+1$ so we'd write it as $10111$ in binary (that zero is for the missing $2^3=8$). Describe in words what the function $f(x)=16x+5$ does to a binary number $x$.
We denote by $[x]$ the largest integer less than or equal to $x$, so $[\pi]=3$ and $[-e]=-3$ and $[1]=1$ for example. Describe in words the relationship between the function $f(x)=[\log_{2}x]$ and the binary expansion of $x$.
How many different factors does the number $16=2^4$ have? How many different factors does the number $63=3^2\times 7$ have? Prove that in general, the number $p_1^{k_1}\times p_2^{k_2}\times \dots \times p_n^{k_n}$ where the $p_i$ are different prime numbers has $(k_1+1)\times(k_2+1)\times \dots \times (k_n+1)$ factors.

MAT questions

MAT 2014 Q1H

The function $F(n)$ is defined for all positive integers as follows: $F(1)=0$ and for all $n\geq 2$,

\begin{eqnarray*}
F(n)&=&F(n-1)+2 & \quad \text{if 2 divides $n$ but 3 does not divide $n$;}\\
F(n)&=&F(n-1)+3 & \quad \text{if 3 divides $n$ but 2 does not divide $n$;}\\
F(n)&=&F(n-1)+4 & \quad \text{if 2 and 3 both divide $n$;}\\
F(n)&=&F(n-1) & \quad \text{if neither 2 nor 3 divides $n$.}\\
\end{eqnarray*}

The value of $F(6000)$ equals

(a) 9827,

(b) 10121,

(d) 12300,

(e) 12352.

Hint: Follow the rules to work out $F(2)$ and$F(3)$ and a few more. As you calculate these, when do you expect to see a pattern?

MAT 2015 Q1A

Pick a whole number.
Add one.
Square the answer.
Multiply the answer by four.
Subtract three.

Which of the following statements are true regardless of which starting number is chosen?

I: The final answer is odd.
II:The final answer is one more than a multiple of three.
III: The final answer is one more than a multiple of eight.
IV: The final answer is not prime.
V: The final answer is not one less than a multiple of three.

(a) I, II, and V,

(b) I and IV,

(d) I, III, and V,

(e) I and V.

Hint: try some small whole numbers.

MAT 2015 Q2

(i) Expand and simplify
\[(a-b)(a^n+a^{n-1}b + a^{n-2}b^{2} + \dotsb + ab^{n-1} + b^n).\]

(ii) The prime number $3$ has the property that it is one less than a square number. Are there any other prime numbers with this property? Justify your answer.

(iii) Find all the prime numbers that are one more than a cube number. Justify your answer.

(iv) Is $3^{2015} - 2^{2015}$ a prime number? Explain your reasoning carefully.

(v) Is there a positive integer $k$ for which $k^3 + 2k^2 + 2k + 1$ is a cube number? Explain your reasoning carefully.

Hint: In part (iv), be very careful in your choice of $a$ and $b$, because even prime numbers are allowed to be a multiple of 1. Is there another choice that let's us use part (i), perhaps with different values of $a$ and $b$ to factorise the expression in part (iv)?

MAT 2013 Q5

We define the digit sum of a non-negative integer to be the sum of its digits. For example, the digit sum of 123 is $1+2+3=6$.

(i) How many positive integers less than 100 have digit sum equal to 8?

Let $n$ be a positive integer with $n<10$.

(ii) How many positive integers less than 100 have digit sum equal to $n$?

(iii) How many positive integers less than 1000 have digit sum equal to $n$?

(iv) How many positive integers between 500 and 999 have digit sum equal to 8?

(v) How many positive integers less than 1000 have digit sum equal to 8, and one digit at least 5?

(vi) What is the total of the digit sums of the integers from 0 to 999 inclusive?

Hint: This question doesn't involve any primes or proofs, but you will need to work carefully and to think logically. I'm including it to demonstrate that MAT questions might be based on very limited mathematics indeed!

Extension

The following material is included for your interest only, and not for MAT preparation.

There's a lovely proof that there are infinitely many prime numbers, which you might have seen before;

Suppose there are only finitely many primes $p_1$, $p_2$, $p_3$, $\dots$, $p_n$.
Consider $N=p_1\times p_2\times p_3\times p_n+1$.
This must have at least one prime factor (possibly just itself, if it's prime).
But on the other hand, it's not a multiple of $p_1$ or $p_2$ or $p_3$ or $\dots$ or $p_n$.
This is a contradiction.
So there must be infinitely many primes.

Even better, we can use a modified version of this proof to prove that there are infinitely many primes which are each three more than a multiple of 4.

First, a couple of notes; every odd number is either one more than a multiple of 4 or three more than a multiple of 4. If you multiply together two numbers that are each one more than a multiple of 4, you get something which is one more than a multiple of 4 (that's like a more advanced version of the fact that ``odd times odd is odd"). Now for the proof;

Suppose there are only finitely many primes that are three more than a multiple of 4; $p_1$, $p_2$, $p_3$, $\dots$, $p_n$.
Consider $N=4\times p_1\times p_2\times p_3\times p_n-1$.
This must have at least one prime factor (possibly just itself, if it's prime).
Not all of the prime factors of $N$ are one more than a multiple of 4, because if they were then $N$, the product of those primes, would also be one more than a multiple of 4 (and $N$ is clearly 3 more than a multiple of 4).
So $N$ has a prime factor that's three more than a multiple of 4.
But on the other hand, it's not a multiple of $p_1$ or $p_2$ or $p_3$ or $\dots$ or $p_n$.
This is a contradiction.
So there must be infinitely many primes that are three more than a multiple of 4.

Sadly, there isn't a matching proof with $N=4\times p_1\times p_2\times p_3\times p_n+1$ to show that there are infinitely many primes that are one more than a multiple of 4 (but it is a true fact that there are infinitely many such primes!). You might like to look carefully at the proof above and work out where it would go wrong. I know a proof that uses Fermat's Little Theorem, but I don't have space in this Extension to describe what that is.