For an arbitrary integer $n$, let $g(n)$ be the GCD of $2n + 9$ and $6n^2 + 11n - 2$. What is the largest positive integer that can be obtained as the value of $g(n)$? If $g(n)$ can be arbitrarily large, state so explicitly and prove it.

A positive integer $n$ is called a magic number if it has the following property: if $a$ and $b$ are two positive numbers that are not coprime to $n$ then $a + b$ is also not coprime to $n$. For example, 2 is a magic number, because sum of any two even numbers is also even. Which of the following are magic numbers? Write your answers as a sequence of four letters (Y for Yes and N for No) in correct order.
(i) 129
(ii) 128
(iii) 127
(iv) 100.

Find all pairs $(p, n)$ of positive integers where $p$ is a prime number and $p^{3} - p = n^{7} - n^{3}$.

You are told that $n = 110179$ is the product of two primes $p$ and $q$. The number of positive integers less than $n$ that are relatively prime to $n$ (i.e. those $m$ such that $\operatorname{gcd}(m,n) = 1$) is 109480. Write the value of $p + q$. Then write the values of $p$ and $q$.

For a natural number $m$, define $\Phi_{1}(m)$ to be the number of divisors of $m$ and for $k \geq 2$ define $\Phi_{k}(m) := \Phi_{1}\left(\Phi_{k-1}(m)\right)$. For example, $\Phi_{2}(12) = \Phi_{1}(6) = 4$. Find the minimum $k$ such that $$\Phi_{k}\left(2019^{2019}\right) = 2.$$

For a positive integer $n$, let $D(n) =$ number of positive integer divisors of $n$. For example, $D(6) = 4$ because 6 has four divisors, namely $1, 2, 3$ and $6$. Find the number of $n \leq 60$ such that $D(n) = 6$.

Note that $25 \times 16 - 19 \times 21 = 1$. Using this or otherwise, find positive integers $a, b$ and $c$, all $\leq 475 = 25 \times 19$, such that

• $a$ is $1 \bmod 19$ and $0 \bmod 25$,
• $b$ is $0 \bmod 19$ and $1 \bmod 25$, and
• $c$ is $4 \bmod 19$ and $10 \bmod 25$.

(Recall the mod notation: since 13 divided by 5 gives remainder 3, we say 13 is $3 \bmod 5$.)

[15 points] Solve the following. You may do (i) and (ii) in either order.
(i) Let $p$ be a prime number. Show that $x^2 + x - 1$ has at most two roots modulo $p$, i.e., the cardinality of $\{n \mid 1 \leq n \leq p$ and $n^2 + n - 1$ is divisible by $p\}$ is $\leq 2$. Find all primes $p$ for which this set has cardinality 1.
(ii) Find all positive integers $n \leq 121$ such that $n^2 + n - 1$ is divisible by 121.
(iii) What can you say about the number of roots of $x^2 + x - 1$ modulo $p^2$ for an arbitrary prime $p$, i.e., the cardinality of
$$\left\{n \mid 1 \leq n \leq p^2 \text{ and } n^2 + n - 1 \text{ is divisible by } p^2\right\}?$$
You do NOT need to repeat any reasoning from previous parts. You may simply refer to any such relevant reasoning and state your conclusion with a brief explanation.

Statements
(25) There is a unique natural number $n$ such that $n ^ { 2 } + 19 n - n ! = 0$. (26) There are infinitely many pairs $( x , y )$ of natural numbers satisfying $$( 1 + x ! ) ( 1 + y ! ) = ( x + y ) ! .$$ (27) For any natural number $n$, consider GCD of $n ^ { 2 } + 1$ and $( n + 1 ) ^ { 2 } + 1$. As $n$ ranges over all natural numbers, the largest possible value of this GCD is 5. (28) If $n$ is the largest natural number for which 20! is divisible by $80 ^ { n }$, then $n \geq 5$.

