We consider the following algorithm, where $A$ and $B$ are natural integers such that $A < B$:

Inputs:	$A$ and $B$ natural integers such that $A < B$
Variables:	$D$ is an integer
	The input variables $A$ and $B$
Processing:	Assign to $D$ the value of $B - A$
	While $D > 0$
	$B$ takes the value of $A$
	$A$ takes the value of $D$
	If $B > A$ Then
	$D$ takes the value of $B - A$
	Else
	$D$ takes the value of $A - B$
	End If
	End While
Output:	Display $A$

1. We enter $A = 12$ and $B = 14$. By filling in the table given in the appendix, determine the value displayed by the algorithm.
2. This algorithm calculates the value of the GCD of the numbers $A$ and $B$. By entering $A = 221$ and $B = 331$, the algorithm displays the value 1. a. Justify that there exist pairs $(x;y)$ of relative integers that are solutions of the equation $$(\mathrm{E}) \quad 221x - 331y = 1.$$ b. Verify that the pair $(3;2)$ is a solution of equation (E). Deduce the set of pairs $(x;y)$ of relative integers that are solutions of equation (E).
3. We consider the sequences of natural integers $(u_{n})$ and $(v_{n})$ defined for every natural integer $n$ by $$u_{n} = 2 + 221n \text{ and } \begin{cases} v_{0} = 3 \\ v_{n+1} = v_{n} + 331 \end{cases}$$ a. Express $v_{n}$ as a function of the natural integer $n$. b. Determine all pairs of natural integers $(p;q)$ such that $$u_{p} = v_{q}, \quad 0 \leqslant p \leqslant 500 \quad \text{and} \quad 0 \leqslant q \leqslant 500.$$

(Candidates who followed the specialization course)
Consider the sequence defined by its first term $u _ { 0 } = 3$ and, for every natural number $n$, by
$$u _ { n + 1 } = 2 u _ { n } + 6$$

1. Prove that, for every natural number $n$, $$u _ { n } = 9 \times 2 ^ { n } - 6$$
2. Prove that, for every integer $n \geqslant 1 , u _ { n }$ is divisible by 6. Define the sequence of integers ( $\nu _ { n }$ ) by, for every natural number $n \geqslant 1 , \nu _ { n } = \frac { u _ { n } } { 6 }$.
3. Consider the statement: ``for every non-zero natural number $n$, $v _ { n }$ is a prime number''. Indicate whether this statement is true or false by justifying the answer.
4. a. Prove that, for every integer $n \geqslant 1 , v _ { n + 1 } - 2 v _ { n } = 1$. b. Deduce that, for every integer $n \geqslant 1 , v _ { n }$ and $v _ { n + 1 }$ are coprime. c. Deduce, for every integer $n \geqslant 1$, the GCD of $u _ { n }$ and $u _ { n + 1 }$.
5. a. Verify that $2 ^ { 4 } \equiv 1 [ 5 ]$. b. Deduce that if $n$ is of the form $4 k + 2$ with $k$ a natural number, then $u _ { n }$ is divisible by 5. c. Is the number $u _ { n }$ divisible by 5 for the other values of the natural number $n$? Justify.

Question 140
Um fazendeiro possui um terreno retangular com 300 m de comprimento e 200 m de largura. Ele deseja dividir esse terreno em lotes quadrados de mesma área, sem que sobre nenhuma parte do terreno. O lado de cada lote deve ter a maior medida possível.
O número de lotes que o fazendeiro obterá é
(A) 6 (B) 8 (C) 10 (D) 12 (E) 15

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.

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$.

Throughout this subsection II.B, we fix two natural integers $m$ and $n$. The Chebyshev polynomials of the second kind $U_n$ have roots $\cos\left(\frac{k\pi}{n+2}\right)$ for $k = 1, \ldots, n+1$.
Let $h$ be the $\gcd$ in $\mathbb{N}$ of $m+1$ and $n+1$. By examining the common roots of $U_n$ and $U_m$, show that $U_{h-1}$ is a $\gcd$ in $\mathbb{R}[X]$ of $U_n$ and $U_m$.

Throughout this subsection II.B, we fix two natural integers $m$ and $n$. Let $g > 0$ be the $\gcd$ of $m$ and $n$. We set $m_1 = m/g$ and $n_1 = n/g$.
a) Show that if $m_1$ and $n_1$ are odd, then $T_g$ is a $\gcd$ of $T_n$ and $T_m$.
b) Show that if one of the two integers $m_1$ or $n_1$ is even, then $T_n$ and $T_m$ are coprime.
c) What can be said about the gcds of $T_n$ and $T_m$ when $m$ and $n$ are odd? When $n$ and $m$ are two distinct powers of 2?

