Exercise 4 — Candidates who have chosen the specialty course

An integer $N$ is said to be a triangular number if there exists a natural number $n$ such that: $N = 1 + 2 + \ldots + n$.
For example, 10 is a triangular number because $10 = 1 + 2 + 3 + 4$. The purpose of this problem is to determine triangular numbers that are perfect squares. Recall that, for every non-zero natural number $n$, we have:
$$1 + 2 + \ldots + n = \frac{n(n+1)}{2}$$

Part A: triangular numbers and perfect squares

1. Show that 36 is a triangular number, and that it is also the square of an integer.
2. a. Show that the number $1 + 2 + \ldots + n$ is the square of an integer if and only if there exists a natural number $p$ such that: $n^{2} + n - 2p^{2} = 0$. b. Deduce that the number $1 + 2 + \ldots + n$ is the square of an integer if and only if there exists a natural number $p$ such that: $(2n + 1)^{2} - 8p^{2} = 1$.

Part B: study of the associated Diophantine equation

Consider (E) the Diophantine equation
$$x^{2} - 8y^{2} = 1$$
where $x$ and $y$ denote two integers.

Exercise 5 -- For candidates who have followed the specialization course

A right-angled triangle with integer sides (TRPI) is a right-angled triangle whose three sides have lengths that are natural integers. If the triangle with sides $x$, $x+1$ and $y$, where $y$ is the length of the hypotenuse, is a TRPI, we will say that the couple $(x ; y)$ defines a TRPI.

Part A

1. Prove that the couple of natural integers $(x ; y)$ defines a TRPI if, and only if, we have: $$y^{2} = 2x^{2} + 2x + 1$$
2. Show that the TRPI having the smallest non-zero sides is defined by the couple $(3 ; 5)$.
3. a. Let $n$ be a natural integer. Show that if $n^{2}$ is odd then $n$ is odd. b. Show that in a couple of integers $(x ; y)$ defining a TRPI, the number $y$ is necessarily odd.
4. Show that if the couple of natural integers $(x ; y)$ defines a TRPI, then $x$ and $y$ are coprime.

Part B

We denote by $A$ the square matrix: $A = \left( \begin{array}{ll} 3 & 2 \\ 4 & 3 \end{array} \right)$, and $B$ the column matrix: $B = \binom{1}{2}$. Let $x$ and $y$ be two natural integers; we define the natural integers $x^{\prime}$ and $y^{\prime}$ by the relation: $$\binom{x^{\prime}}{y^{\prime}} = A\binom{x}{y} + B.$$

1. Express $x^{\prime}$ and $y^{\prime}$ as functions of $x$ and $y$. a. Show that: $y^{\prime 2} - 2x^{\prime}(x^{\prime}+1) = y^{2} - 2x(x+1)$. b. Deduce that if the couple $(x ; y)$ defines a TRPI, then the couple $(x^{\prime} ; y^{\prime})$ also defines a TRPI.
2. We consider the sequences $(x_{n})_{n \in \mathbb{N}}$ and $(y_{n})_{n \in \mathbb{N}}$ of natural integers, defined by $x_{0} = 3$, $y_{0} = 5$ and for every natural integer $n$: $$\binom{x_{n+1}}{y_{n+1}} = A\binom{x_{n}}{y_{n}} + B.$$ Show by induction that, for every natural integer $n$, the couple $(x_{n} ; y_{n})$ defines a TRPI.
3. Determine, by the method of your choice which you will specify, a TRPI whose side lengths are greater than 2017.

Exercise 4 — Candidates who have followed the specialization course

We consider the equation (E) $$x ^ { 2 } - 5 y ^ { 2 } = 1$$ where $x$ and $y$ are natural integers.

Part A

We suppose that ( $x ; y$ ) is a solution pair of equation (E).

1. Can $x$ and $y$ have the same parity? Justify.
2. Prove that $x$ and $y$ are coprime.
3. Let $k$ be a natural integer. Copy and complete the following table:
   

   \begin{tabular}{ l } Remainder of the euclidean

   division of $k$ by 5

   & 0 & 1 & 2 & 3 & 4 \hline

   Remainder of the euclidean

   division of $k ^ { 2 }$ by 5

   & & & & & \hline \end{tabular}
   
4. Deduce that $x \equiv 1$ [5] or $x \equiv 4$ [5].

Part B

Let $A$ be the matrix $\left( \begin{array} { c c } 9 & 20 \\ 4 & 9 \end{array} \right)$. We consider the sequences $\left( x _ { n } \right)$ and $\left( y _ { n } \right)$ defined by $$x _ { 0 } = 1 \text { and } y _ { 0 } = 0 \text {, and for all natural integer } n , \binom { x _ { n + 1 } } { y _ { n + 1 } } = A \binom { x _ { n } } { y _ { n } }$$

