Problems

Filters
Clear Filters

16 problems found

2022 Paper 3 Q2
D: 1500.0 B: 1500.0
number theory proof by contradiction infinite descent divisibility diophantine equation modular arithmetic

  1. Suppose that there are three non-zero integers \(a\), \(b\) and \(c\) for which \(a^3 + 2b^3 + 4c^3 = 0\). Explain why there must exist an integer \(p\), with \(|p| < |a|\), such that \(4p^3 + b^3 + 2c^3 = 0\), and show further that there must exist integers \(p\), \(q\) and \(r\), with \(|p| < |a|\), \(|q| < |b|\) and \(|r| < |c|\), such that \(p^3 + 2q^3 + 4r^3 = 0\). Deduce that no such integers \(a\), \(b\) and \(c\) can exist.
  2. Prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(9a^3 + 10b^3 + 6c^3 = 0\).
  3. By considering the expression \((3n \pm 1)^2\), prove that, unless an integer is a multiple of three, its square is one more than a multiple of \(3\). Deduce that the sum of the squares of two integers can only be a multiple of three if each of the integers is a multiple of three. Hence prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(a^2 + b^2 = 3c^2\).
  4. Prove that there are no non-zero integers \(a\), \(b\) and \(c\) for which \(a^2 + b^2 + c^2 = 4abc\).

View
2020 Paper 2 Q5
D: 1500.0 B: 1500.0
number theory digit sum divisibility modular arithmetic proof base 10 representation exhaustive search

If \(x\) is a positive integer, the value of the function \(\mathrm{d}(x)\) is the sum of the digits of \(x\) in base 10. For example, \(\mathrm{d}(249) = 2 + 4 + 9 = 15\). An \(n\)-digit positive integer \(x\) is written in the form \(\displaystyle\sum_{r=0}^{n-1} a_r \times 10^r\), where \(0 \leqslant a_r \leqslant 9\) for all \(0 \leqslant r \leqslant n-1\) and \(a_{n-1} > 0\).

  1. Prove that \(x - \mathrm{d}(x)\) is non-negative and divisible by \(9\).
  2. Prove that \(x - 44\mathrm{d}(x)\) is a multiple of \(9\) if and only if \(x\) is a multiple of \(9\). Suppose that \(x = 44\mathrm{d}(x)\). Show that if \(x\) has \(n\) digits, then \(x \leqslant 396n\) and \(x \geqslant 10^{n-1}\), and hence that \(n \leqslant 4\). Find a value of \(x\) for which \(x = 44\mathrm{d}(x)\). Show that there are no further values of \(x\) satisfying this equation.
  3. Find a value of \(x\) for which \(x = 107\mathrm{d}\left(\mathrm{d}(x)\right)\). Show that there are no further values of \(x\) satisfying this equation.

View
2019 Paper 1 Q7
D: 1500.0 B: 1500.0
proof by contradiction irrationality divisibility surds number theory modular arithmetic coprime integers

Consider the following steps in a proof that \(\sqrt{2} + \sqrt{3}\) is irrational.

  1. If an integer \(a\) is not divisible by 3, then \(a = 3k \pm 1\), for some integer \(k\). In both cases, \(a^2\) is one more than a multiple of 3.
  2. Suppose that \(\sqrt{2} + \sqrt{3}\) is rational, and equal to \(\frac{a}{b}\), where \(a\) and \(b\) are positive integers with no common factor greater than one.
  3. Then \(a^4 + b^4 = 10a^2b^2\).
  4. So if \(a\) is divisible by 3, then \(b\) is divisible by 3.
  5. Hence \(\sqrt{2} + \sqrt{3}\) is irrational.
  1. Show clearly that steps 1, 3 and 4 are all valid and that the conclusion 5 follows from the previous steps of the argument.
  2. Prove, by means of a similar method but using divisibility by 5 instead of 3, that \(\sqrt{6} + \sqrt{7}\) is irrational. Why can divisibility by 3 not be used in this case?

