Problems

---

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.

---

Solution:

1. \(p(x) = C(x-1)(x-2)(x-3)(x-4)+1\)
2. Suppose \(P(N+1) = 1\) them we could consider \(f(x) = P(x) - 1\) to be a polynomial of degree \(N\) with at least \(N+1\) roots, which would be a contradiction. Therefore \(P(N+1) \neq 1\). Since \(P(x) = C(x-1)(x-2)\cdots(x-N) + 1\) and \(P(N+1) = 2\) we must have \(C \cdot N! + 1 = 2 \Rightarrow C = \frac{1}{N!}\), hence \(P(x) = \binom{x-1}{N} + 1\) ie \(P(N+r) = \binom{N+r-1}{N}+1\) so \(P(N+2) = \binom{N+1}{N} +1= N+2\), so we can take \(r=2\).
3. 1. Suppose consider \(p(x) = S(x) - 2001\), then \(p(x)\) has roots \(a,b,c,d\) and suppose we can find \(e\) such that \(p(e) = 17\) then we must have \((e-a)(e-b)(e-c)(e-d) = 17\) but the only possible factors of \(17\) are \(-17,-1,1,17\) and we cannot have all \(4\) of them. Hence this is not possible.
   2. Now we have \(abcd = 16\), so we can have factors \(-16,-8,-4, -2, -1, 1, 2, 4,8,16\) (and we need to have \(4\) of them). If we have \(0\) negatives, the smallest product is \(1 \cdot 2 \cdot 4 \cdot 8 > 16\) If we have \(2\) negatives we must have \(1\) and \(-1\) (otherwise we have the same problem of being too large. So \(\{-1,1,-2,8\},\{-1,1,2,-8\},\{-1,1,-4,4\},\) If we have \(4\) negatives that's the same issue as with \(0\) negatives.

---

Solution:

1. Let \(n! + 5 = p\). If \(n \geq 5\) then \(5\) divides the LHS and so must also divide the RHS. Since \(n!+5 > 5\) this means the RHS cannot be prime. Therefore consider \(n = 1, 2, 3, 4\). \begin{align*} n = 1: && 1! + 5 = 6 &&\text{ nope} \\ n=2: && 2! + 5 = 7 && \checkmark \\ n=3: && 3! + 5 = 11 && \checkmark \\ n=4: && 4! + 5 = 29 && \checkmark \end{align*} Therefore the solutions are \((2,7), (3,11), (4,29)\).
2. Suppose \(1! \times 3! \times \cdots \times (2n-1)! = m!\). If \(n \geq 7\) then \(m! > (4n)!\) (by the first theorem) in particular \(m > 4n\). Therefore (by the second theorem) the RHS is divisible by some prime which cannot divide the LHS. Therefore consider \(n = 1,2,3,4,5,6\) \begin{align*} n = 1: && 1! = 1 = 1! && \checkmark \\ n = 2: && 1! \times 3! = 6 = 3! && \checkmark \\ n = 3: && 1! \times 3! \times 5! = 6! && \checkmark \\ n = 4: && 1! \times 3! \times 5! \times 7! = 6! \times 7! = 10! && \checkmark \\ n = 5: && 1! \times 3! \times 5! \times 7! \times 9! = 10! 9! > 11! && \text{would need a factor of } 11\text{ so no} \\ n = 6: && 1! \times 3! \times 5! \times 7! \times 9! \times 11! = 10! 11! 9! > 13! && \text{would need a factor of } 13\text{ so no} \\ \end{align*} Therefore all solutions are \((1,1), (2,3), (3,6), (4,10)\)

---

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\).
4. • \(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.

---

Solution:

1. Notice that \((1+x)^{2m+1} = 1+\binom{2m+1}{1}x+\cdots + \binom{2m+1}{m}x^{m} + \binom{2m+1}{m+1} + \cdots\). Notice also that \(\binom{2m+1}{m} = \binom{2m+1}{m+1}\). Therefore evaluating at \(x = 1\), we see \(2^{2m+1} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m} \Rightarrow \binom{2m+1}{m} < 2^{2m}\)
2. Each prime dividing \(P_{m+1, 2m+1}\) divides the numerator of \(\binom{2m+1}{m}\) since it appears in \((2m+1)!\), but not the denominator, since they wont appear in \(m!\) or \((m+1)!\), and since they are prime they have to appear to divide it. Therefore the must divide \(\binom{2m+1}{m}\) and therefore \(P_{m+1,2m+1}\) must divide that binomail coefficient. Since \(a \mid b \Rightarrow a \leq b\) we must have \(P_{m+1, 2m+1} \leq \binom{2m+1}{m} < 2^{2m}\)
3. Since \begin{align*} P_{1,2m+1} &= P_{1,m+1}P_{m+1, 2m+1} \tag{split into primes below \(m+1\) and abvoe} \\ &< 4^{m+1}P_{m+1,2m+1} \tag{use the condition from the question}\\ &<4^{m+1}2^{2m} \tag{use our inequality} \\ &= 4^{2m+1} \end{align*}
4. We proceed by (strong) induction. Base case: (\(n = 2\)): \(P_{1,2} = 2 < 4^2 =16\) Suppose it is true for all \(k=2,3,\cdots,2m\) then it is true for \(k=2m+1\) by the previous part of the question. However it is also true for \(k=2m+2\), since that can never be prime (as n is now an even number bigger than 2). Therefore by the principle of mathematical induction it is true for all \(n\).

