27 problems found
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\).
Let \(k\) be an integer satisfying \(0\le k \le 9\,\). Show that \(0\le 10k-k^2\le 25\) and that \(k(k-1)(k+1)\) is divisible by \(3\,\). For each \(3\)-digit number \(N\), where \(N\ge100\), let \(S\) be the sum of the hundreds digit, the square of the tens digit and the cube of the units digit. Find the numbers \(N\) such that \(S=N\). [Hint: write \(N=100a+10b+c\,\) where \(a\,\), \(b\,\) and \(c\) are the digits of \(N\,\).]
Solution: First note that \(10k - k^2 = 25 - (5-k)^2\) which is clearly bounded above by \(25\). The smallest it can be is when \(|5-k|\) is as large as possible, ie when \(k =0\) and we get a lower bound of \(0\). For \((k-1)k(k+1)\) notice this is the product of \(3\) consecutive integers, and therefore must be divisible by \(3\). (In fact, it's divisible by six, since \(\binom{k+1}{3}\) is the number of ways to choose \(3\) objects from \(k+1\). Let \(N = 100a + 10b + c\) where \(0 \leq a,b,c < 10\) and \(1 \leq a\). \(S = a + b^2 + c^3\) we want to find \begin{align*} && 100a +10b + c &= a + b^2 + c^3 \\ \Rightarrow && 0 &= \underbrace{99a}_{3 \mid 99 } + 10b - b^2 -\underbrace{c(c+1)(c-1)}_{3 \mid c(c+1)(c-1)} \\ \end{align*} Therefore \(3 \mid 10b - b^2 = b(10-b)\). Therefore \(3 \mid b\) or \(3 \mid 10-b\) so \(b = 0, 3, 6, 1, 4, 7\) We also have \(99a \geq 99\) and \(10b-b^2 \in [0, 25]\) so we need \(c^3-c \geq 99\), so \(c \geq 5\) Case \(c = 5\), Then \(c^3-c = 120\) so \(a = 1\) and \(10b-b^2 = 21\) so \(b= 3, 7\) \(N = 135, 175\) Case \(c = 6\), so \(c^3 - c = 210\) so \(a = 2\) and \(25-(5-k)^2 = 12\) so no solutions. Case \(c = 7\), so \(7^3 - 7 = 336\) so \(a = 3\) and \(25-(5-k)^2 = 39\) so no solutions. Case \(c = 8\) so \(8^3-8 = 504\) so \(a = 5\) and \(25-(5-k)^2 = 9\), so \(b = 1, 9\) and \(N = 518, 598\) Case \(c = 9\) so \(9^3 - 9 = 720\), so \(a = 7\) and \(25-(5-k)^2 = 27\) so no solutions. Therefore all the solutions are \(N = 135, 175, 518, 598\)
The \(n\)th Fermat number, \(F_n\), is defined by \[ F_n = 2^{2^n} +1\, , \ \ \ \ \ \ \ n=0, \ 1, \ 2, \ \ldots \ , \] where \(\ds 2^{2^n}\) means \(2\) raised to the power \(2^n\,\). Calculate \(F_0\), \(F_1\), \(F_2\) and \(F_3\,\). Show that, for \(k=1\), \(k=2\) and \(k=3\,\), $$ F_0F_1 \ldots F_{k-1} = F_k-2 \;. \tag{*} $$ Prove, by induction, or otherwise, that \((*)\) holds for all \(k\ge1\). Deduce that no two Fermat numbers have a common factor greater than \(1\). Hence show that there are infinitely many prime numbers.
Solution: \begin{align*} && F_0 &= 2^{2^0}+1 \\ &&&= 2^1+1 = 3\\ && F_1 &= 2^{2^1}+1 \\ &&&= 2^2+1 = 5 \\ && F_2 &= 2^{2^2}+1 \\ &&&= 2^4+1 \\ &&&= 17 \\ &&F_3 &= 2^{2^3}+1 \\ &&&= 2^8+1 \\ &&&= 257 \\ \\ && \text{empty product} &= 1\\ && F_1 - 2 &= 3-2 = 1\\ \Rightarrow&& 1 &= F_1-2\\ && F_0 &=3 \\ && F_2-2 &= 3 \\ \Rightarrow && F_0 &= F_2 - 2\\ && F_0F_1 &= 3 \cdot 5 = 15 \\ && F_3-2 &= 17-2 = 15 \\ \Rightarrow && F_0F_1 &= F_3-2 \end{align*} \begin{align*} && F_0 F_1 \cdots F_{k-1} &= \prod_{i=0}^{k-1} \left ( 2^{2^{i}}+1\right) \\ &&&= \sum_{l = \text{sum of }2^i} 2^l \\ &&&= \sum_{l=0}^{2^{k}-1}2^l \\ &&&= 2^{2^k}-1 \\ &&&= F_k-2 \end{align*} Suppose \(p \mid F_a, F_b\) with \(b > a\), then \(p \mid 2=F_b - F_0\cdots F_a \cdots F_{b-1}\) therefore \(p = 1, 2\), but \(2 \nmid F_a\) for any \(a\). Therefore any number dividing two Fermat numbers is \(1\), ie they are all coprime. Consider the smallest prime dividing \(F_n\) for each \(n\). Clearly these are all different since each \(F_n\) is coprime from all the others. Clearly there are infinitely many of time (since there are infinitely many \(F_n\)). Therefore there are infinitely many primes.
How many integers greater than or equal to zero and less than a million are not divisible by 2 or 5? What is the average value of these integers? How many integers greater than or equal to zero and less than 4179 are not divisible by 3 or 7? What is the average value of these integers?
Solution: There are \(1\,000\,000\) numbers between 1 and a million (inclusive). \(500\,000\) are divisible by \(2\), \(200\,000\) are divisible by \(5\) and \(100\,000\) are divisible by both. Therefore there are: \(1\,000\,000 - 500\,000-200\,000+100\,000 = 400\,000\). (Alternatively, the only numbers are those which are \(1,3,7,9 \pmod{10}\) so there are \(4\) every \(10\), or \(4 \cdot 100\,000\)). We can sum all these values similarly, \begin{align*} S &= \underbrace{\sum_{i=1}^{10^6} i}_{\text{all numbers}}-\underbrace{\sum_{i=1}^{5 \cdot 10^5} 2i}_{\text{all multiples of } 2}-\underbrace{\sum_{i=1}^{2 \cdot 10^5} 5i}_{\text{all multiples of } 5}+\underbrace{\sum_{i=1}^{10^5} 10i}_{\text{all multiples of } 5} \\ &= \frac{10^6 \cdot (10^6 + 1)}{2} - \frac{10^6 \cdot (5\cdot 10^5+1)}{2} - \frac{10^6 \cdot (2\cdot 10^5+1)}{2} + \frac{10^6 \cdot (10^5+1)}{2} \\ &= \frac{10^6 (10^5 \cdot (10-5-2+1))))}{2} \\ &= \frac{10^6 \cdot 10^5 \cdot 4}{2} \\ &= 2\cdot 10^{11} \end{align*} So the average value is \(\frac{2 \cdot 10^{11}}{4 \cdot 10^5} = \frac{10^6}{2} = 500\,000\). (Alternatively, each value can be paired off eg \(999\,999\) with \(1\) and so on, leaving averages of \(500\,000\)). Note that \(4197\) is divisible by \(3\) and \(7\). Using the same long we have: \(4179 - \frac{4179}{3} - \frac{4179}{7} + \frac{4179}{21} = 4179 - 1393 - 597 + 199 = 2388\). The sum will be: \begin{align*} S &= \underbrace{\sum_{i=1}^{4179}i }_{\text{all numbers}}- \underbrace{\sum_{i=1}^{1393}3i }_{\text{multiples of }3}- \underbrace{\sum_{i=1}^{597}7i }_{\text{multiples of }7}+ \underbrace{\sum_{i=1}^{199}21i }_{\text{mulitples of }21} \\ &= \frac{4179 \cdot 4180}{2} - \frac{4179 \cdot 1394}{2} - \frac{4179 \cdot 598}{2} +\frac{4179 \cdot 200}{2} \\ &= \frac{4179 \cdot 2388}{2} \end{align*} So the average value is \(\frac{4179}{2}\).
Suppose that a solution \((X,Y,Z)\) of the equation \[X+Y+Z=20,\] with \(X\), \(Y\) and \(Z\) non-negative integers, is chosen at random (each such solution being equally likely). Are \(X\) and \(Y\) independent? Justify your answer. Show that the probability that \(X\) is divisible by \(5\) is \(5/21\). What is the probability that \(XYZ\) is divisible by 5?
Solution: They are not independent: \begin{align*} && \mathbb{P}(X = 20 \,\, \cap Y = 20) = 0 \\ && \mathbb{P}(X = 20 )\mathbb{P}(Y = 20) \neq 0 \\ \end{align*} \begin{align*} X = 0: && 21 \text{ solutions} \\ X = 5: && 16 \text{ solutions} \\ X = 10: && 11 \text{ solutions} \\ X = 15: && 6 \text{ solutions} \\ X = 20: && 1 \text{ solutions} \\ 5 \mid X: && 55 \text{ solutions} \\ \\ && \binom{20+2}{2} = 11 \cdot 21 \text{ total solutions} \\ \Rightarrow && \mathbb{P}(5 \mid X) = \frac{55}{11 \cdot 21} = \frac{5}{21} \end{align*} \begin{align*} \mathbb{P}(5 \mid XYZ) &= 3\cdot \mathbb{P}(5 \mid X) - 2\mathbb{P}(5 \mid X, Y, Z) \\ &= \frac{3 \cdot 55 - 2 \cdot \binom{4+2}{2}}{11 \cdot 21} = \frac{35}{77} \end{align*}
Show that, if \(n\) is an integer such that $$(n-3)^3+n^3=(n+3)^3,\quad \quad {(*)}$$ then \(n\) is even and \(n^2\) is a factor of \(54\). Deduce that there is no integer \(n\) which satisfies the equation \((*)\). Show that, if \(n\) is an integer such that $$(n-6)^3+n^3=(n+6)^3, \quad \quad{(**)}$$ then \(n\) is even. Deduce that there is no integer \(n\) which satisfies the equation \((**)\).
Solution: \begin{align*} && n^3 &= (n+3)^3 - (n-3)^3 \\ &&&= n^3 + 9n^2+27n + 27 - (n^3 - 9n^2+27n-27) \\ &&&= 18n^2+54 \end{align*} Therefore since \(2 \mid 2(9n^2 + 27)\), \(2 \mid n^3 \Rightarrow 2 \mid n\), so \(n\) is even. Since \(n^2 \mid n^3\), \(n^2 \mid 54 = 2 \cdot 3^3\), therefore \(n = 1\) or \(n = 3\). \((1-3)^3 + 1^3 < 0 < (1+3)^3\). So \(n = 1\) doesn't work. \((3 - 3)^3 + 3^3 < (3+3)^3\) so \(n = 3\) doesn't work. Therefore there are no solutions. \begin{align*} && n^3 &= (n+6)^3 - (n-6)^3 \\ &&&= n^3 + 18n^2 + 180n + 6^3 - (n^3 - 18n^2 + 180n - 6^3 ) \\ &&&= 36n^2+2 \cdot 6^3 \end{align*} Therefore \(n^2 \mid 2 \cdot 6^3 = 2^4 \cdot 3^3\), therefore \(n = 1, 2, 3, 4, 6, 12\). \(n = 1\), \(1^3 <36+2\cdot 6^3\) \(n = 2\), \(2^3 <36 \cdot 4 + 2 \cdot 6^3\) \(n = 3\), \(3^3 <36 \cdot 9 + 2 \cdot 6^3\) \(n = 4\), \(4^3 < 36 \cdot 16 + 2 \cdot 6^3\) \(n = 6\), \(6^3 < 36\cdot 6^2+ 2 \cdot 6^3\) \(n = 12\), \(12^3 < 36 \cdot 12^2 + 2 \cdot 6^3\) Therefore there are no solutions \(n\) to the equation. These are both special cases of Fermat's Last Theorem, when \(n = 3\)
Let \(n\) be a positive integer.
Solution:
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\)
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.
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.
Let \(G\) be a finite group with identity \(e.\) For each element \(g\in G,\) the order of \(g\), \(o(g),\) is defined to be the smallest positive integer \(n\) for which \(g^{n}=e.\)
Solution: \begin{questionparts} \item Show that, if \(o(g)=n\) and \(g^{N}=e,\) then \(n\) divides \(N.\) Using the division algorithm, write \(N = qn + r\) where \(0 \leq r < n\) to divide \(N\) by \(n\). Then we have \(e = g^N = g^{qn + r} = g^{qn}g^r = (g^{n})^qg^r = e^qg^r = g^r\) therefore \(r\) is a number smaller than \(n\) such that \(g^r = e\). Therefore either \(r = 0\) or \(o(g) = r\), but by definition \(o(g) = n\) therefore \(r = 0\) and \(n \mid N\). \item Let \(g\) and \(h\) be elements of \(G\). Prove that, for any integer \(m,\) \[ gh^{m}g^{-1}=(ghg^{-1})^{m}. \] \((ghg^{-1})^m = \underbrace{(ghg^{-1})(ghg^{-1})\cdots(ghg^{-1})}_{m \text{ times}} = gh(g^{-1}g)h(g^{-1}g)\cdots (g^{-1}g)hg^{-1} = gh^mg^{-1}\) \item Let \(g\) and \(h\) be elements of \(G\), such that \(g^{5}=e,h\neq e\) and \(ghg^{-1}=h^{2}.\) Prove that \(g^{2}hg^{-2}=h^{4}\) and find \(o(h).\) \(g^2hg^{-2} = g(ghg^{-1})g^{-1} = gh^2g^{-1} = (ghg^{-1})^2 = (h^2)^2 = h^4\). \(h = g^{5}hg^{-5} = g^4ghg^{-1}g^{-4} = g^4h^2g^{-4} = g^3(ghg^{-1})^2g^{-3} = g^3h^4g^{-3} = h^32\) Therefore \(e = h^{31}\). Therfore \(o(h) \mid 31 \Rightarrow \boxed{o(h) = 31}\) since \(31\) is prime and \(o(h) \neq 1\)
Find the set of positive integers \(n\) for which \(n\) does not divide \((n-1)!.\) Justify your answer. [Note that small values of \(n\) may require special consideration.]
Solution: Claim: \(n \not \mid (n-1)!\) if and only if \(n\) is prime or \(4\) Proof: \((\Leftarrow)\)