Solution:

  1. Step 1: There are only three possibilities for the remainder of \(a\) when divided by \(3\), (\(0\), \(1\), \(2\)). \(a = 3m+r\). If \(r = 0\) we are done, if \(r = 1\) take \(k = m\), and \(r=2\) take \(k=(m+1)\) and we have \(a = 3k-1\) as required. Then \(a^2 = (3k\pm1)^2 =9k^2\pm6k+1 = 3(3k^32\pm2k)+1\) which is clearly \(1\) more than a square. Step 3: \begin{align*} && \frac{a}{b} &= \sqrt{2}+\sqrt{3} \\ \Rightarrow && \frac{a^2}{b^2} &= 5+2\sqrt{6} \\ \Rightarrow && \frac{a^2}{b^2}-5 &= 2\sqrt{6} \\ \Rightarrow && 24 &= \left ( \frac{a^2}{b^2}-5 \right)^2 \\ &&&= 25 + \frac{a^4}{b^4}-10\frac{a^2}{b^2} \\ \Rightarrow && -b^4 &= a^4-10a^2b^2 \\ \Rightarrow && a^4+b^4 &= 10a^2b^2 \end{align*} Step 4: If \(a\) is divisible by \(3\) then \(b^4 = 10a^2b^2-a^4\) is a multiple of \(3\), but if \(b\) was not a multiple of \(3\) then \(b^2\) would be \(1\) more than a multiple of \(3\) (by Step 3) and \(b^4\) would also be \(1\) more than a multiple of \(3\), and we would have a contradiction. Step 5: Follows since either \(a,b\) are both divisible by \(3\) (contradicting Step 2), or neither is, but then \(a^2\) and \(b^2\) are both one more than a multiple of \(3\) and the RHS is one more than a multiple of \(3\) but the LHS is \(2\) more than a multiple of \(3\) which is a contradiction.
  2. Step 1: If \(a\) is not divisible by \(5\) then \(a^2 \equiv \pm 1 \pmod{5}\) Step 2: Suppose \(\frac{a}{b} = \sqrt{6}+\sqrt{7}\) Step 3: \begin{align*} && \frac{a}{b} &= \sqrt{6}+\sqrt{7} \\ \Rightarrow && \frac{a^2}{b^2} &= 13 + 2\sqrt{42} \\ \Rightarrow && 168 &= \left (\frac{a^2}{b^2} - 13 \right)^2 \\ &&&= 169 - 26 \frac{a^2}{b^2} + \frac{a^4}{b^4} \\ \Rightarrow && a^4+b^4 &= 26a^2b^2 \end{align*} Step 4: If \(a\) is a multiple of \(5\) then so is \(b^4\) and hence so is \(b^2\) and \(b\). Step 5: But the left hand side is always \(2 \pmod{5}\) and the right hand side is never \(2 \pmod{5}\) contradiction. Divisibility by \(3\) doesn't work here since mod \(3\) we can have \(a = 1, b = 1\) and have a valid solution.

View
2016 Paper 1 Q7
D: 1500.0 B: 1500.0
proof number theory modular arithmetic sets divisibility prime factorization closure properties counterexample

The set \(S\) consists of all the positive integers that leave a remainder of 1 upon division by 4. The set \(T\) consists of all the positive integers that leave a remainder of 3 upon division by 4.

  1. Describe in words the sets \(S \cup T\) and \(S \cap T\).
  2. Prove that the product of any two integers in \(S\) is also in \(S\). Determine whether the product of any two integers in \(T\) is also in \(T\).
  3. Given an integer in \(T\) that is not a prime number, prove that at least one of its prime factors is in \(T\).
  4. For any set \(X\) of positive integers, an integer in \(X\) (other than 1) is said to be \(X\)-prime if it cannot be expressed as the product of two or more integers all in \(X\) (and all different from 1).
    • \(\bf (a)\) Show that every integer in \(T\) is either \(T\)-prime or is the product of an odd number of \(T\)-prime integers.
    • \(\bf (b)\) Find an example of an integer in \(S\) that can be expressed as the product of \(S\)-prime integers in two distinct ways. [Note: \(s_1s_2\) and \(s_2s_1\) are not counted as distinct ways of expressing the product of \(s_1\) and \(s_2\).]