---

Solution:

1. \(\,\) \begin{align*} && S & = 1 +\quad 2\quad \;\;+ \quad 3 \quad+ \cdots + \quad n \\ && S &= n + (n-1) + (n-2) + \cdots + 1 \\ && 2S &= (n+1) + (n+1) + \cdots + (n+1) \\ \Rightarrow && S &= \frac12n(n+1) \end{align*}
2. \(\,\) \begin{align*} && (N-m)^{k} + m^k&= \sum_{i=0}^k \binom{k}{i} N^{k-i} (-m)^{i} + m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i -m^k+m^k \\ &&&= N\sum_{i=0}^{k-1} \binom{k}{i}N^{k-i-1}(-m)^i \end{align*} which is clearly divisible by \(N\).

\begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=0}^n (\underbrace{(n-i)^k + i^k}_{\text{divisible by }n}) \\ \end{align*} Therefore \(2S\) is divisible by \(n\) and so if \(n\) is odd, \(n\) divides \(S\) and if \(n\) is even, \(\frac{n}{2}\) divides \(S\). Also notice \begin{align*} 2S &= 2\sum_{i=1}^n i^k \\ &= \sum_{i=1}^{n} (\underbrace{(n+1-i)^k + i^k}_{\text{divisible by }n+1}) \\ \end{align*} Therefore if \(n+1\) is odd, \(n+1 \mid S\) otherwise \(\frac{n+1}{2} \mid S\), and in either case \(\frac{n(n+1)}{2} \mid S\) (since they are both coprime) but this is the same as \(1 + 2 + \cdots + n \mid S\)

---

Solution: \begin{align*} {\mathrm D}^2 x^a &= x\frac{\d\ }{\d x}\left( x\frac{\d}{\d x} \left ( x^a \right) \right) \\ &= x\frac{\d\ }{\d x}\left( ax^a \right) \\ &= a^2 x^a \end{align*}

