Exercise 2 — Candidates WHO HAVE FOLLOWED the mathematics specialization course

Part A

We consider the following algorithm:

Variables :	$a$ is a natural integer $b$ is a natural integer $c$ is a natural integer
Initialization :	Assign to $c$ the value 0 Request the value of $a$ Request the value of $b$
Processing :	While $a > b$ Assign to $c$ the value $c + 1$ Assign to $a$ the value $a - b$ End of while
Output :	Display $c$ Display $a$

1. Run this algorithm with $a = 13$ and $b = 4$ by indicating the values of the variables at each step.
2. What does this algorithm allow us to calculate?

Part B

To each letter of the alphabet, we associate, using the table below, an integer between 0 and 25.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

We define an encoding process as follows: Step 1: To the letter we want to encode, we associate the corresponding number $m$ in the table. Step 2: We calculate the remainder of the Euclidean division of $9 m + 5$ by 26 and denote it $p$. Step 3 : To the number $p$, we associate the corresponding letter in the table.

1. Encode the letter U.
2. Modify the algorithm from Part A so that for a value of $m$ entered by the user, it displays the value of $p$, calculated using the above encoding process.

Part C

1. Find an integer $x$ such that $9 x \equiv 1$ [26].
2. Then prove the equivalence: $$9 m + 5 \equiv p \quad [ 26 ] \Longleftrightarrow m \equiv 3 p - 15$$
3. Then decode the letter B.

Exercise 4 — For candidates who have followed the specialization course
Let $E$ denote the set of twenty-seven integers between 0 and 26.
Let $A$ denote the set whose elements are the twenty-six letters of the alphabet and a separator between two words, denoted ``$\star$'' and considered as a character.
To encode the elements of $A$, we proceed as follows:

• First: We associate to each of the letters of the alphabet, arranged in alphabetical order, a natural integer between 0 and 25, arranged in increasing order. We thus have $a \rightarrow 0 , b \rightarrow 1 , \ldots z \rightarrow 25$. We associate to the separator ``$\star$'' the number 26.
• Second: to each element $x$ of $E$, the function $g$ associates the remainder of the Euclidean division of $4 x + 3$ by 27. Note that for every $x$ in $E$, $g ( x )$ belongs to $E$.
• Third: The initial character is then replaced by the character of rank $g ( x )$.

Example: $s \rightarrow 18 , \quad g ( 18 ) = 21$ and $21 \rightarrow v$. So the letter $s$ is replaced during encoding by the letter $v$.
1. Find all integers $x$ of $E$ such that $g ( x ) = x$, that is, invariant under $g$.
Deduce the invariant characters in this encoding.
2. Prove that, for every natural number $x$ belonging to $E$ and every natural number $y$ belonging to $E$, if $y \equiv 4 x + 3$ modulo 27 then $x \equiv 7 y + 6$ modulo 27.
Deduce that two distinct characters are encoded by two distinct characters.
3. Propose a decoding method.
4. Decode the word ``vfv''.

(For candidates who have followed the specialization course)
In this exercise, we call the number of the day of birth the rank of this day in the month and the number of the month of birth, the rank of the month in the year. For example, for a person born on May 14, the number of the day of birth is 14 and the number of the month of birth is 5.

Part A

During a performance, a magician asks spectators to perform the following calculation program (A): ``Take the number of your day of birth and multiply it by 12. Take the number of your month of birth and multiply it by 37. Add the two numbers obtained. I will then be able to give you the date of your birthday''.
A spectator announces 308 and in a few seconds, the magician declares: ``Your birthday falls on August $1^{\text{st}}$!''.

1. Verify that for a person born on August $1^{\text{st}}$, calculation program (A) indeed gives the number 308.
2. a. For a given spectator, we denote $j$ the number of their day of birth, $m$ that of their month of birth and $z$ the result obtained by applying calculation program (A). Express $z$ as a function of $j$ and $m$ and prove that $z$ and $m$ are congruent modulo 12. b. Then find the birthday of a spectator who obtained the number 474 by applying calculation program (A).

Part B

During another performance, the magician decides to change their calculation program. For a spectator whose day of birth number is $j$ and month of birth number is $m$, the magician asks to calculate the number $z$ defined by $z = 12j + 31m$. In the following questions, we study different methods to find the spectator's birthday.