Solution:

  1. \(S \cup T\) is the set of odd positive integers. \(S \cap T\) is the empty set.
  2. Suppose we have two integers in \(S\), say \(4n+1\) and \(4m+1\), so \((4n+1)(4m+1) = 16nm + 4(n+m) + 1 = 4(4nm + n+m) + 1\) which clearly is in \(S\). The product of any two integers in \(T\) is in \(S\), since \((4n+3)(4m+3) = 16nm + 12(n+m) + 9 = 4(4nm+3(n+m) + 2) + 1\)
  3. Suppose \(p \in T\) is not prime, then it must have prime factors. They must all be odd, so they are in \(T\) or \(S\). If they are all in \(S\) then \(p\) must also be in \(S\) (as the product of numbers in \(S\)) but this is a contraction. Therefore \(p\) must have a prime factor in \(T\).
    • \(3, 7, 11, 19\) are all primes in \(T\). Notice therefore that any product of two of them must be \(S\)-prime. But then \((3 \times 7) \times (11 \times 19)\) and \((3 \times 11) \times (7 \times 19)\) are distinct factorisations into \(S\)-prime factors.

View
2015 Paper 3 Q12
D: 1700.0 B: 1500.0
probability generating functions PGF dice divisibility modular arithmetic roots of unity geometric series

A 6-sided fair die has the numbers 1, 2, 3, 4, 5, 6 on its faces. The die is thrown \(n\) times, the outcome (the number on the top face) of each throw being independent of the outcome of any other throw. The random variable \(S_n\) is the sum of the outcomes.

  1. The random variable~\(R_n\) is the remainder when \(S_n\) is divided by 6. Write down the probability generating function, \(\G(x)\), of \(R_1\) and show that the probability generating function of \(R_2\) is also \(\G(x)\). Use a generating function to find the probability that \(S_n\) is divisible by 6.
  2. The random variable \(T_n\) is the remainder when \(S_n\) is divided by 5. Write down the probability generating function, \(\G_1(x)\), of \(T_1\) and show that \(\G_2(x)\), the probability generating function of \(T_2\), is given by \[ {\rm G}_2(x) = \tfrac 1 {36} (x^2 +7y) \] where \(y= 1+x+x^2+x^3+x^4\,\). Obtain the probability generating function of \(T_n\) and hence show that the probability that \(S_n\) is divisible by \(5\) is \[ \frac15\left(1- \frac1 {6^n}\right) \] if \(n\) is not divisible by 5. What is the corresponding probability if \(n\) is divisible by 5?

Solution:

  1. \(G(x) = \frac{1}{6} (1 + x + x^2 + x^3 + x^4 + x^5)\) The pgf for \(R_2\) is: \begin{align*} \frac1{36}x^2 + \frac{2}{36}x^3 + \frac{3}{36}x^4 + \frac{4}{36}x^5 + \frac{5}{36} +\\ \quad \quad + \frac{6}{36}x^1 + \frac{5}{36}x^2 + \frac4{36}x^3 + \frac3{36}x^4 + \frac{2}{36}x^5 + \frac{1}{36} \\ = \frac{1}{6}(1 + x + x^2 + x^3 + x^4 + x^5) = G(x) \end{align*} Since rolling the dice twice is the same as rolling the dice once, rolling the dice \(n\) times will be the same as rolling it once, ie the pgf for \(R_n\) will be \(G(x)\) and the probability \(S_n\) is divisible by \(6\) is \(\frac16\)
  2. \(G_1(x) = \frac{1}{6} + \frac{1}{3}x^1 + \frac{1}{6}x^2 + \frac16x^3+ \frac16x^4 = \frac16(1 + 2x+x^2+x^3+x^4)\). If \(G_n\) is the probability generating function for \(T_n\) then we can obtain \(G_n\) by multiplying \(G_{n-1}\) by \(G(x)\) and replacing any terms of order higher than \(5\) with their remainder on division by \(5\). (Or equivalently, working over \(\mathbb{R}[x]/(x^5-1)\). If \(y = 1 + x + x^2 + x^3 + x^4\) then: \begin{align*} xy &= x + x^2 + x^3 + x^4 +x^5 \\ &= x + x^2 + x^3 + x^4 + 1 \\ &= y \\ \\ y^2 &= (1 + x+x^2 + x^3+x^4)^2 \\ &= 1 + 2x + 3x^2 + 4x^3+5x^4+4x^5+3x^6 + 2x^7 + x^8 \\ &= (1+4) + (2+3)x+(3+2)x^2 + (4+1)x^3 + 5x^4 \\ &= 5y \end{align*} \begin{align*} \frac{1}{36}(y+x)(y+x) &= \frac1{36}(y^2 + 2xy + x^2) \\ &= \frac1{36}(5y + 2y + x^2 ) \\ &= \frac1{36}(7y + x^2) \end{align*} Similarly, \begin{align*} G_n(x) &= \l\frac{1}{6}(x+y) \r^n \\ &= \frac1{6^n} \l \sum_{i=0}^n \binom{n}{i} y^ix^{n-i} \r \\ &= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} y^i + x^n \r \\ &= \frac1{6^n} \l \sum_{i=1}^n \binom{n}{i} 5^{i-1}y + x^n \r \\ &= \frac1{6^n} \l \frac{1}{5}y((5+1)^n-1) + x^n \r \\ &= \frac1{6^n} \l \frac{1}{5}y(6^n-1) + x^n \r \\ \end{align*} Therefore if \(n \not \equiv 0 \pmod{5}\), we can find the probability of \(T_n = 0\) by looking at the constant coefficient, ie plugging in \(x = 0\), which is: \[\frac1{6^n} \l \frac{1}{5}(6^n-1) \r = \frac{1}{5} \l 1- \frac{1}{6^n} \r \] When \(n \equiv 0 \pmod{5}\) we can also find the constant coefficient by plugging in \(x = 0\), which is: \[\frac1{6^n} \l \frac{1}{5}(6^n-1) + 1 \r = \frac{1}{5} \l 1+ \frac{4}{6^n} \r \]