1. Claim: \({\mathrm D^n}(x^a) =a^n x^a\) Proof: Induct on \(n\). Base cases we have already seen, so consider \(D^{k+1}(x^a) = D(a^k x^a) = a^{k+1}x^a\) as required. Claim: \({\mathrm D}\) is linear, ie \({\mathrm D}(f(x) + g(x)) = {\mathrm D}(f(x)) + {\mathrm D}(g(x))\) Proof: \begin{align*} {\mathrm D}(f(x) + g(x)) &= x\frac{\d\ }{\d x}\left(f(x) + g(x) \right) \\ &= x\frac{\d\ }{\d x}f(x) + x\frac{\d\ }{\d x}g(x) \\ &= {\mathrm D}(f(x)) + {\mathrm D}(g(x)) \end{align*} Claim: If \(p(x)\) is a polynomial degree \(r\) then \({\mathrm D}^n p(x)\) is a polynomial degree \(n\). Proof: Since \({\mathrm D}\) is linear, it suffices to prove this for a monomial of degree \(n\), but this was already proven in the first question.
2. Claim: If \(f(x)\) is some polynomial, \({\mathrm D}((1-x)^m f(x))\) is divisible by \((1-x)^{m-1}\) Proof: \({\mathrm D}((1-x)^mf(x)) = -xm(1-x)^{m-1}f(x) + (1-x)^mxf'(x) = x(1-x)^{m-1}((1-x)f'(x)-xf(x))\) as required. Therefore repeated application of \({\mathrm D}\) will reduce the factor of \(1-x\) by at most \(1\) each time as required.
3. \begin{align*} {\mathrm D}^n(1-x)^m &= {\mathrm D}^n \left ( \sum_{r=0}^m \binom{m}{r}(-1)^r x^r\right) \\ &= \sum_{r=0}^m {\mathrm D}^n \left ( \binom{m}{r}(-1)^r x^r \right ) \\ &= \sum_{r=0}^m\binom{m}{r}(-1)^r r^n x^r \end{align*} Since the left-hand side is divisible by \(1-x\), if we substitute \(x = 1\), the sum must be \(0\), i.e., we get the desired result.
4. On each application of \({\mathrm D}\) to \((1-x)^m f(x)\) we end up with a term in the form \(x(1-x)^{m-1}(x)\) and a term of the form \((1-x)^m\). After the latter term will be annihilated once we evaluate at \(x = 1\) because there will be insufficient applications to remove the factors of \(1-x\). Therefore we only need to focus on the term which does not get annihilated. This term is will be \((-x)^n n \cdot (n-1) \cdots 1\), so \(f_n(1) = (-1)^n n!\) as required. Alternatively: \begin{align*} {\mathrm D}^n((1-x)^n) &= D^{n-1}(-nx(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(x(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}((x-1+1)(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(-(1-x)^{n}+(1-x)^{n-1}) \\ &= -n{\mathrm D}^{n-1}(-(1-x)^{n})-n{\mathrm D}^{n-1}((1-x)^{n-1}) \\ \end{align*} Therefore, when this is evaluated at \(x = 1\), recursively, we will have \(f_n(1) = -nf_{n-1}(1)\), in particular, \(f_n(1) = (-1)^n n!\)

---

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

---

Solution:

1. Suppose \(q^nN = p^n\) then since \((p,q) =1\) we must have \(p \mid N\), and then by dividing both \(p^n\) and \(N\) by \(p\) we can repeat this process \(n\) times to find that \(N = kp^n\) and in particular \(q = 1\). Suppose \(\sqrt[n]{N} = \frac{p}q\) for \(p,q\) coprime positive integers (ie it is not irrational), then \(q^nN = p^n\) and so \(q = 1\) and in fact \(\sqrt[n]{N}\) is an integer so \(N\).
2. Suppose \((a,b) = 1, (c,d) = 1\) and \(a^ad^b = b^ac^b\), then since \((a,b) = 1\) we must have \((b^a, a) = 1\) so \(b^a \mid d^b\). Similarly since \((c,d) = 1\) we must have \((d^b, c) = 1\) so \(d^b \mid b^a\). Therefore \(d^b = b^a\). Suppose \(p \mid d\) then \(p \mid d^b = b^a \Rightarrow p \mid b\). Suppose \(\nu_p(d) = m, \nu_p(b) = n\) we must have \(bm = \nu_p(d^b) = \nu_p(b^a) = an\), ie \(b = \frac{an}{m}\). Note that \(p^n \mid b \Rightarrow p^n \mid n \frac{a}{m} \Rightarrow p^n \mid n \Rightarrow p^n \leq n\). Since \((p,a) = 1\).. But since \(p^n > n\) if \(p \geq 2\) we must have that \(b = 1\). Therefore suppose \(r = \frac{a}{b}\) with \((a,b) = 1\) an \(r^r = \frac{c}{d}\) we must ahve \(a^ac^b = b^ad^b\) and so \(b = 1\) implying \(r\) is an integer.

---

Solution: Let \(\f(x) = x^n + a_{{n-1}}x^{n-1}+ \cdots + a_{2} x^2+ a_{1} x + a_{0}\), and suppose \(f(p/q) = 0\) with \((p,q) = 1\), the consider \begin{align*} && 0 &= q^{n-1}f(p/q) \\ &&&= \frac{p^n}{q} + \underbrace{a_{n-1}p^{n-1} + a_{n-2}p^{n-2}q + \cdots + a_0q^{n-1}}_{\in \mathbb{Z}} \\ \end{align*} But \(p^n/q \not \in \mathbb{Z}\) unless \(q = 1\) therefore \(p/q\) must be an integer, ie all rational roots are integers.

1. Note that \(\sqrt[n]2\) is a root of \(x^n - 2 =0\), but this has no integer solutions. (We can try all factors of \(2\)). Therefore all its roots must be irrational, ie \(\sqrt[n]2\) is irrational for \(n \geq 2\)
2. If \(n\) is a root of \(x^3 - x+1\) then it must be \(1\) or \(-1\) by the rational root theorem, ie \(1-1+1 \neq 0\) and \(-1 + 1 +1 \neq 0\), therefore no integer roots, therefore no rational roots.
3. Suppose \(m\) is an integer root of \(x^n - 5x + 7 = 0\) then by considering parity we must have \(m^n - 5m + 7 \equiv 1 \pmod{2}\) therefore we cannot have any rational roots.

---

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\)

---

Solution: \(p(x) = q(x)(x-1)^5 + 1\) where \(q(x)\) has degree \(4\).

1. \(p(1) = q(1)(1-1)^5 + 1 = 1\).
2. \(p'(x) = q'(x)(x-1)^5 + 5(x-1)^4q(x) + 0 = (x-1)^4((x-1)q'(x) + 5q(x))\) so \(p'(x)\) is divisible by \((x-1)^4\)
3. \(p(x)+1\) divisible by \((x+1)^5\) means that \(p(-1) = -1\) and \(p'(x)\) is divisible by \((x+1)^4\). Since \(p'(x)\) is degree \(8\) it must be \(c(x+1)^4(x-1)^4 = c(x^2 - 1)^4\). Expanding and integrating, we get \(p(x) = c(\frac{1}{9}x^9 -\frac{4}{7}x^7 + \frac{6}{5}x^5 - \frac{4}{3}x^3 + x) + d\). When \(x = 1\) we get \(c \frac{128}{315} + d = 1\) and when \(x = -1\) we get \(-c \frac{128}{315} + d = -1\) so \(2d = 0 \Rightarrow d = 0, c = \frac{315}{128}\) and \[ p(x) =\frac{315}{128} \l \frac{1}{9}x^9 -\frac{4}{7}x^7 + \frac{6}{5}x^5 - \frac{4}{3}x^3 + x\r \]