Solutions

Part of the Oxford MAT Livestream

These are the solutions for the Primes & Proof worksheet.

Warm-up

  1. Are there any primes of the form \(n^2-1\) where \(n\) is a whole number?
    • The expression factorises to \((n-1)(n+1)\). Each bracket is a whole number, so if this is prime then one of those brackets must be the number \(1\). If \(n-1=1\) then \(n=2\), or if \(n+1=1\) then \(n=0\). Let's check whether those actually give primes or not; \(2^2-1=3\) is a prime number, but \(0^2-1=-1\) is not. Anyway, the answer is "yes", because \(3\) is an example of a prime of the form \(n^2-1\) with \(n\) a whole number, but that's the only one.
  2. Are there any primes of the form \(n^4-16\) where \(n\) is a whole number?
    • That's the difference of two squares again, and the expression factorises to \((n^2-4)(n^2+4)\). That first expression factorises again to give us \((n-2)(n+2)(n^2+4)\). This doesn't look very prime at all! If it's a prime number, then at least one of \((n-2)\) or \((n+2)\) or \((n^2+4)\) must be 1. So we should check \(n=3\) or \(n=-1\). Neither \(65\) nor \(-15\) are prime numbers, so this is never a whole number.
  3. Prove that if \(\sqrt[3]{3}=p/q\) with \(p\) and \(q\) both whole numbers, then both \(p\) and \(q\) are multiples of 3.
    • If \(\sqrt[3]{3}=p/q\) then, cubing each side, we have \(3=p^3/q^3\) so \(3q^3=p^3\). So \(p^3\) is definitely a multiple of 3 because it's 3 times \(q^3\) and \(q\) is a whole number.
    • What does that mean about \(p\)? Well, in general, the three possibilities are that \(p\) might be a multiple of 3, or it might be one more than a multiple of 3, or it might be two more than a multiple of 3. In the first case, we could write \(p=3k\) for some whole number \(k\), and then \(p^3=27k^3=3(9k^3)\) would be a multiple of 3. In the second case, we could write \(p=3k+1\) for some whole number \(k\), and then \(p^3=27k^3+27k^2+9k+1\) is not a multiple of 3. In the third case, we could write \(p=3k+2\) for some whole number \(k\), and then \(p^3=27k^3+54k^2+36k+4\) is not a multiple of 3. So the only possibility that works with the fact that \(p^3\) is a multiple of 3 is the case that \(p\) is a multiple of \(3\).
    • So now let's write \(p=3k\) for some whole number \(k\). We have \(3q^3=27p^3\) so \(q^3=9p^3\). So \(q^3\) is a multiple of 3. By the same logic as the previous part, this means that \(q\) is a multiple of 3.
  4. Prove that \(\sqrt[n]{2}\) is irrational for \(n>1\) a whole number.
    • Suppose \(\sqrt[n]{2}=p/q\) with \(p\) and \(q\) whole numbers and the fraction written in lowest terms (so no common factor shared between \(p\) and \(q\)). We can rearrange that equation to \(p^n=2q^n\), so \(p^n\) is even. Could \(p\) be an odd number? No, because an odd number to the power of \(n\) would be odd. So \(p\) is an even number. Let's write \(p=2k\) for some whole number \(k\). Then \(2^{n-1}k^n=q^n\). Since \(n>1\) the left-hand side is even. So \(q^n\) is even, and so \(q\) is even. So \(p\) and \(q\) are both even. But that's a contradiction; we said that the fraction was in lowest terms and then proved that \(p\) and \(q\) have a common factor of 2. So it must be impossible to write \(\sqrt[n]{2}\) as \(p/q\), so that number is irrational.
  5. 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\)".
    • There's an isosceles triangle with angles \(178^\circ,1^\circ,1^\circ\).
  6. Find a counter-example to the claim "\(n^2+n+41\) is prime for every positive whole number \(n\)".
    • Try \(n=41\). That's a multiple of \(41\), and it's not equal to 41 because it's too big.
  7. Find a counter-example to the claim "Every country's flag has either got some red or some white or some blue on it".
    • Jamaica.
  8. Prove that for any prime \(p\) that's bigger than four, \(p^2-1\) is a multiple of 24.
    • Difference of two squares \(p^2-1=(p-1)(p+1)\). Any prime \(p\) that's bigger than four is odd, so both of those brackets are even. In fact, the second bracket is the next even number after the one before, so either the first bracket or the second bracket is a multiple of 4, because every other even number is a multiple of 4. Any prime \(p\) that's bigger than four is not a multiple of 3, so one of the numbers \(p-1\) or \(p+1\) is a multiple of 3. Putting all that together, the prime factorisation of \((p-1)(p+1)\) includes at least three 2s (two from the multiple of 4 and one more from the other even number), and at least one 3. So this number is a multiple of \(2^3\times3=24\).
  9. Describe in words what the function \(f(x)=16x+5\) does to a binary number \(x\).
    • Multiplying by 16 means multiplying by \(2^4\), which is \(10000\) in binary. So multiplying by 16 means writing four zeros at the end of a binary number. Then adding five means adding \(101\) in binary, so overall this function takes the binary number \(x\) and writes \(0101\) at the end.
  10. 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\).
    • If \(x=2^n\) for some whole number \(n\), then \(x\) has a nice binary expansion \(100...000\) with \(n\) zeros. Also, \(f(x)=[n]=n\) and this is the first number where the function inside the square brackets is large enough to have \(f(x)=n\). In fact, \(f(x)=n\) for all numbers from \(x\) up to but not including \(2^{n+1}\). What do these numbers have in common? They've all got \(n+1\) digits in their binary expansion. The function \(f(x)\) is one less than the number of digits in the binary expansion of \(x\).
  11. 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.
    • The factors of \(16\) are \(1\), \(2\), \(4\), \(8\), and \(16\). It's got five factors.
    • The factors of \(63\) are \(1\), \(3\), \(9\), \(7\), \(21\), \(63\) (working systematically through the factors that aren't a multiple of seven first, then the factors that are a multiple of seven). It's got six factors.
    • Let's give the number \(p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}\) a name; let's call it \(N\). In general, a factor of \(N\) only includes primes that appear in that expression, and only has at most as many of any particular prime as \(N\) has. So any factor of \(N\) is a number of the form \(p_1^{m_1}p_2^{m_2}\dots p_n^{m_n}\) where \(0\leq m_i\leq k_i\) for each \(i\) between 1 and \(n\). We can make different factors of \(N\) by choosing different powers \(m_i\).
    • There are \((k_1+1)\) choices for the power \(m_1\) (0 or 1 or 2 or ... or \(k_1\)), and then separately \((k_2+1)\) choices for \(m_2\) and so. We make all these choices separately, so the total number of choices we've got when making a factor of \(N\) is \((k_1+1)\times(k_2+1)\times \dots \times (k_n+1)\).

 

MAT questions

MAT 2014 Q1H

  • Here are the first few values. \(F(2)=2\) because 2 divides 2 but 3 does not divide 2. Then \(F(3)=5\) because 3 divides 3 but 2 does not divide 3. Then \(F(4)=7\) and \(F(5)=7\) and \(F(6)=11\).
  • The overall pattern of whether or not numbers are multiples of 2 and/or 3 repeats every six numbers.
  • So the sequence of numbers that we're adding as we go along is 0, 2, 3, 2, 0, 4, 0, 2, 3, 2, 0, 4, 0, 2, 3, 2, 0, 4,...
  • When we get to \(F(6000)\), we'll have added one thousand copies of 0, 2, 3, 2, 0, 4. That's one thousand times 11.
  • The answer is (c).

 

MAT 2015 Q1A

  • If we write \(n\) for the initial number, then the final answer is \(4n^2+8n+1\).
  • We could check values when \(n\) is 0 or 1 or 2. Those inputs give the outputs 1 or 13 or 33. The possibility of 33 shows that II is false because 33 is not one more than a multiple of 3. The possibility of 13 shows that III is false because 13 is not one more than a multiple of 8. The possibility of 13 also shows that IV is false because 13 is prime. So the answer is (e).
  • For completeness, let's try and prove the other two. I is true because \(4n^2+8n\) is even so \(4n^2+8n+1\) is odd. V is true, but that's a little harder to prove. There are three possibilities for \(n\); it's either a multiple of 3, or it's one more or two more than a multiple of 3. In the first case, the final answer is one more than a multiple of \(n\) so one more than a multiple of 3. In the second case \(n=3k+1\) for some integer \(k\) and \(4n^2+8n+1=36k^2+48k+13\) is again one more than a multiple of 3, and in the third case \(n=3k+2\) for some integer \(k\) and \(4n^2+8n+1=36k^2+72k+33\) is a multiple of 3. So the final answer can never be one less than a multiple of 3.
  • The answer is (e).

 

MAT 2015 Q2

(i) Lots of multiplying out to do here; I get \[a^{n+1}-a^nb + a^nb-a^{n-1}b^2+a^{n-1}b^2-a^{n-2}b^3+\dots +a^2b^{n-1}-ab^n+ab^n-b^{n+1}\]
    which almost all cancels out to leave \(a^{n+1}-b^{n+1}\). This shows that \((a-b)\) is a factor of \(a^{n+1}-b^{n+1}\).

(ii) We could write such a prime number as \(n^2-1\). But then that factorises as \((n-1)(n+1)\) (using the fact in part (i) with \(n=2\), or just recognising the difference of two squares). If that's a prime number then one of those brackets should be 1. But then the only possibilities are \(n=2\) or \(n=0\). The first case gives the prime \(3\), and the second case gives \(-1\) which isn't prime. So no, there are no other prime numbers with this property.

(iii) We might like to repeat the method above for the expression \(n^3+1\). For that reason, I'm going to look for a factor of \(n^3+1\). This feels just like factorising a polynomial, so I could think about factoring out \((n+1)\). Or instead, we could use part (i) with \(a=n\) and \(b=-1\). Either way, the expression factorises to \((n+1)(n^2-n+1)\). Are either of those brackets equal to one? A quick bit of algebra shows that no, not unless \(n=0\) or \(n=1\), and that just gives the prime \(2=1^3+1\). So that's the only prime with this property.

(iv) I'd like to use part (i) because this is a difference between two powers, and we showed that the difference of two powers has a factor in part (i). I've got to be careful not to pick \(a=3\) and \(b=2\) because then the factor that I get would be \(a-b=1\), which is a trivial factor! Instead, if I pick \(a=3^{403}\) and \(b=2^{403}\) then I can use part (i) with \(n=4\) to show that \(3^{403}-2^{403}\) is a factor of this number. That's huge and I don't want to work it out, but we've shown that \(3^{2015}-2^{2015}\) isn't a prime number.

(v) We can check some small values of \(k\) to see what's going on. If \(k=1\) then we get \(4\), if \(k=2\) then we get 21, if \(k=3\) then we get 52. As I was working these out, I noticed that each one wasn't as big as the next cube number that I had to work out. So I think that \(k^3+2k^2+2k+1<(k+1)^3\). If that's true then this number is somewhere in between \(k^3\) and \((k+1)^3\) so it can't be a cube number. OK, to prove this I can multiply out the right-hand side and then simplify a bit, and the thing I'm claiming is equivalent to \(k^2+k>0\). That's true, because \(k^2+k=k(k+1)\) is the product of two positive integers. So this expressions is in between consecutive cube numbers and cannot be a cube number itself.

 

MAT 2013 Q5

(i) There are nine; the last digit could be anything from 0 to 8, and then in each case the first digit can be uniquely chosen to make the digit sum equal to 8.

(ii) This is a generalisation of the previous part to other numbers for the digit sum. There are now \(n+1\) possibilities for the last digit; 0 up to \(n\) are all possible last digits since \(n<10\). In each case there is one unique choice for the other digit to make the digit sum equal to \(n\).

(iii) Let's think about the possibilities for the last digit. Perhaps this will be easier if we work in the special case \(n=2\) to start with. Then the last digit could be 0 or 1 or 2 (but not anything else). If the last digit is 2 then we've already reached a digit sum of 2, so we must have 0 for both the other digits. If the last digit is 1, then we need another 1 in one of the other digits; two possibilities. If the last digit is 0, then there are three possibilities; we can have a 2 as the second digit, or a 1, or a 0 (and then we can make the digit sum equal to 2 by choosing the first digit correctly). Overall, that's \(1+2+3=6\) possibilities.

In general for a digit sum of \(n\), the possibilities follow a similar pattern; if we write \(n\) for the last digit then there is only one possibility for the other digits, but if the last digit is \(k<n\) then the number of possibilities for the other two digits is \(n-k+1\) using part (ii). Adding these all up gives \(1+2+\dots+n+(n+1)=\frac{1}{2}(n+1)(n+2)\).

(iv) In this part we're told that the first digit is 5 or 6 or 7 or 8 (it can't be 9). Then we can work through each case to find the ten possibilities for the integer with digit sum equal to 8; they are 503, 512, 521, 530, 602, 611, 620, 701, 710, 800.