Note: this whole question can be considered a "roots-of-unity" filter in disguise. Our computations in \(\mathbb{R}[x]/(x^5 - 1)\) are the same as computations using \(\omega\), in fact \(\mathbb{R}[x]/(x^5 - 1) \cong \mathbb{R}[\omega]\) where \(\omega\) is a primitive \(5\)th root of unity

View
2010 Paper 1 Q8
D: 1500.0 B: 1484.0
proof by contradiction divisibility infinite descent number theory modular arithmetic integer solutions proof

  1. Suppose that \(a\), \(b\) and \(c\) are integers that satisfy the equation \[ a^{3}+3b^{3}=9c^{3}. \] Explain why \(a\) must be divisible by 3, and show further that both \(b\) and \(c\) must also be divisible by 3. Hence show that the only integer solution is \(a=b=c=0\,\).
  2. Suppose that \(p\), \(q\) and \(r\) are integers that satisfy the equation \[ p^4 +2q^4 = 5r^4 \,.\] By considering the possible final digit of each term, or otherwise, show that \(p\) and \(q\) are divisible by 5. Hence show that the only integer solution is \(p=q=r=0\,\).

Solution:

  1. Since \(a^3 = 9c^3 - 3b^3 = 3(3c^3-b^3)\) we must have \(3 \mid a^3\). But since \(3\) is prime, \(3 \mid a\). Since \(3 \mid a\) we can write \(a = 3a'\) for some \(a' \in \mathbb{Z}\). Therefore our equation is \(27(a')^3 + 3b^3 = 9c^3 \Rightarrow 9(a')^3 + b^3 = 3c^3\) which means that \(3 \mid b\) by the same argument from earlier. So \(b = 3b'\) so the equation is \(9(a')^3 + 27(b')^3 = 3c^3 \Rightarrow 3(a')^3 + 9(b')^3 = c^3\) which means that \(3 \mid c\). Suppose \((a,b,c)\) is the smallest measured by \(a^2+b^2+c^2\) with \(a, b, c\neq 0\). Then \((\frac{a}{3}, \frac{b}{3}, \frac{c}{3})\) is also a solution. But this contradicts that we had found the smallest solution. Therefore the only possible solution is \((0,0,0)\) which clearly works.
  2. Consider \(p, q \pmod{5}\). By \(FLT\) \(p^4, q^4 = 0, 1 \pmod{5}\) so \(p^4+2q^4 \in \{0, 1, 2, 3\}\) and in particular the only way they are divisible by \(5\) is if \(p \equiv q \equiv 0 \pmod{5}\). Therefore \(p = 5p', q = 5q'\) and so \(5^4(p')^4 + 5^4(q')^4 = 5r^4 \Rightarrow r^4 = 5(25(p')^4 + 25(q')^4) \Rightarrow 5\mid r^4 \Rightarrow 5 \mid r\). Therefore we can use the same argument about the smallest solution to show that \(p = q= r = 0\)

View
2004 Paper 1 Q5
D: 1484.0 B: 1500.0
proof arithmetic progressions modular arithmetic divisibility proof by contradiction number theory Diophantine equation residues

The positive integers can be split into five distinct arithmetic progressions, as shown: \begin{align*} A&: \ \ 1, \ 6, \ 11, \ 16, \ ... \\ B&: \ \ 2, \ 7, \ 12, \ 17, \ ...\\ C&: \ \ 3, \ 8, \ 13, \ 18, \ ... \\ D&: \ \ 4, \ 9, \ 14, \ 19, \ ... \\ E&: \ \ 5, 10, \ 15, \ 20, \ ... \end{align*} Write down an expression for the value of the general term in each of the five progressions. Hence prove that the sum of any term in \(B\) and any term in \(C\) is a term in \(E\). Prove also that the square of every term in \(B\) is a term in \(D\). State and prove a similar claim about the square of every term in \(C\).

  1. Prove that there are no positive integers \(x\) and \(y\) such that \[ x^2+5y=243\,723 \,. \]
  2. Prove also that there are no positive integers \(x\) and \(y\) such that \[ x^4+2y^4=26\,081\,974 \,. \]

View
1997 Paper 1 Q3
D: 1484.0 B: 1501.4
sequences recurrence relation exponentials and logarithms powers of 3 modular arithmetic estimation decimal approximation

Let \(a_{1}=3\), \(a_{n+1}=a_{n}^{3}\) for \(n\geqslant 1\). (Thus \(a_{2}=3^{3}\), \(a_{3}=(3^{3})^{3}\) and so on.)

  1. What digit appears in the unit place of \(a_{7}\)?
  2. Show that \(a_{7}\geqslant 10^{100}\).
  3. What is \(\dfrac{a_{7}+1}{2a_{7}}\) correct to two places of decimals? Justify your answer.

Solution:

  1. Notice that \(a_n = 3^{3^{n-1}}\) in particular, \(a_7 = 3^{3^6}\). Using Fermat's little theorem, we can see that \(3^4 \equiv 1 \pmod{5}\) and so we need to figure out \(3^6 \pmod{4}\), which is clearly \(1\). Therefore \(3^{3^6} \equiv 3^{4k+1} \equiv 3 \pmod{5}\). Therefore the units digit is \(3\).
  2. Notice that \(3^5 > 100\) and \(3^3 > 10\). Therefore \begin{align*} a_7 &= 3^{3^6} \\ &= (3^3)^{3^5} \\ &> 10^{3^5} \\ &> 10^{100} \end{align*}
  3. \begin{align*} \frac{a_7+1}{2a_7} &= \frac12 + \frac1{2a_7} \\ &= 0.5 + 0.\underbrace{000\cdots}_{\text{at least }99\text{ zeros}} \\ &= 0.50 \end{align*} Since \(a_7 > 10^{100}, \, \frac{1}{2a_7} < 10^{-100}\)

View
1996 Paper 1 Q3
D: 1500.0 B: 1486.0
proof divisibility factorisation proof by induction modular arithmetic number theory

Let \(n\) be a positive integer.

  1. Factorise \(n^{5}-n^{3},\) and show that it is divisible by 24.
  2. Prove that \(2^{2n}-1\) is divisible by 3.
  3. If \(n-1\) is divisible by 3, show that \(n^{3}-1\) is divisible by 9.

Solution:

  1. \(n^5 -n^3 = n^3(n-1)(n+1)\). If \(n\) is even then \(8 \mid n^3\). if \(n\) is odd then both of \(n-1\) and \(n+1\) are divisible by \(2\) and one is divisible by \(4\), so regardless \(8\) divides our expression. We can write \(n = 3k, 3k+1, 3k+2\) and in all cases our expression is divisible by \(3\). \(n = 3k \Rightarrow 3 \mid n\), \(n = 3k+1 \Rightarrow 3 \mid n-1\), \(n = 3k+2 \Rightarrow 3 \mid n+1\). Therefore \(3\) and \(8\) both divide our expression, and they are coprime so their product (24) divides our expression.
  2. \(2^{2n}-1 = (2^2-1) \cdot (1+2^2+\cdots + 2^{2n-2}) = 3 \cdot N\) therefore \(3\) divides our number.
  3. Suppose \(n-1 = 3k\) then \(n^3-1 = (3k+1)^3-1 = 27k^3 + 27k^2 + 9k\) which is clearly divisible by 9

View
1995 Paper 3 Q7
D: 1654.7 B: 1516.0
groups group axioms closure identity element inverse isomorphism complex numbers modular arithmetic matrix rotation matrix unit modulus

Consider the following sets with the usual definition of multiplication appropriate to each. In each case you may assume that the multiplication is associative. In each case state, giving adequate reasons, whether or not the set is a group.

  1. the complex numbers of unit modulus;
  2. the integers modulo 4;
  3. the matrices \[ \mathrm{M}(\theta)=\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta \end{pmatrix}, \] where \(0\leqslant\theta<2\pi\);
  4. the integers \(1,3,5,7\) modulo 8;
  5. the \(2\times2\) matrices all of whose entries are integers;
  6. the integers \(1,2,3,4\) modulo 5.
In the case of each pair of groups above state, with reasons, whether or not they are isomorphic.

Solution:

  1. \(\{ z \in \mathbb{C} : |z| = 1\}\) is a group.
    1. (Closure) \(|z_1z_2| = |z_1||z_2| = 1\). Set is closed under multiplication
    2. (Associativity) Multiplication of complex numbers is associative
    3. (Identity) \(|1| = 1\)
    4. (Inverses) \(| \frac{1}{z} | = \frac{1}{|z|} = \frac{1}{1} = 1\), the set contains inverses
  2. the integers \(\pmod{4}\) are not a group under multiplication, \(2\) has no inverse, since \(0 \times k \equiv 0 \pmod{4}\)
  3. The set of rotation matrices is a group:
    1. (Closure) \begin{align*} \begin{pmatrix}\cos\theta_1 & -\sin\theta_1\\ \sin\theta_1 & \cos\theta_1 \end{pmatrix} \begin{pmatrix}\cos\theta_2 & -\sin\theta_2\\ \sin\theta_2 & \cos\theta_2 \end{pmatrix} &= {\scriptscriptstyle\begin{pmatrix}\cos\theta_1 \cos \theta_2 - \sin \theta_1\sin \theta_2 & -\sin\theta_1\ \cos \theta_1 - \sin \theta_2\cos\theta_1\\ \sin\theta_1\ \cos \theta_1 + \sin \theta_2\cos\theta_1 & \cos\theta_1 \cos \theta_2 - \sin \theta_1\sin \theta_2 \end{pmatrix}} \\ &= \begin{pmatrix}\cos(\theta_1+\theta_2) & -\sin(\theta_1+\theta_2)\\ \sin(\theta_1+\theta_2) & \cos(\theta_1+\theta_2) \end{pmatrix} \end{align*} Since \(\cos, \sin\) are periodic with period \(2\pi\), we can find \(\theta_3 = \theta_1 + \theta_2 + 2k\pi\) such that \(0 \leq \theta_3 < 2 \pi\), so our set is closed
    2. (Associativity) Matrix multiplication is associative
    3. (Identity) Consider \(\theta = 0\)
    4. (Inverses) Consider \(2\pi - \theta\)
  4. \(\{1, 3, 5, 7\} \pmod{8}\) is a group:
    1357
    11357
    33175
    55713
    77531
    1. (Closure) See Cayley table
    2. (Associativity) Integer multiplication is associative
    3. (Identity) \(1\)
    4. (Inverses) \(x \mapsto x\) (See Cayley table)
  5. \(2\times2\) matrices are not a group, consider $0 = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}\(, then \)\mathbf{0}\mathbf{M} = \mathbf{0}$ for all other matrices.
  6. 1234
    11234
    22413
    33142
    44321
    1. (Closure) See Cayley table
    2. (Associativity) Integer multiplication is associative
    3. (Identity) \(1\)
    4. (Inverses) \(1 \mapsto 1, 2 \mapsto 3, 3 \mapsto 2, 4 \mapsto 4\) (See Cayley table)