We want to find odd integers $n > 1$ for which $n$ is a factor of $2023 ^ { n } - 1$.
(a) Find the two smallest such integers.
(b) Prove that there are infinitely many such integers.

Starting with any given positive integer $a > 1$ the following game is played. If $a$ is a perfect square, take its square root. Otherwise take $a + 3$. Repeat the procedure with the new positive integer (i.e., with $\sqrt { a }$ or $a + 3$ depending on the case). The resulting set of numbers is called the trajectory of $a$. For example the set $\{ 3, 6, 9 \}$ is a trajectory: it is the trajectory of each of its members.
Which numbers have a finite trajectory? Possible hint: Find the set $$\{ n \mid n \text{ is the smallest number in some trajectory } S \}.$$
If you wish, you can get partial credit by solving the following simpler questions.
(a) Show that there is no trajectory of cardinality 1 or 2.
(b) Show that $\{ 3, 6, 9 \}$ is the only trajectory of cardinality 3.
(c) Show that for any integer $k \geq 3$, there is a trajectory of cardinality $k$.
(d) Find an infinite trajectory.

Two mighty frogs jump once per unit time on the number line as described in the question.
The first frog is at $x = 2^i$ at time $t = i$. How many numbers of the form $7n+1$ (with $n$ an integer) does the frog visit from $t=0$ to $t=99$ (both endpoints included)? [3 points]

An integer $d$ is called a factor of an integer $n$ if there is an integer $q$ such that $n = qd$. In particular the set of factors of $n$ contains $n$ and contains 1. You are given that $2024 = 8 \times 11 \times 23$.
Write the number of even positive integers that are factors of $2024^2$. [2 points]

5. Let $\mathbb { Z }$ be the set of all integers. Let $A = \left\{ n \in \mathbb { Z } \mid n ^ { 2 } + 10 n + 21 \right.$ is divisible by 7 $\}$. Which of the following statements is/are true?
(a) $A = \{ n \in \mathbb { Z } \mid ( n \equiv 0 \bmod 7 ) \}$
(b) $A = \{ n \in \mathbb { Z } \mid ( n \equiv 0 \bmod 7 )$ or $( n \equiv 4 \bmod 7 ) \}$
(c) $A = \{ n \in \mathbb { Z } \mid ( n \equiv 1 \bmod 7 )$ or $( n \equiv 5 \bmod 7 ) \}$
(d) $A = \{ n \in \mathbb { Z } \mid ( n \equiv 2 \bmod 7 )$ or $( n \equiv 6 \bmod 7 ) \}$

For a natural number $m$ ($m \geq 2$), let $f ( m )$ be the number of natural numbers $n \geq 2$ such that an integer exists among the $n$-th roots of $m ^ { 12 }$. What is the value of $\sum _ { m = 2 } ^ { 9 } f ( m )$? [4 points]
(1) 37
(2) 42
(3) 47
(4) 52
(5) 57

Find all prime numbers $p$ such that $p ^ { 2 } + 2$ is also a prime number.

Find all prime numbers $p$ such that $p ^ { 2 } + 2$ is also a prime number.

Let $p$ be an odd prime number. For every integer $r \in \mathbb{Z}$, we denote by $\varphi(r)$ the remainder of the Euclidean division of $r^2$ by $p$. We thus have $0 \leqslant \varphi(r) \leqslant p - 1$ and $r^2 - \varphi(r) \in p\mathbb{Z}$. a) Show that the restriction of $\varphi$ to $\left\{0, \ldots, \frac{p-1}{2}\right\}$ is injective. b) We consider the sets $X = \left\{p - \varphi(r) \left\lvert\, 0 \leqslant r \leqslant \frac{p-1}{2}\right.\right\}$ and $Y = \left\{\varphi(s) + 1 \left\lvert\, 0 \leqslant s \leqslant \frac{p-1}{2}\right.\right\}$.
Show that $X$ and $Y$ are contained in $\{1, \ldots, p\}$ and that their intersection is non-empty. Deduce that there exist $u, v \in \left\{0, \ldots, \frac{p-1}{2}\right\}$ and $m \in \{1, \ldots, p-1\}$ such that $u^2 + v^2 + 1 = mp$.