(v) Maybe it's the first digit which is at least five, which would lead to the ten integers above. Or maybe it's the second digit which is at least five, which gives ten different integers 350, 251, 152, 053, 260, 161, 062, 170, 071, 080, which I've made by shifting the digits of each of the previous ten integers, moving the last digit to the front. Or maybe it's the third digit which is at least five, in which case there are ten more integers for a similar reason. That's a total of 30 integers.

(vi) That total involves the sum of all the first digits, the sum of all the second digits, and the sum of all the last digits. First think about the first digit; that takes the value 0 one-hundred times, then it's 1 for the next hundred integers, and so on. The sum of the first digit of each integer is therefore \(100(0+1+2+3+\dots+8+9)=4500\). With some similar careful counting (or by thinking about how each digit cycles through the possible numbers and is about to hit zero again if we go to the number 1000), we see that the sum of all the second digits is also \(4500\) and the sum of all the third digits is also \(4500\). That gives a final answer \(13500\).

 

Reflection

  • Giving things names is helpful. I wrote \(N\) for \(p_1^{k_1}p_2^{k_2}\dots p_n^{k_n}\) above and then I could say things like "a factor of \(N\)" rather than writing it all out again. If you're worried about your handwriting, then giving an expression a name that is a big unambiguous symbol that's easier for you to write might help. And even if you have great handwriting, who wants to write out all those little letters and numbers each time? Not me.
  • There is a really subtle difference between the statement "for all positive whole numbers \(k\) there is a positive whole number which is one more than \(k\)" and the statement "there is a positive whole number which, for all positive whole numbers \(k\), is one more than \(k\)". That's part of the reason that questions like MAT 2016 Q1J are tricky.
  • The last part of MAT 2013 Q5 involved the idea that instead of summing the digits of each number and then adding, we could rearrange the sum so that we added together all the first digits instead. Watch out for times when you can change the order of operations like this; it's helpful here that we're adding everything together (so we can happily rearrange it like this). Note that if we wanted the product of all the digit sums of the integers from 1 to 999 then we'd have to do a lot more work because we wouldn't be able to rearrange like this.
Please contact us with feedback and comments about this page. Last updated on 03 Aug 2022 10:36.