(i)(iii)(iv)(vi)
(i)\(\checkmark\)\(\checkmark\) consider \(z \mapsto \begin{pmatrix} \cos \arg (z)- \sin \arg(z)
\sin \arg(z)\cos \arg(z) \end{pmatrix}\)not finitenot finite
(iii)\(\checkmark\)not finitenot finite
(iv)\(\checkmark\)no element order \(4\)
(vi)\(\checkmark\)

View
1994 Paper 2 Q1
D: 1600.0 B: 1484.0
proof number theory divisibility decimal representation modular arithmetic existence proof digit properties

In this question we consider only positive, non-zero integers written out in the usual (decimal) way. We say, for example, that 207 ends in 7 and that 5310 ends in 1 followed by 0. Show that, if \(n\) does not end in 5 or an even number, then there exists \(m\) such that \(n\times m\) ends in 1. Show that, given any \(n\), we can find \(m\) such that \(n\times m\) ends either in 1 or in 1 followed by one or more zeros. Show that, given any \(n\) which ends in 1 or in 1 followed by one or more zeros, we can find \(m\) such that \(n\times m\) contains all the digits \(0,1,2,\ldots,9\).

Solution: \begin{array}{c|c} \text{ends in} & \text{multiply by} \\ \hline 1 & 1 \\ 3 & 7 \\ 7 & 3 \\ 9 & 9 \end{array} If if \(n = 2^a \cdot 5^b \cdot c\) where \(c\) has no factors of \(2\) and \(5\) then we can multiply by \(2^b \cdot 5^a\) to obtain \(c\) followed by \(0\)s. Since \(c\) is neither even, nor a multiple of \(5\), by the earlier part of the question we can find a multiple such that it ends in \(1\). Suppose it is a \(k\) digit number, the consider Now consider \(1\underbrace{00\cdots0}_{k\text{ digits}}2\underbrace{00\cdots0}_{k\text{ digits}}\cdots 8\underbrace{00\cdots0}_{k\text{ digits}}9\cdot 0\), then clearly each section will end in the leading digit (ie all digits from \(1\) to \(9\)) and also end with a \(0\)