We denote $\mathbb{G} = \{xe + yI + zJ + tK \mid x, y, z, t \in \mathbb{Z}\}$ the set of ``integer'' quaternions. For $q = xe + yI + zJ + tK \in \mathbb{H}$, $q^* = xe - yI - zJ - tK$ and $N(q) = x^2 + y^2 + z^2 + t^2$. We still assume that $p$ is an odd prime number. Justify that there exist $m \in \{1, \ldots, p-1\}$ and $\mu = xe + yI + zJ + tK \in \mathbb{G} \backslash \{0\}$ such that $N(\mu) = mp$. We choose $m$ minimal and assume that $m > 1$. a) Show that if $m$ were even, an even number of the integers $x, y, z, t$ would be odd and lead to a contradiction.
You may write $\left(\frac{x-y}{2}\right)^2 + \left(\frac{x+y}{2}\right)^2 = \frac{x^2 + y^2}{2}$. b) We assume $m$ is odd. Show that there exists $\nu \in \mathbb{G}$ such that $N(\mu - m\nu) < m^2$. c) Prove that $\mu' = \frac{1}{m}\mu(\mu - m\nu)^*$ is in $\mathbb{G} \backslash \{0\}$ and that $N(\mu')$ is a multiple of $p$ strictly less than $mp$. Conclude.

Show that every natural integer is a sum of four squares of integers.

Let $\Lambda$ be a non-empty subset of $\mathbb{R}_*^+$ closed under addition. We define $$\Gamma = \left\{z \in \mathbb{R}_+^* \mid \exists (x, y) \in \Lambda,\, z = y - x\right\}, \quad \text{and} \quad r(\Lambda) = \inf \Gamma.$$ Give two examples of such sets $\Lambda$, one for which $r(\Lambda) > 0$ and another for which $r(\Lambda) = 0$.

Let $\Lambda$ be a non-empty subset of $\mathbb{R}_*^+$ closed under addition, with $$\Gamma = \left\{z \in \mathbb{R}_+^* \mid \exists (x, y) \in \Lambda,\, z = y - x\right\}, \quad r(\Lambda) = \inf \Gamma.$$ We assume that $r(\Lambda) > 0$. Show that there exist $(a, b) \in \Lambda^2$ such that $b - a \in [r(\Lambda), 2r(\Lambda)[$.

Let $\Lambda$ be a non-empty subset of $\mathbb{R}_*^+$ closed under addition, with $r(\Lambda) > 0$. Let $(a, b) \in \Lambda^2$ such that $b - a \in [r(\Lambda), 2r(\Lambda)[$ and denote $d = b - a$. Let $k, n \in \mathbb{N}$ such that $k \leqslant n-1$. Show that $$\Lambda \cap [na + kd,\, na + (k+1)d] = \{na + kd,\, na + (k+1)d\}$$

Let $\Lambda$ be a non-empty subset of $\mathbb{R}_*^+$ closed under addition, with $r(\Lambda) > 0$. Let $(a, b) \in \Lambda^2$ such that $b - a \in [r(\Lambda), 2r(\Lambda)[$ and denote $d = b - a$. Show that there exists $n_0 \in \mathbb{N}$ such that $n_0 a + n_0 d > (n_0 + 1)a$, then that there exists $k \in \mathbb{N}$ such that $a = kd$.

Let $\Lambda$ be a non-empty subset of $\mathbb{R}_*^+$ closed under addition, with $r(\Lambda) > 0$ and $d = b - a$ as defined above. Deduce that $\Lambda \subset d\mathbb{Z}$, where $d\mathbb{Z} = \{kd \mid k \in \mathbb{Z}\}$.