Let $n \geqslant 2$ and $a_1, \ldots, a_n$ be integers not all zero. The purpose of this question is to show that there exists a matrix in $M_n(\mathbb{Z})$ whose first column is $(a_1, \ldots, a_n)$ and whose determinant is $\gcd(a_1, \ldots, a_n)$. For this we proceed by induction on $n$.
Let $N \in M_{n-1}(\mathbb{Z})$ be a matrix whose first column is $(a_2, \ldots, a_n)$. Given $u, v \in \mathbb{Q}$, we consider the matrix $$M = \left(\begin{array}{cccc|c} a_1 & 0 & \cdots & 0 & u \\ \hline & & & & va_2 \\ & N & & & va_3 \\ & & & & \vdots \\ & & & & va_n \end{array}\right).$$
4a. Express $\det M$ as a function of $\det N$, $u$ and $v$.
4b. Suppose that $a_2, \ldots, a_n$ are not all zero and that $\det N = \gcd(a_2, \ldots, a_n)$. Show that we can choose $u, v$ so that $M$ answers the question.
4c. Conclude the induction.

Let $M \in M_n(\mathbb{Z})$ with nonzero determinant. We wish to show that there exists a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $MA$ is upper triangular and, denoting $MA = (c_{ij})$, we have the inequalities $0 < c_{11}$ and $0 \leqslant c_{ij} < c_{ii}$ for all $i, j \in \{1, \ldots, n\}$ such that $i < j$.
5a. We denote $M = (x_1 | \cdots | x_n)$. Let $x_1', \ldots, x_n'$ be the elements of $\mathbb{Z}^{n-1}$ obtained by taking the last $(n-1)$ coordinates of $x_1, \ldots, x_n$. Show that there exist $a_1, \ldots, a_n$ in $\mathbb{Q}$, not all zero, such that $\sum_{i=1}^n a_i x_i' = 0$. Show that we can choose the $a_i$ to be integers that are coprime as a set.
5b. Show that there exists a matrix $A_1$ in $\mathrm{GL}_n(\mathbb{Z})$ such that the first column of $\tilde{C} = MA_1$ has all its coefficients $\tilde{c}_{i1}$ zero except the first $\tilde{c}_{11}$ which we can take to be strictly positive.
5c. By considering for all $j = 2, \ldots, n$ the Euclidean division $\tilde{c}_{1j} = q_j \tilde{c}_{11} + r_j$, $0 \leqslant r_j < \tilde{c}_{11}$, show that we can assume $\tilde{c}_{11} > \tilde{c}_{1j}$, if necessary by changing $A_1$.
5d. Conclude by induction.

Let $M \in M_n(\mathbb{Z})$ with nonzero determinant. Show that there exists a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $AM$ is lower triangular and, denoting $AM = (c_{ij})$, we have the inequality $0 \leqslant c_{ij} < c_{jj}$ for all $i, j \in \{1, \ldots, n\}$ such that $j < i$.

Let $m$ and $n$ be two non-zero natural integers that are coprime. Show that the map
$$\pi : \left\lvert\, \begin{gathered} \mathcal{D}_n \times \mathcal{D}_m \rightarrow \mathcal{D}_{mn} \\ \left( d_1, d_2 \right) \mapsto d_1 d_2 \end{gathered} \right.$$
is well-defined and realizes a bijection between $\mathcal{D}_n \times \mathcal{D}_m$ and $\mathcal{D}_{mn}$.

Let $m$ and $n$ be two non-zero natural integers that are coprime. Show that the map
$$\pi : \left\lvert\, \begin{gathered} \mathcal{D}_n \times \mathcal{D}_m \rightarrow \mathcal{D}_{mn} \\ \left( d_1, d_2 \right) \mapsto d_1 d_2 \end{gathered} \right.$$
is well-defined and establishes a bijection between $\mathcal{D}_n \times \mathcal{D}_m$ and $\mathcal{D}_{mn}$.

For every integer $k \geqslant 2$, we set $\zeta(k) = \sum_{n=1}^{+\infty} n^{-k}$.
Let $s, n \in \mathbb{N}^*$ with $2 \leqslant s \leqslant n$. We randomly draw $s$ numbers from $\{1, 2, \ldots, n\}$ and we denote $P_n(s)$ the probability that these numbers are coprime. Show that $$\lim_{n \rightarrow +\infty} P_n(s) = \frac{1}{\zeta(s)}$$ and give the value of $\lim_{n \rightarrow +\infty} P_n(s)$ in the case where $s = 2$, then $s = 4$, and finally $s = 6$.

