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

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

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.

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

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

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]

6. a. For $q \in \mathbb{N}$, we set $S_q = \sum_{\ell=0}^{p-1} \ell^q$. Observe that $p$ divides $\sum_{\ell=0}^{p-1} ((\ell+1)^{q+1} - \ell^{q+1})$ and deduce by recursion that $p$ divides $S_q$ for $0 \leq q \leq p-2$. b. Let $Z = [z_{ij}]$ and $Z' = [z'_{ij}]$ be two square matrices of order $N$ with entries in $\mathbb{Z}$. We define the relation $Z \equiv Z'[p]$ by $z_{ij} \equiv z'_{ij}[p]$ for $1 \leq i, j \leq N$. Prove that $$(M_{p-1})^{(p-1)} \equiv (-1)^{(p-1)/2} \mathrm{Id} \quad [p].$$ c. What can be said about a polynomial $Q$ with integer coefficients such that $Q(M_{p-1}) \equiv 0[p]$?

If $n \in \mathbb{N}^*$, we denote, for $i \in \{0,1,2,3\}$, $$r_i(n) = \operatorname{Card}\{d \in \mathbb{N} : d \equiv i [4] \text{ and } d \mid n\}$$ We set $g(n) = r_1(n) - r_3(n)$.
Show that, for all $n \in \mathbb{N}$, and all prime number $p$, we have $$g\left(p^n\right) = \begin{cases} 1 & \text{if } p = 2 \\ n+1 & \text{if } p \equiv 1 [4] \\ \frac{1}{2}\left(1+(-1)^n\right) & \text{if } p \equiv 3 [4] \end{cases}$$

Let $d$ be a nonzero integer and $u$ be an integer. Show that the sum $$\sum_{k\in\mathbb{Z}/d\mathbb{Z}} e^{\frac{2i\pi}{d}ku}$$ equals $d$ if $u\equiv 0\bmod d$ and $0$ otherwise.

Let $(u,v)\in\mathbb{Z}^2\setminus(0,0)$. Let $p$ be a prime number congruent to 1 modulo 4 and $\alpha\geq 2$. Show that $L(u,v,p^\alpha)=0$ as soon as $p^{\alpha-1}$ does not divide $u^2+v^2$. Deduce that if $\alpha\geq 3$, then $L_{\mathrm{prim}}(u,v,p^\alpha)=0$ as soon as $p^{\alpha-2}$ does not divide $u^2+v^2$.

$N$ is a 50 digit number. All the digits except the 26th from the right are 1. If $N$ is divisible by 13, then the unknown digit is
(A) 1
(B) 3
(C) 7
(D) 9

$N$ is a 50 digit number. All the digits except the 26th from the right are 1. If $N$ is divisible by 13, then the unknown digit is
(A) 1
(B) 3
(C) 7
(D) 9

$N$ is a 50 digit number. All the digits except the 26th from the right are 1. If $N$ is divisible by 13, then the unknown digit is
(A) 1
(B) 3
(C) 7
(D) 9

Let $a \geq b \geq c \geq 0$ be integers such that $2 ^ { a } + 2 ^ { b } - 2 ^ { c } = 144$. Then, $a + b - c$ equals:
(A) 7
(B) 8
(C) 9
(D) 10 .

Suppose the numbers 71, 104 and 159 leave the same remainder $r$ when divided by a certain number $N > 1$. Then, the value of $3 N + 4 r$ must equal:
(A) 53
(B) 48
(C) 37
(D) 23

The number of positive integers $n$ less than or equal to 22 such that 7 divides $n ^ { 5 } + 4 n ^ { 4 } + 3 n ^ { 3 } + 2022$ is
(A) 7
(B) 8
(C) 9
(D) 10

Suppose $x$ and $y$ are positive integers. If $4 x + 3 y$ and $2 x + 4 y$ are divided by 7, then the respective remainders are 2 and 5. If $11 x + 5 y$ is divided by 7, then the remainder equals
(A) 0.
(B) 1.
(C) 2.
(D) 3.

Let $N$ be a 50 digit number. All the digits except the 26th one from the right are 1. If $N$ is divisible by 13, then the unknown digit is
(a) 1 .
(B) 3 .
(C) 7 .
(D) 9 .

If $(27)^{999}$ is divided by 7, then the remainder is
(1) 3
(2) 1
(3) 6
(4) 2

Let $A = \{ n \in N : n$ is a 3-digit number $\}$, $B = \{ 9 k + 2 : k \in N \}$ and $C = \{ 9 k + l : k \in N \}$ for some $l ( 0 < l < 9 )$. If the sum of all the elements of the set $A \cap ( B \cup C )$ is $274 \times 400$, then $l$ is equal to

The total number of two digit numbers $n$, such that $3 ^ { n } + 7 ^ { n }$ is a multiple of 10, is $\underline{\hspace{1cm}}$.

If the remainder when $x$ is divided by 4 is 3, then the remainder when $( 2020 + x ) ^ { 2022 }$ is divided by 8 is $\underline{\hspace{1cm}}$.