1. First method:
   We consider the following algorithm: \begin{verbatim} Variables: j and m are natural integers Processing : For m ranging from 1 to 12 do: For j ranging from 1 to 31 do: z takes the value 12j+31m Display z End For End For \end{verbatim} Modify this algorithm so that it displays all values of $j$ and $m$ such that $12j + 31m = 503$.
2. Second method: a. Prove that $7m$ and $z$ have the same remainder in the Euclidean division by 12. b. For $m$ varying from 1 to 12, give the remainder of the Euclidean division of $7m$ by 12. c. Deduce the birthday of a spectator who obtained the number 503 with calculation program (B).
3. Third method: a. Prove that the pair $(-2; 17)$ is a solution of the equation $12x + 31y = 503$. b. Deduce that if a pair of relative integers $(x; y)$ is a solution of the equation $12x + 31y = 503$, then $12(x + 2) = 31(17 - y)$. c. Determine the set of all pairs of relative integers $(x; y)$, solutions of the equation $12x + 31y = 503$. d. Prove that there exists a unique pair of relative integers $(x; y)$ such that $1 \leqslant y \leqslant 12$. Deduce the birthday of a spectator who obtained the number 503 with calculation program (B).

Exercise 4 — Candidates who have chosen the specialization option

In the mountains, a hiker made reservations in two types of accommodations: Accommodation A and Accommodation B. One night in accommodation A costs $24 €$ and one night in accommodation B costs $45 €$. He remembers that the total cost of his reservation is $438 €$. We wish to find the numbers $x$ and $y$ of nights spent respectively in accommodation $A$ and accommodation $B$.

1. a. Show that the numbers $x$ and $y$ are respectively less than or equal to 18 and 9. b. Copy and complete lines (1), (2) and (3) of the following algorithm so that it displays the possible pairs ( $x ; y$ ).
   

   Input: Processing:	\begin{tabular}{l} $x$ and $y$ are numbers
   For $x$ varying from $0$ to $\ldots$ (1)
   For $y$ varying from $0$ to $\ldots$ (2)
   If $\ldots$ (3) Display $x$ and $y$ End If End For End For

   \hline \end{tabular}
   
2. Justify that the total cost of the reservation is a multiple of 3.
   
3. a. Justify that the equation $8 x + 15 y = 1$ admits at least one solution in integers. b. Determine such a solution. c. Solve the equation (E): $8 x + 15 y = 146$ where $x$ and $y$ are integers.
   
4. The hiker remembers having spent at most 13 nights in accommodation A. Show then that he can find the exact number of nights spent in accommodation A and that of nights spent in accommodation B. Calculate these numbers.

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

Part A

We consider the equation (E): $15 x - 26 k = m$ where $x$ and $k$ denote relative integers and $m$ is a non-zero integer parameter.