View
1994 Paper 3 Q7
D: 1679.5 B: 1503.1
groups permutations symmetric group S3 cyclic group isomorphism roots of unity element order modular arithmetic subgroup complex numbers

Let \(S_{3}\) be the group of permutations of three objects and \(Z_{6}\) be the group of integers under addition modulo 6. List all the elements of each group, stating the order of each element. State, with reasons, whether \(S_{3}\) is isomorphic with \(Z_{6}.\) Let \(C_{6}\) be the group of 6th roots of unity. That is, \(C_{6}=\{1,\alpha,\alpha^{2},\alpha^{3},\alpha^{4},\alpha^{5}\}\) where \(\alpha=\mathrm{e}^{\mathrm{i}\pi/3}\) and the group operation is complex multiplication. Prove that \(C_{6}\) is isomorphic with \(Z_{6}.\) Is there any (multiplicative or additive) subgroup of the complex numbers which is isomorphic with \(S_{3}\)? Give a reason for your answer.

Solution: \(S_3 \) $\begin{array}{c | c |c |c |c |c |c |} \text{elements} & e & (12) & (13) & (23) & (123) & (132) \\ \text{order} & 1 & 2 & 2 & 2 & 3 & 3 \\ \end{array}$ \(\mathbb{Z}_6\) $\begin{array}{c | c |c |c |c |c |c |} \text{elements} & 0 & 1 & 2 & 3 & 4 & 5 \\ \text{order} & 1 & 6 & 3 & 2 & 3 & 6 \\ \end{array}$ \(S_3\) is not isomorphic to \(\mathbb{Z}_6\) since \(\mathbb{Z}_6\) has two elements of order \(6\) but \(S_3\) has none. Consider the map \(f : \mathbb{Z}_6 \to C_6\) with \(i \mapsto \alpha^i\). This is an isomorphism, since \(i + j \mapsto \alpha^{i+j} = \alpha^i\alpha^j\) \(S_3\) is non-abelian, since \((12)(123) = (23) \neq (13) = (123)(12)\) but multiplication and addition of complex numbers is commutative.