For every integer $k \geqslant 2$, we set $\zeta(k) = \sum_{n=1}^{+\infty} n^{-k}$. Let $s, n \in \mathbb{N}^*$ with $2 \leqslant s \leqslant n$. We randomly draw $s$ numbers from $\{1, 2, \ldots, n\}$ and we denote $P_n(s)$ the probability that these numbers are coprime. Show that $$\lim_{n \rightarrow +\infty} P_n(s) = \frac{1}{\zeta(s)}$$ and give the value of $\lim_{n \rightarrow +\infty} P_n(s)$ in the case where $s = 2$, then $s = 4$, and finally $s = 6$.

Let $n$ be an integer coprime to $d$. Show that the map $$(a,b)\mapsto(na,nb)$$ is a bijection from $S_{\mathrm{prim}}(d)$ to $S_{\mathrm{prim}}(d)$.

Let $d_1$ and $d_2$ be two coprime integers and $m$ and $n$ be two integers such that $md_1+nd_2=1$. Show that the map $$\varphi:\left((a_1,b_1),(a_2,b_2)\right)\mapsto\left(nd_2 a_1+md_1 a_2,\, nd_2 b_1+md_1 b_2\right)$$ is a bijection from $S_{\mathrm{prim}}(d_1)\times S_{\mathrm{prim}}(d_2)$ to $S_{\mathrm{prim}}(d_1 d_2)$.

Let $r \in \mathbb { N } ^ { \star }$. Let $a _ { 1 } , \ldots , a _ { r }$ be non-zero natural integers. Justify that there exists a unique natural integer $d \left( a _ { 1 } , \ldots , a _ { r } \right)$ such that
$$a _ { 1 } \mathbb { Z } \cap a _ { 2 } \mathbb { Z } \cap \cdots \cap a _ { r } \mathbb { Z } = d \left( a _ { 1 } , \ldots , a _ { r } \right) \mathbb { Z }$$

Let $r \in \mathbb { N } ^ { * }$. Let $a _ { 1 } , \ldots , a _ { r }$ be non-zero natural integers. Show that $d \left( a _ { 1 } , \ldots , a _ { r } \right)$ is the smallest non-zero natural integer that is divisible by $a _ { 1 } , \ldots , a _ { r }$.

Calculate $d _ { 2 } , d _ { 3 }$ and $d _ { 4 }$, then show that $d _ { n } \leqslant n !$ for all natural integer $n \in \mathbb { N } ^ { * }$.

For all $n \in \mathbb { N } ^ { * }$, we denote by $d _ { n }$ the LCM of the natural integers between 1 and $n$, in other words: $d _ { n } = \operatorname { LCM } ( 1,2 , \ldots , n )$. For all prime number $p$, we denote by $k _ { p }$ the largest natural integer such that $p ^ { k _ { p } } \leqslant n$.
Show that $d _ { n } = \prod _ { \substack { p \leqslant n \\ p \text { prime } } } p ^ { k _ { p } }$.

For all $n \in \mathbb { N } ^ { * }$, we denote by $d _ { n }$ the LCM of the natural integers between 1 and $n$, in other words: $d _ { n } = \operatorname { LCM } ( 1,2 , \ldots , n )$. For all prime number $p$, we denote by $k _ { p }$ the largest natural integer such that $p ^ { k _ { p } } \leqslant n$.
For all prime number $p$, show that $k _ { p } = \left\lfloor \frac { \ln ( n ) } { \ln ( p ) } \right\rfloor$. Deduce that $d _ { n } \leqslant n ^ { \pi ( n ) }$.

Let $r$ and $s$ be two strictly positive natural integers such that $r > s$, and
$$J _ { r , s } = \frac { 1 } { r - s } \sum _ { k = s + 1 } ^ { r } \frac { 1 } { k }$$
Deduce that we can write
$$J _ { r , s } = \frac { p _ { r , s } } { q _ { r , s } }$$
with $p _ { r , s }$ and $q _ { r , s }$ natural integers and $q _ { r , s }$ dividing $d _ { r } ^ { 2 }$.

Let $X = \{0,1,2,3,\ldots,99\}$. For $a, b$ in $X$, we define $a * b$ to be the remainder obtained by dividing the product $ab$ by 100. For example, $9 * 18 = 62$ and $7 * 5 = 35$. Let $x$ be an element in $X$. An element $y$ in $X$ is called the inverse of $x$ if $x * y = 1$. Find all elements of $X$ that have inverses and write down their inverses.

Let $N$ be the smallest positive integer such that among any $N$ consecutive integers, at least one is coprime to $374 = 2 \times 11 \times 17$. Find $N$.
(A) 4 (B) 5 (C) 6 (D) 7

In the Mathematics department of a college, there are 60 first year students, 84 second year students, and 108 third year students. All of these students are to be divided into project groups such that each group has the same number of first year students, the same number of second year students, and the same number of third year students. What is the smallest possible size of each group?
(A) 9
(B) 12
(C) 19
(D) 21.