1. For all natural integer $n$, express $x _ { n + 1 }$ and $y _ { n + 1 }$ in terms of $x _ { n }$ and $y _ { n }$.
2. Prove by induction that, for all natural integer $n$, $\left( x _ { n } , y _ { n } \right)$ is a solution of equation (E).
3. a. Determine $A ^ { 2 }$, then deduce $x _ { 2 }$ and $y _ { 2 }$. b. Let $p$ be a natural integer. Prove that if $y _ { p }$ is a multiple of 9 then $y _ { p + 2 }$ is also a multiple of 9. c. Deduce that $y _ { 2020 }$ is a multiple of 9.

Show that there is no infinite arithmetic progression consisting of distinct integers all of which are squares.

The domain of a function $f$ is the set of natural numbers. The function is defined as follows: $$f(n) = n + \lfloor \sqrt{n} \rfloor$$ where $\lfloor k \rfloor$ denotes the nearest integer smaller than or equal to $k$. For example, $\lfloor \pi \rfloor = 3$, $\lfloor 4 \rfloor = 4$. Prove that for every natural number $m$ the following sequence contains at least one perfect square $$m, f(m), f^{2}(m), f^{3}(m), \ldots$$ The notation $f^{k}$ denotes the function obtained by composing $f$ with itself $k$ times, e.g., $f^{2} = f \circ f$.

List in increasing order all positive integers $n \leq 40$ such that $n$ cannot be written in the form $a^{2} - b^{2}$, where $a$ and $b$ are positive integers.

For how many natural numbers $n$ is $n^{6} + n^{4} + 1$ a square of a natural number?

[14 points] Suppose an integer $n > 1$ is such that $n + 1$ is not a multiple of 4 (i.e., such that $n$ is not congruent to $3 \bmod 4$). Prove that there exist $1 \leq i < j \leq n$ such that the following is a perfect square.
$$\frac { 1 ! 2 ! \cdots n ! } { i ! j ! }$$
Hint (use this or your own method): Make cases and first treat the case $n = 4k$.

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 ordered pairs $(a,b)$ of positive integers such that $a^2 - b^2 = 2024^2$. If there are infinitely many such pairs, write the word infinite as your answer. [3 points]

Find all solutions of the following equation where it is required that $x, k, y, n$ are positive integers with the exponents $k$ and $n$ both $> 1$. $$20x^k + 24y^n = 2024$$

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.

Find the number of integer solutions to $x^2 + y^2 = 2007$.

Find the number of positive integer solutions to $2^a - 5^b \cdot 7^c = 1$.

If $n$ is a positive integer such that $8n + 1$ is a perfect square, then
(A) $n$ must be odd
(B) $n$ cannot be a perfect square
(C) $2n$ cannot be a perfect square
(D) none of the above

If $n$ is a positive integer such that $8 n + 1$ is a perfect square, then
(a) $n$ must be odd
(b) $n$ cannot be a perfect square
(c) $2 n$ cannot be a perfect square
(d) none of the above.

If $n$ is a positive integer such that $8 n + 1$ is a perfect square, then
(a) $n$ must be odd
(b) $n$ cannot be a perfect square
(c) $2 n$ cannot be a perfect square
(d) none of the above.

If $n$ is a positive integer such that $8n + 1$ is a perfect square, then
(A) $n$ must be odd
(B) $n$ cannot be a perfect square
(C) $2n$ cannot be a perfect square
(D) none of the above

If $n$ is a positive integer such that $8 n + 1$ is a perfect square, then
(A) $n$ must be odd
(B) $n$ cannot be a perfect square
(C) $2 n$ cannot be a perfect square
(D) none of the above

Let $p _ { 1 } , p _ { 2 } , p _ { 3 }$ be primes with $p _ { 2 } \neq p _ { 3 }$, such that $4 + p _ { 1 } p _ { 2 }$ and $4 + p _ { 1 } p _ { 3 }$ are perfect squares. Find all possible values of $p _ { 1 } , p _ { 2 } , p _ { 3 }$.

The number of pairs of integers $( x , y )$ satisfying the equation $x y ( x + y + 1 ) = 5 ^ { 2018 } + 1$ is:
(A) 0
(B) 2
(C) 1009
(D) 2018.

The sum of all natural numbers $a$ such that $a ^ { 2 } - 16 a + 67$ is a perfect square is:
(A) 10
(B) 12
(C) 16
(D) 22.

The number of integers $n \geq 10$ such that the product $\binom { n } { 10 } \cdot \binom { n + 1 } { 10 }$ is a perfect square is
(A) 0
(B) 1
(C) 2
(D) 3

The number of all integer solutions of the equation $x ^ { 2 } + y ^ { 2 } + x - y = 2021$ is
(A) 5 .
(B) 7 .
(C) 1 .
(D) 0 .

For a positive integer $n$, the equation $$x ^ { 2 } = n + y ^ { 2 } , \quad x , y \text { integers} ,$$ does not have a solution if and only if
(A) $n = 2$.
(B) $n$ is a prime number.
(C) $n$ is an odd number.
(D) $n$ is an even number not divisible by 4 .