View
1993 Paper 2 Q7
D: 1600.0 B: 1491.2
number theory modular arithmetic divisibility proof by contradiction infinite descent Diophantine equation mod 5

The integers \(a,b\) and \(c\) satisfy \[ 2a^{2}+b^{2}=5c^{2}. \] By considering the possible values of \(a\pmod5\) and \(b\pmod5\), show that \(a\) and \(b\) must both be divisible by \(5\). By considering how many times \(a,b\) and \(c\) can be divided by \(5\), show that the only solution is \(a=b=c=0.\)

Solution: \begin{array}{c|ccccc} a & 0 & 1 & 2 & 3 & 4 \\ a^2 & 0 & 1 & 4 & 4 & 1 \end{array} Therefore \(a^2 \in \{0,1,4\}\) and so we can have \begin{array} $2a^2+b^2 & 0 & 1 & 4 \\ \hline 0 & 0 & 1 & 4 \\ 1 & 2 & 3 & 1 \\ 4 & 3 & 4 & 2 \end{array} Therefore the only solution must have \(5 \mid a,b\), but then we can write them has \(5a'\) and \(5b'\) so the equation becomes \(2\cdot25 a'^2 + 25b'^2 = 5c^2\) ie \(5 \mid c^2 \Rightarrow 5 \mid c\). But that means we can always divide \((a,b,c)\) by \(5\), which is clearly a contradiction if we consider the lowest power of \(5\) dividing \(a,b,c\) for any solution.