1. Justify, by stating a theorem, that there exists a pair of relative integers $( u ; v )$ such that $15 u - 26 v = 1$. Find such a pair.
2. Deduce a particular solution ( $x _ { 0 } ; k _ { 0 }$ ) of equation (E).
3. Show that ( $x ; k$ ) is a solution of equation (E) if and only if $15 \left( x - x _ { 0 } \right) - 26 \left( k - k _ { 0 } \right) = 0$.
4. Show that the solutions of equation (E) are exactly the pairs ( $x$; $k$ ) of relative integers such that: $$\left\{ \begin{array} { l } x = 26 q + 7 m \\ k = 15 q + 4 m \end{array} \text { where } q \in \mathbb { Z } . \right.$$

Part B

We associate with each letter of the alphabet an integer as indicated in the table below.

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

We define an encoding system:

• to each letter of the alphabet, we associate the corresponding integer $x$,
• we then associate to $x$ the integer $y$ which is the remainder of the Euclidean division of $15 x + 7$ by 26,
• we associate to $y$ the corresponding letter.

Thus, by this method, the letter E is associated with 4, 4 is transformed into 15 and 15 corresponds to the letter P, and therefore the letter E is encoded by the letter P.

1. Encode the word MATHS.
2. Let $x$ be the number associated with a letter of the alphabet using the initial table and $y$ be the remainder of the Euclidean division of $15 x + 7$ by 26. a. Show then that there exists a relative integer $k$ such that $15 x - 26 k = y - 7$. b. Deduce that $x \equiv 7 y + 3 ( \bmod 26 )$. c. Deduce a description of the decoding system associated with the encoding system considered.
3. Explain why the letter W in an encoded message will be decoded by the letter B. Decode the word WHL.
4. Show that, by this encoding system, two different letters are encoded by two different letters.

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 4 (5 points) -- Candidate who has followed the specialization course

Numbers of the form $2^n - 1$ where $n$ is a non-zero natural number are called Mersenne numbers.

1. We denote by $a$, $b$ and $c$ three non-zero natural numbers such that $\operatorname{GCD}(b\,;\,c) = 1$.
   Prove, using Gauss's theorem, that: if $b$ divides $a$ and $c$ divides $a$ then the product $bc$ divides $a$.
2. We consider the Mersenne number $2^{33} - 1$.
   A student uses his calculator and obtains the results below:
   

   $\left(2^{33}-1\right) \div 3$	2863311530
   $\left(2^{33}-1\right) \div 4$	2147483648
   $\left(2^{33}-1\right) \div 12$	715827882.6

   
   He claims that 3 divides $\left(2^{33}-1\right)$ and 4 divides $\left(2^{33}-1\right)$ and 12 does not divide $\left(2^{33}-1\right)$. a. How does this claim contradict the result proved in question 1? b. Justify that, in reality, 4 does not divide $\left(2^{33}-1\right)$. c. By noting that $2 \equiv -1\ [3]$, show that, in reality, 3 does not divide $2^{33}-1$. d. Calculate the sum $S = 1 + 2^3 + \left(2^3\right)^2 + \left(2^3\right)^3 + \cdots + \left(2^3\right)^{10}$. e. Deduce that 7 divides $2^{33}-1$.
3. We consider the Mersenne number $2^7 - 1$. Is it prime? Justify.
4. We are given the following algorithm where $\operatorname{MOD}(N,k)$ represents the remainder of the Euclidean division of $N$ by $k$:
   

   Variables:

   $n$ natural number greater than or equal to 3

   $k$ natural number greater than or equal to 2

   Initialization:

   Ask the user for the value of $n$.

   Assign to $k$ the value 2.

   Processing:

   While $\operatorname{MOD}\left(2^n - 1,\,k\right) \neq 0$ and $k \leqslant \sqrt{2^n - 1}$

   Assign to $k$ the value $k+1$

   End While.

   Output:

   Otherwise

   Display ``CASE 2''

   End If

   
   a. What does this algorithm display if we enter $n = 33$? And if we enter $n = 7$? b. What does CASE 2 correspond to?

For every pair of non-zero integers $(a, b)$, we denote by $\operatorname{gcd}(a, b)$ the greatest common divisor of $a$ and $b$. The plane is equipped with a coordinate system $(\mathrm{O}; \vec{\imath}, \vec{\jmath})$.

1. Example. Let $\Delta_{1}$ be the line with equation $y = \frac{5}{4}x - \frac{2}{3}$. a. Show that if $(x, y)$ is a pair of integers then the integer $15x - 12y$ is divisible by 3. b. Does there exist at least one point on the line $\Delta_{1}$ whose coordinates are two integers? Justify.

Generalization: We now consider a line $\Delta$ with equation $(E): y = \frac{m}{n}x - \frac{p}{q}$ where $m, n, p$ and $q$ are non-zero integers such that $\operatorname{gcd}(m, n) = \operatorname{gcd}(p, q) = 1$. Thus, the coefficients of equation $(E)$ are irreducible fractions and we say that $\Delta$ is a rational line. The purpose of the exercise is to determine a necessary and sufficient condition on $m, n, p$ and $q$ for a rational line $\Delta$ to contain at least one point whose coordinates are two integers.

1. We suppose here that the line $\Delta$ contains a point with coordinates $(x_{0}, y_{0})$ where $x_{0}$ and $y_{0}$ are integers. a. By noting that the number $ny_{0} - mx_{0}$ is an integer, prove that $q$ divides the product $np$. b. Deduce that $q$ divides $n$.
2. Conversely, we suppose that $q$ divides $n$, and we wish to find a pair $(x_{0}, y_{0})$ of integers such that $y_{0} = \frac{m}{n}x_{0} - \frac{p}{q}$. a. We set $n = qr$, where $r$ is a non-zero integer. Prove that we can find two integers $u$ and $v$ such that $qru - mv = 1$. b. Deduce that there exists a pair $(x_{0}, y_{0})$ of integers such that $y_{0} = \frac{m}{n}x_{0} - \frac{p}{q}$.
3. Let $\Delta$ be the line with equation $y = \frac{3}{8}x - \frac{7}{4}$. Does this line have a point whose coordinates are integers? Justify.

We consider the following equation with unknowns $x$ and $y$ integers: $$7x - 3y = 1 \tag{E}$$

1. An incomplete algorithm is given below. Copy it and complete it, writing its missing lines (1) and (2) so that it gives the integer solutions $(x; y)$ of the equation (E) satisfying $-5 \leqslant x \leqslant 10$ and $-5 \leqslant y \leqslant 10$.
   

   Variables:

   X is an integer

   Y is an integer

   Start:

   For X varying from $-5$ to 10

   (1) \ldots

   (2) \ldots

   Then Display X and Y

   End If

   End For

   End

   
   
2. a. Give a particular solution of equation (E). b. Determine the set of pairs of integers solutions of equation (E). c. Determine the set of pairs $(x; y)$ of integers solutions of equation (E) such that $-5 \leqslant x \leqslant 10$ and $-5 \leqslant y \leqslant 10$.

Exercise 4 - Candidates who have followed the specialization course

For each of the five following propositions, indicate whether it is true or false and justify the answer chosen. One point is awarded for each correct answer correctly justified. An unjustified answer is not taken into account. An absence of answer is not penalized.

Proposition 1:

For every natural integer $n$, the units digit of $n ^ { 2 } + n$ is never equal to 4.

Proposition 2:

We consider the sequence $u$ defined, for $n \geqslant 1$, by $$u _ { n } = \frac { 1 } { n } \operatorname { gcd } ( 20 ; n ) .$$ The sequence $\left( u _ { n } \right)$ is convergent.

Proposition 3:

For all square matrices $A$ and $B$ of dimension 2, we have $A \times B = B \times A$.

Proposition 4:

A mobile can occupy two positions $A$ and $B$. At each step, it can either remain in the position it is in or change it. For every natural integer $n$, we denote $a_n$ (resp. $b_n$) the probability that the mobile is in position $A$ (resp. $B$) at step $n$.

Exercise 5 — Candidates who have followed the specialization course The natural integers $1, 11, 111, 1111, \ldots$ are rep-units. These are natural integers written only with 1s. For all non-zero natural integer $p$, we denote $N _ { p }$ the rep-unit written with $p$ times the digit 1:
$$N _ { p } = \underbrace { 11 \ldots 1 } _ { \substack { p \text { repetitions } \\ \text { of the digit 1 } } } = \sum _ { k = 0 } ^ { k = p - 1 } 10 ^ { k }$$
Throughout the exercise, $p$ denotes a non-zero natural integer. The purpose of this exercise is to study some properties of rep-units.
Part A: divisibility of rep-units in some particular cases

1. Show that $N _ { p }$ is divisible neither by 2 nor by 5.
2. In this question, we study the divisibility of $N _ { p }$ by 3. a. Prove that, for all natural integer $j$, $10 ^ { j } \equiv 1 \bmod 3$. b. Deduce that $N _ { p } \equiv p \bmod 3$. c. Determine a necessary and sufficient condition for the rep-unit $N _ { p }$ to be divisible by 3.
3. In this question, we study the divisibility of $N _ { p }$ by 7. a. Copy and complete the congruence table below, where $a$ is the unique relative integer belonging to $\{ - 3 ; - 2 ; - 1 ; 0 ; 1 ; 2 ; 3 \}$ such that $10 ^ { m } \equiv a \bmod 7$. No justification is required.
   

   $m$	0	1	2	3	4	5	6
   $a$

   
   b. Let $p$ be a non-zero natural integer. Show that $10 ^ { p } \equiv 1 \bmod 7$ if and only if $p$ is a multiple of 6. You may use the Euclidean division of $p$ by 6. c. Justify that, for all natural integer $p$ non-zero, $N _ { p } = \frac { 10 ^ { p } - 1 }{ 9 }$.

Exercise 4 (Candidates who have followed the specialization course)
A bank card number is of the form: $$a _ { 1 } a _ { 2 } a _ { 3 } a _ { 4 } a _ { 5 } a _ { 6 } a _ { 7 } a _ { 8 } a _ { 9 } a _ { 10 } a _ { 11 } a _ { 12 } a _ { 13 } a _ { 14 } a _ { 15 } c$$ where $a _ { 1 } , a _ { 2 } , \ldots , a _ { 15 }$ and $c$ are digits between 0 and 9. The first fifteen digits contain information about the card type, the bank, and the bank account number. $c$ is the validation key for the number. This digit is calculated from the other fifteen. The following algorithm allows validation of the conformity of a given card number.
Initialization: $I$ takes the value 0 $P$ takes the value 0 $R$ takes the value 0 Processing: For $k$ going from 0 to 7: $R$ takes the value of the remainder of the Euclidean division of $2 a _ { 2 k + 1 }$ by 9 $I$ takes the value $I + R$ End For For $k$ going from 1 to 7: $P$ takes the value $P + a _ { 2 k }$ End For $S$ takes the value $I + P + c$ Output: If $S$ is a multiple of 10

Exercise 4 — Candidates who have followed the specialization course
A person has developed the following encryption process: — To each letter of the alphabet, we associate an integer $n$ as indicated below:

A	B	C	D	E	F	G	H	I	J	K	L	M
0	1	2	3	4	5	6	7	8	9	10	11	12
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
13	14	15	16	17	18	19	20	21	22	23	24	25

— We choose two integers $a$ and $b$ between 0 and 25. — Every integer $n$ between 0 and 25 is encoded by the remainder of the Euclidean division of $an + b$ by 26. The following table gives the frequencies $f$ in percentage of letters used in a text written in French.

Letter	A	B	C	D	E	F	G	H	I	J	K	L	M
Frequency	9.42	1.02	2.64	3.38	15.87	0.94	1.04	0.77	8.41	0.89	0.00	5.33	3.23

Letter	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Frequency	7.14	5.13	2.86	1.06	6.46	7.90	7.26	6.24	2.15	0.00	0.30	0.24	0.32

Part A
A text written in French and sufficiently long has been encoded according to this process. Frequency analysis of the encoded text showed that it contains $15.9\%$ of O and $9.4\%$ of E. We wish to determine the numbers $a$ and $b$ that allowed the encoding.

1. Which letters were encoded by the letters O and E?
2. Show that the integers $a$ and $b$ are solutions of the system $$\left\{ \begin{array}{l} 4a + b \equiv 14 [26] \\ b \equiv 4 [26] \end{array} \right.$$
3. Determine all pairs of integers $(a, b)$ that could have allowed the encoding of this text.

Part B

1. We choose $a = 22$ and $b = 4$. a. Encode the letters K and X. b. Is this encoding feasible?
2. We choose $a = 9$ and $b = 4$. a. Show that for all natural integers $n$ and $m$, we have: $$m \equiv 9n + 4 [26] \Longleftrightarrow n \equiv 3m + 14 [26]$$ b. Decode the word AQ.

An association assigns each registered child a 6-digit number $c_1 c_2 c_3 c_4 c_5 k$ where:

• $c_1 c_2$ represents the last two digits of the child's birth year;
• $c_3 c_4 c_5$ are three digits chosen by the association;
• $k$ is a check digit computed as follows:

• we compute the sum $S = c_1 + c_3 + c_5 + a \times (c_2 + c_4)$ where $a$ is an integer between 1 and 9;
• we perform the Euclidean division of $S$ by 10, the remainder obtained is the check digit $k$.

When an employee enters the 6-digit number of a child, an input error can be detected when the sixth digit is not equal to the check digit calculated from the first five digits.

1. In this question only, we choose $a = 3$. a. Can the number 111383 be that of a child registered with the association? b. The employee, confusing a brother and sister, exchanges their birth years: 2008 and 2011. Thus, the number $08c_3c_4c_5k$ is transformed into $11c_3c_4c_5k$. Is this error detected thanks to the check digit?
2. We denote $c_1c_2c_3c_4c_5k$ the number of a child. We seek the values of the integer $a$ for which the check digit systematically detects the typing error when the digits $c_3$ and $c_4$ are swapped. We therefore assume that the digits $c_3$ and $c_4$ are distinct. a. Show that the check digit does not detect the error of swapping the digits $c_3$ and $c_4$ if and only if $(a-1)(c_4 - c_3)$ is congruent to 0 modulo 10. b. Determine the integers $n$ between 0 and 9 for which there exists an integer $p$ between 1 and 9 such that $np \equiv 0 \pmod{10}$. c. Deduce the values of the integer $a$ which allow, thanks to the check digit, to systematically detect the swap of the digits $c_3$ and $c_4$.

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

We consider a ``word'' formed of 4 bits which we denote $b _ { 1 } , b _ { 2 } , b _ { 3 }$ and $b _ { 4 }$. We add to this list a check key $c _ { 1 } c _ { 2 } c _ { 3 }$ formed of three bits:

• $c _ { 1 }$ is the remainder of the Euclidean division of $b _ { 2 } + b _ { 3 } + b _ { 4 }$ by 2;
• $c _ { 2 }$ is the remainder of the Euclidean division of $b _ { 1 } + b _ { 3 } + b _ { 4 }$ by 2;
• $c _ { 3 }$ is the remainder of the Euclidean division of $b _ { 1 } + b _ { 2 } + b _ { 4 }$ by 2.

We then call ``message'' the sequence of 7 bits formed of the 4 bits of the word and the 3 control bits.

1. Preliminaries a. Justify that $c _ { 1 } , c _ { 2 }$ and $c _ { 3 }$ can only take the values 0 or 1. b. Calculate the check key associated with the word 1001.
   
2. Let $b _ { 1 } b _ { 2 } b _ { 3 } b _ { 4 }$ be a word of 4 bits and $c _ { 1 } c _ { 2 } c _ { 3 }$ the associated key. Prove that if we change the value of $b _ { 1 }$ and recalculate the key, then:
   • the value of $c _ { 1 }$ is unchanged;
   • the value of $c _ { 2 }$ is modified;
   • the value of $c _ { 3 }$ is modified.
   
   
3. We assume that, during the transmission of the message, at most one of the 7 bits was transmitted incorrectly. From the first four bits of the received message, we recalculate the 3 control bits, and compare them with the received control bits. Without justification, copy and complete the table below. The letter $F$ means that the received control bit does not match the calculated control bit, and $J$ means that these two bits are equal.
   

   \backslashbox{Calculated control bit}{Erroneous bit}	$b _ { 1 }$	$b _ { 2 }$	$b _ { 3 }$	$b _ { 4 }$	$c _ { 1 }$	$c _ { 2 }$	$c _ { 3 }$	None
   $c _ { 1 }$	$J$
   $c _ { 2 }$	$F$
   $c _ { 3 }$	$F$

   
   
4. Justify briefly, using the table, that if a single received bit is erroneous, we can in all cases determine which one it is, and correct the error.
   
5. Here are two messages of 7 bits: $$A = 0100010 \quad \text { and } \quad B = 1101001 .$$ We admit that each of them contains at most one transmission error. Say whether they contain an error, and correct it if necessary.

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 (For candidates who have followed the specialty course)

We denote $\mathbb{Z}$ the set of integers. In this exercise, we study the set $S$ of matrices that can be written in the form $A = \left(\begin{array}{cc} a & b \\ c & d \end{array}\right)$, where $a, b, c$ and $d$ belong to the set $\mathbb{Z}$ and satisfy: $ad - bc = 1$. We denote $I$ the identity matrix $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$.

Part A

1. Verify that the matrix $A = \left(\begin{array}{rr} 6 & 5 \\ -5 & -4 \end{array}\right)$ belongs to the set $S$.
2. Show that there exist exactly four matrices of the form $A = \left(\begin{array}{ll} a & 2 \\ 3 & d \end{array}\right)$ belonging to the set $S$; state them explicitly.
3. a. Solve in $\mathbb{Z}$ the equation $(E): 5x - 2y = 1$. We may note that the pair $(1; 2)$ is a particular solution of this equation. b. Deduce that there exist infinitely many matrices of the form $A = \left(\begin{array}{cc} a & b \\ 2 & 5 \end{array}\right)$ that belong to the set $S$. Describe these matrices.

Part B

In this part, we denote $A = \left(\begin{array}{ll} a & b \\ c & d \end{array}\right)$ a matrix belonging to the set $S$. We recall that $a$, $b$, $c$ and $d$ are integers such that $ad - bc = 1$.

1. Show that the integers $a$ and $b$ are coprime.
2. Let $B$ be the matrix: $B = \left(\begin{array}{rr} d & -b \\ -c & a \end{array}\right)$ a. Calculate the product $AB$. It is admitted that $AB = BA$. b. Deduce that the matrix $A$ is invertible and give its inverse matrix $A^{-1}$. c. Show that $A^{-1}$ belongs to the set $S$.
3. Let $x$ and $y$ be two integers. We denote $x'$ and $y'$ the integers such that $\binom{x'}{y'} = A\binom{x}{y}$. a. Show that $x = dx' - by'$. It is admitted that likewise $y = ay' - cx'$. b. We denote $D$ the GCD of $x$ and $y$ and we denote $D'$ the GCD of $x'$ and $y'$. Show that $D = D'$.
4. We consider the sequences of natural numbers $(x_n)$ and $(y_n)$ defined by: $x_0 = 2019$, $y_0 = 673$ and for any natural number $n$: $$\left\{\begin{array}{l} x_{n+1} = 2x_n + 3y_n \\ y_{n+1} = x_n + 2y_n \end{array}\right.$$ Using the previous question, determine, for any natural number $n$, the GCD of the integers $x_n$ and $y_n$.

Exercise 4 — For candidates who have followed the speciality course
We consider the matrix $M = \left( \begin{array} { l l } 2 & 3 \\ 1 & 2 \end{array} \right)$ and the sequences of natural numbers $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by: $u _ { 0 } = 1 , v _ { 0 } = 0$, and for every natural number $n , \binom { u _ { n + 1 } } { v _ { n + 1 } } = M \binom { u _ { n } } { v _ { n } }$. The two parts can be treated independently.

Part A

The first terms of the sequence $\left( v _ { n } \right)$ have been calculated:

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12
$v _ { n }$	0	1	4	15	56	209	780	2911	10864	40545	151316	564719	2107560

1. Conjecture the possible values of the units digit of the terms of the sequence $\left( v _ { n } \right)$.
2. It is admitted that for every natural number $n , \binom { u _ { n + 3 } } { v _ { n + 3 } } = M ^ { 3 } \binom { u _ { n } } { v _ { n } }$. a. Justify that for every natural number $n , \left\{ \begin{array} { l } u _ { n + 3 } = 26 u _ { n } + 45 v _ { n } \\ v _ { n + 3 } = 15 u _ { n } + 26 v _ { n } \end{array} \right.$. b. Deduce that for every natural number $n : v _ { n + 3 } \equiv v _ { n } [ 5 ]$.
3. Let $r$ be a fixed natural number. Prove, using a proof by induction, that, for every natural number $q , v _ { 3 q + r } \equiv v _ { r }$ [5].
4. Deduce that for every natural number $n$ the term $v _ { n }$ is congruent to 0, to 1 or to 4 modulo 5.
5. Conclude regarding the set of values taken by the units digit of the terms of the sequence $\left( v _ { n } \right)$.

Part B

The objective of this part is to prove that $\sqrt { 3 }$ is not a rational number using the matrix $M$.
To do this, we perform a proof by contradiction and assume that $\sqrt { 3 }$ is a rational number. In this case, $\sqrt { 3 }$ can be written in the form of an irreducible fraction $\frac { p } { q }$ where $p$ and $q$ are non-zero natural numbers, with $q$ the smallest possible natural number.

1. Show that $q < p < 2 q$.
2. It is admitted that the matrix $M$ is invertible. Give its inverse $M ^ { - 1 }$ (no justification is expected). Let the pair $\left( p ^ { \prime } ; q ^ { \prime } \right)$ be defined by $\binom { p ^ { \prime } } { q ^ { \prime } } = M ^ { - 1 } \binom { p } { q }$.
3. a. Verify that $p ^ { \prime } = 2 p - 3 q$ and that $q ^ { \prime } = - p + 2 q$. b. Justify that ( $p ^ { \prime } ; q ^ { \prime }$ ) is a pair of relative integers. c. Recall that $p = q \sqrt { 3 }$. Show that $p ^ { \prime } = q ^ { \prime } \sqrt { 3 }$. d. Show that $0 < q ^ { \prime } < q$. e. Deduce that $\sqrt { 3 }$ is not a rational number.

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.

Part A
For all natural integers $n$, we define the integers $a _ { n } = 6 \times 5 ^ { n } - 2$ and $b _ { n } = 3 \times 5 ^ { n } + 1$.

1. a. Show that, for all natural integers $n$, each of the integers $a _ { n }$ and $b _ { n }$ is congruent to 0 modulo 4. b. For all natural integers $n$, calculate $2 b _ { n } - a _ { n }$. c. Determine the GCD of $a _ { n }$ and $b _ { n }$.
2. a. Show that $b _ { 2020 } \equiv 3 \times 2 ^ { 2020 } + 1$ [7]. b. By noting that $2020 = 3 \times 673 + 1$, show that $b _ { 2020 }$ is divisible by 7. c. Is the integer $a _ { 2020 }$ divisible by 7? Justify your answer.

Part B
We consider the sequences $\left( u _ { n } \right)$ and $\left( v _ { n } \right)$ defined by:
$$u _ { 0 } = v _ { 0 } = 1 \text { and, for every natural integer } n , \left\{ \begin{array} { l } u _ { n + 1 } = 3 u _ { n } + 4 v _ { n } \\ v _ { n + 1 } = u _ { n } + 3 v _ { n } \end{array} \right.$$
For a given natural integer $N$, we wish to calculate the terms of rank $N$ of the sequences $(u_n)$ and $(v_n)$ and we wonder if the algorithm below allows this calculation.

\multicolumn{2}{|c|}{Algorithm}
1.	$U \leftarrow 1$
2.	$V \leftarrow 1$
3.	$K \leftarrow 0$
4.	While $K < N$
5.	$U \leftarrow 3 U + 4 V$
6.	$V \leftarrow U + 3 V$
7.	$K \leftarrow K + 1$
8.	End While

1. We run the algorithm with $N = 2$. Copy and complete the table below by giving the values successively assigned to the variables $U, V$ and $K$.
   

   $U$	$V$	$K$
   1	1	0
   7	10	1

   
   
2. Does the algorithm actually allow us to calculate $u _ { N }$ and $v _ { N }$ for a given value of $N$? If not, write on your paper a corrected version of this algorithm so that the variables $U$ and $V$ contain the correct values of $u _ { N }$ and $v _ { N }$ at the end of its execution.

Part C
For every natural integer $n$, we define the column matrix $X _ { n } = \binom { u _ { n } } { v _ { n } }$.

1. Give, without justification, a square matrix $A$ of order 2 such that, for every natural integer $n$: $$X _ { n + 1 } = A X _ { n } .$$
2. Show by induction that, for every natural integer $n$, we have: $X _ { n } = A ^ { n } X _ { 0 }$.
3. We admit that, for every natural integer $n$, $A ^ { n } = \frac { 1 } { 4 } \left( \begin{array} { c c } 2 \times 5 ^ { n } + 2 & 4 \times 5 ^ { n } - 4 \\ 5 ^ { n } - 1 & 2 \times 5 ^ { n } + 2 \end{array} \right)$.
   Show that, for every natural integer $n$, $u _ { n } = \frac { a _ { n } } { 4 }$ and $v _ { n } = \frac { b _ { n } } { 4 }$, where $a _ { n }$ and $b _ { n }$ are the integers defined in Part A.
4. Justify that, for every natural integer $n$, $u _ { n }$ and $v _ { n }$ are coprime.

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

QUESTION 176
The number of prime numbers between 10 and 30 is
(A) 3
(B) 4
(C) 5
(D) 6
(E) 7

Let $f(x) = x^n + a_{n-1} x^{n-1} + \cdots + a_0$ be a polynomial with integer coefficients and whose degree is at least 2. Suppose each $a_i$ ($0 \leq i \leq n-1$) is of the form $$a_i = \pm \frac{17!}{r!(17-r)!}$$ with $1 \leq r \leq 16$. Show that $f(m)$ is not equal to zero for any integer $m$.