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.

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

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.

1. We consider the equation (E) to solve in $\mathbb { Z }$ : $$7 x - 5 y = 1$$ a. Verify that the pair (3; 4) is a solution of (E). b. Show that the pair of integers $( x ; y )$ is a solution of (E) if and only if $7 ( x - 3 ) = 5 ( y - 4 )$. c. Show that the integer solutions of the equation (E) are exactly the pairs ( $x ; y$ ) of relative integers such that: $$\left\{ \begin{array} { l } x = 5 k + 3 \\ y = 7 k + 4 \end{array} \text { where } k \in \mathbb { Z } . \right.$$
2. A box contains 25 tokens, some red, some green and some white. Out of the 25 tokens there are $x$ red tokens and $y$ green tokens. Knowing that $7 x - 5 y = 1$, what can be the numbers of red, green and white tokens?
In the rest, we will assume that there are 3 red tokens and 4 green tokens.
3. We consider the following random walk of a pawn on a triangle $A B C$. At each step, we randomly draw one of the tokens from the 25, then put it back in the box.

• When at A: If the token drawn is red, the pawn goes to B. If the token drawn is green, the pawn goes to C. If the token drawn is white, the pawn stays at A.
• When at B: If the token drawn is red, the pawn goes to A. If the token drawn is green, the pawn goes to C. If the token drawn is white, the pawn stays at B.
• When at C: If the token drawn is red, the pawn goes to A. If the token drawn is green, the pawn goes to B. If the token drawn is white, the pawn stays at C.

Initially, the pawn is on vertex A. For any natural integer $n$, we denote $a _ { n } , b _ { n }$ and $c _ { n }$ the probabilities that the pawn is respectively on vertices $\mathrm { A } , \mathrm { B }$ and C at step $n$. We denote $X _ { n }$ the row matrix $\left( a _ { n } \quad b _ { n } \quad c _ { n } \right)$ and $T$ the matrix $\left( \begin{array} { l l l } 0,72 & 0,12 & 0,16 \\ 0,12 & 0,72 & 0,16 \\ 0,12 & 0,16 & 0,72 \end{array} \right)$. Give the row matrix $X _ { 0 }$ and show that, for any natural integer $n$, $X _ { n + 1 } = X _ { n } T$.
4. We admit that $T = P D P ^ { - 1 }$ where $P ^ { - 1 } = \left( \begin{array} { c c c } \frac { 3 } { 10 } & \frac { 37 } { 110 } & \frac { 4 } { 11 } \\ \frac { 1 } { 10 } & - \frac { 1 } { 10 } & 0 \\ 0 & \frac { 1 } { 11 } & - \frac { 1 } { 11 } \end{array} \right)$ and $D = \left( \begin{array} { c c c } 1 & 0 & 0 \\ 0 & 0,6 & 0 \\ 0 & 0 & 0,56 \end{array} \right)$.

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?

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 following statements, say whether it is true or false by justifying the answer. One point is awarded for each correct justified answer. An unjustified answer will not be taken into account and the absence of an answer is not penalized.

• Consider the system $\left\{ \begin{array} { l l l l } n & \equiv & 1 & { [ 5 ] } \\ n & \equiv & 3 & { [ 4 ] } \end{array} \right.$ with unknown $n$ a relative integer.

Statement 1: If $n$ is a solution of this system then $n - 11$ is divisible by 4 and by 5. Statement 2: For all relative integer $k$, the integer $11 + 20 k$ is a solution of the system. Statement 3: If a relative integer $n$ is a solution of the system then there exists a relative integer $k$ such that $n = 11 + 20 k$.

• An automaton can be in one of two states A or B. At each second it can either remain in the state it is in or change it, with probabilities given by the probabilistic graph below. For all natural number $n$, we denote $a _ { n }$ the probability that the automaton is in state A after $n$ seconds and $b _ { n }$ the probability that the automaton is in state B after $n$ seconds. Initially, the automaton is in state B.

Consider the following algorithm:

\begin{tabular}{l} Variables: Initialization:

Processing:

Output:

&

$a$ and $b$ are real numbers

$a$ takes the value 0

$b$ takes the value 1

For $k$ going from 1 to 10

$a$ takes the value $0.8 a + 0.3 b$

$b$ takes the value $1 - a$

End For

Display $a$

Display $b$

\hline \end{tabular}
Statement 4: On output, this algorithm displays the values of $a _ { 10 }$ and $b _ { 10 }$. Statement 5: After 4 seconds, the automaton has an equal chance of being in state $A$ or being in state $B$.

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

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

Exercise 4 — Candidates who have followed the specialisation course
For each of the following statements, indicate whether it is true or false, by justifying the answer.
One point is awarded for each correct answer that is properly justified. An unjustified answer is not taken into account. No answer is not penalised.
1. Statement 1: The solutions of the equation $7 x - 12 y = 5$, where $x$ and $y$ are relative integers, are the pairs $( - 1 + 12 k ; - 1 + 7 k )$ where $k$ ranges over the set of relative integers.
2. Statement 2: For all natural number $n$, the remainder of the Euclidean division of $4 + 3 \times 15 ^ { n }$ by 3 is equal to 1.
3. Statement 3: The equation $n \left( 2 n ^ { 2 } - 3 n + 5 \right) = 3$, where $n$ is a natural number, has at least one solution.
4. Let $t$ be a real number. We set $A = \left( \begin{array} { c c } t & 3 \\ 2 t & - t \end{array} \right)$.
Statement 4: There is no value of the real number $t$ for which $A ^ { 2 } = \left( \begin{array} { l l } 1 & 0 \\ 0 & 1 \end{array} \right)$.
5. Consider the matrices $A = \left( \begin{array} { c c c } 0 & 1 & - 1 \\ - 1 & 2 & - 1 \\ 1 & - 1 & 2 \end{array} \right)$ and $I _ { 3 } = \left( \begin{array} { l l l } 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array} \right)$.
Statement 5: For all integer $n \geqslant 2 , A ^ { n } = \left( 2 ^ { n } - 1 \right) A + \left( 2 - 2 ^ { n } \right) I _ { 3 }$.

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 176
The number of prime numbers between 10 and 30 is
(A) 3
(B) 4
(C) 5
(D) 6
(E) 7

Find the remainder given by $3 ^ { 89 } \times 7 ^ { 86 }$ when divided by 17.

(a) A computer program prints out all integers from 0 to ten thousand in base 6 using the numerals $0,1,2,3,4$ and 5. How many numerals it would have printed?
(b) A 3-digit number $abc$ in base 6 is equal to the 3-digit number $cba$ in base 9. Find the digits.

A sequence of integers $c _ { n }$ starts with $c _ { 0 } = 0$ and satisfies $c _ { n + 2 } = a c _ { n + 1 } + b c _ { n }$ for $n \geq 0$, where $a$ and $b$ are integers. For any positive integer $k$ with $\operatorname { gcd } ( k , b ) = 1$, show that $c _ { n }$ is divisible by $k$ for infinitely many $n$.

(a) Let $f \in \mathbb { Z } [ x ]$ be a non-constant polynomial with integer coefficients. Show that as $a$ varies over the integers, the set of divisors of $f ( a )$ includes infinitely many different primes.
(b) Assume known the following result: If $G$ is a finite group of order $n$ such that for integer $d > 0$, $d \mid n$, there is no more than one subgroup of $G$ of order $d$, then $G$ is cyclic. Using this (or otherwise) prove that the multiplicative group of units in any finite field is cyclic.

A positive integer $N$ has its first, third and fifth digits equal and its second, fourth and sixth digits equal. In other words, when written in the usual decimal system it has the form $xyxyxy$, where $x$ and $y$ are the digits. Show that $N$ cannot be a perfect power, i.e., $N$ cannot equal $a ^ { b }$, where $a$ and $b$ are positive integers with $b > 1$.

What is the smallest positive integer $n$ for which $\frac { 50 ! } { 24 ^ { n } }$ is not an integer?

(a) Show that there are exactly 2 numbers $a$ in $\{2, 3, \ldots, 9999\}$ for which $a^2 - a$ is divisible by 10000. Find these values of $a$.
(b) Let $n$ be a positive integer. For how many numbers $a$ in $\{2, 3, \ldots, n^2 - 1\}$ is $a^2 - a$ divisible by $n^2$? State your answer suitably in terms of $n$ and justify.