View
1992 Paper 1 Q1
D: 1484.0 B: 1500.0
proof modular arithmetic calendar calculation divisibility leap year systematic reasoning

Today's date is June 26th 1992 and the day of the week is Friday. Find which day of the week was April 3rd 1905, explaining your method carefully. {[}30 days hath September, April, June and November. All the rest have 31, excepting February alone which has 28 days clear and 29 in each leap year.{]}

Solution: There are \(87\) years between 1905 and 1992. Of those years, every 4th is a leap years, starting with 1908, and ending with 1992, so there are 22 leap years. There are 30 days between Apr 3 and May 3, 31 days between May 3 and Jun 3 and a further 23 days to the 26th. Therefore \(87 \times 365 + 22 \cdot 1 + 61 + 23\) total days. \(\pmod{7}\) this is \(3 \times 1 + 1 + 5 + 2 = 3\), therefore it is \(4\) week days before Friday, ie Monday.

View
1991 Paper 2 Q9
D: 1616.2 B: 1500.0
groups matrix modular arithmetic group axioms order of group commutativity subgroup test element order upper triangular matrix

Let \(G\) be the set of all matrices of the form \[ \begin{pmatrix}a & b\\ 0 & c \end{pmatrix}, \] where \(a,b\) and \(c\) are integers modulo 5, and \(a\neq0\neq c\). Show that \(G\) forms a group under matrix multiplication (which may be assumed to be associative). What is the order of \(G\)? Determine whether or not \(G\) is commutative. Determine whether or not the set consisting of all elements in \(G\) of order \(1\) or \(2\) is a subgroup of \(G\).

Solution: Claim \(G\) is a group under matrix multiplication

  • (Closure) Suppose \(\mathbf{A}\) and \(\mathbf{B}\) are matrices of that form, then \(\begin{pmatrix} a_1 & b_1 \\ 0 & c_1 \end{pmatrix} \begin{pmatrix} a_2 & b_2 \\ 0 & c_2 \end{pmatrix} = \begin{pmatrix} a_1a_2 & a_1b_2 + b_1c_2 \\ 0 & c_1c_2 \end{pmatrix}\), this is clearly of the required form since if \(a_1, a_2, c_1, c_2 \neq 0\) then \(a_1a_2, c_1c_2 \neq 0\)
  • (Associative) By inheritance from matrix multiplication
  • (Identity) Consider \(\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) also clearly of the required form.
  • (Inverse) Consider \((ac)^{-1}\begin{pmatrix} c & -b \\ 0 & a \end{pmatrix}\), since \(ac \neq 0\) we can assume it has an inverse mod \(5\). therefore we have another matrix of the required form.
There are \(4\) possible values for \(a\) and \(c\) and \(5\) possible values for \(b\), so \(4 \times 4 \times 5 = 80\) elements, so the group is order \(80\). \(G\) is not commutative, consider \(\begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix} \begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 2 \end{pmatrix}\) \(\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 2 \end{pmatrix} = \begin{pmatrix} 1 & 3 \\ 0 & 2 \end{pmatrix}\) The elements of order \(1\) or \(2\) satisfy \(\begin{pmatrix} a & b \\ 0 & c \end{pmatrix} = \begin{pmatrix} a^{-1} & -ba^{-1}c^{-1} \\ 0 & c^{-1} \end{pmatrix}\) Therefore \(a^2 = 1, c^2 = 1 \Rightarrow a, c = 1, 4\) and \(b = -ba^{-1}c^{-1} \Rightarrow b = 0\) or , \(ac = -1\), so we have \((a,b,c) = (1,0,1), (4,0,4), (1, *, 4), (4, *, 1)\) So there are \(12\) elements of order \(1\) or \(2\). But this can't be a subgroup since \(12 \not \mid 80\)

View