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

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.

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.

Let $a _ { 1 } , a _ { 2 } , \ldots , a _ { 100 }$ be 100 positive integers. Show that for some $m , n$ with $1 \leq m \leq n \leq 100 , \sum _ { i = m } ^ { n } a _ { i }$ is divisible by 100.

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

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

Each integer is colored with exactly one of three possible colors - black, red or white satisfying the following two rules: the negative of a black number must be colored white, and the sum of two white numbers (not necessarily distinct) must be colored black.
(a) Show that the negative of a white number must be colored black and the sum of two black numbers must be colored white.
(b) Determine all possible colorings of the integers that satisfy these rules.

Let $|\cdot| : \mathbb{R} \longrightarrow \mathbb{R}_{\geq 0}$ be a function such that for every $x, y \in \mathbb{R}$, (i) $|x| = 0$ if and only if $x = 0$; (ii) $|x + y| \leq |x| + |y|$; (iii) $|xy| = |x||y|$. Show that the following are equivalent:
(A) The set $\{|n| : n \in \mathbb{Z}\}$ is bounded;
(B) $|x + y| \leq \max\{|x|, |y|\}$ for every $x, y \in \mathbb{R}$.

A prime $p$ is an integer $\geq 2$ whose only positive integer factors are 1 and $p$.
(a) For any prime $p$ the number $p ^ { 2 } - p$ is always divisible by 3.
(b) For any prime $p > 3$ exactly one of the numbers $p - 1$ and $p + 1$ is divisible by 6.
(c) For any prime $p > 3$ the number $p ^ { 2 } - 1$ is divisible by 24.
(d) For any prime $p > 3$ one of the three numbers $p + 1 , p + 3$ and $p + 5$ is divisible by 8.

[15 points] Solve the following. You may do (i) and (ii) in either order.
(i) Let $p$ be a prime number. Show that $x^2 + x - 1$ has at most two roots modulo $p$, i.e., the cardinality of $\{n \mid 1 \leq n \leq p$ and $n^2 + n - 1$ is divisible by $p\}$ is $\leq 2$. Find all primes $p$ for which this set has cardinality 1.
(ii) Find all positive integers $n \leq 121$ such that $n^2 + n - 1$ is divisible by 121.
(iii) What can you say about the number of roots of $x^2 + x - 1$ modulo $p^2$ for an arbitrary prime $p$, i.e., the cardinality of
$$\left\{n \mid 1 \leq n \leq p^2 \text{ and } n^2 + n - 1 \text{ is divisible by } p^2\right\}?$$
You do NOT need to repeat any reasoning from previous parts. You may simply refer to any such relevant reasoning and state your conclusion with a brief explanation.

Statements
(25) To divide an integer $b$ by a nonzero integer $d$, define a quotient $q$ and a remainder $r$ to be integers such that $b = q d + r$ and $| r | < | d |$. Such integers $q$ and $r$ always exist and are both unique for given $b$ and $d$. (26) To divide a polynomial $b ( x )$ by a nonzero polynomial $d ( x )$, define a quotient $q ( x )$ and a remainder $r ( x )$ to be polynomials such that $b = q d + r$ and $\deg ( r ) < \deg ( d )$. (Here $b ( x )$ and $d ( x )$ have real coefficients and the 0 polynomial is taken to have negative degree by convention.) Such polynomials $q ( x )$ and $r ( x )$ always exist and are both unique for given $b ( x )$ and $d ( x )$. (27) Suppose that in the preceding question $b ( x )$ and $d ( x )$ have rational coefficients. Then $q ( x )$ and $r ( x )$, if they exist, must also have rational coefficients. (28) The least positive number in the set $$\left\{ \left( a \times 2023 ^ { 2020 } \right) + \left( b \times 2020 ^ { 2023 } \right) \right\}$$ as $a$ and $b$ range over all integers is 3.

We want to find odd integers $n > 1$ for which $n$ is a factor of $2023 ^ { n } - 1$.
(a) Find the two smallest such integers.
(b) Prove that there are infinitely many such integers.

The purpose of this question is to show that $\sqrt { 3 }$ is not an eigenvalue of a matrix in $S _ { 2 } ( \mathbb { Q } )$. We assume that there exists $M \in S _ { 2 } ( \mathbb { Q } )$ such that $\sqrt { 3 }$ is an eigenvalue of $M$.
2a. Using the irrationality of $\sqrt { 3 }$, show that the characteristic polynomial of $M$ is $X ^ { 2 } - 3$.
2b. Show that if $n \in \mathbb { Z }$, then $n ^ { 2 }$ is congruent to 0 or 1 modulo 3.
2c. Show that there does not exist a triple of integers $(x, y, z)$ that are coprime as a whole such that $x ^ { 2 } + y ^ { 2 } = 3 z ^ { 2 }$.
2d. Conclude.

The purpose of this question is to show that $\sqrt { 3 }$ is not an eigenvalue of a matrix in $S _ { 2 } ( \mathbb { Q } )$. We assume that there exists $M \in S _ { 2 } ( \mathbb { Q } )$ such that $\sqrt { 3 }$ is an eigenvalue of $M$.
2a. Using the irrationality of $\sqrt { 3 }$, show that the characteristic polynomial of $M$ is $X ^ { 2 } - 3$.
2b. Show that if $n \in \mathbb { Z }$, then $n ^ { 2 }$ is congruent to 0 or 1 modulo 3.
2c. Show that there does not exist a triple of integers $( x , y , z )$ that are coprime as a whole such that $x ^ { 2 } + y ^ { 2 } = 3 z ^ { 2 }$.
2d. Conclude.

Let $p$ be a prime number. Show that there exists $h\in\mathbb{Z}/p\mathbb{Z}$ such that $h^2=-1$ if and only if $p=2$ or $p\equiv 1\bmod 4$.

Assume that $p$ is a prime number congruent to 1 modulo 4. Show that $(a,b)\in S(p)$ if and only if $$b = ha \quad \text{or} \quad b = -ha$$ where $h$ is a solution of $h^2=-1\bmod p$.

Assume that $p$ is a prime number congruent to 1 modulo 4. Let $\alpha\geq 1$. Show that there exists $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$.

Assume that $p$ is a prime number congruent to 1 modulo 4, and fix $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$. Let $a\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $p$ does not divide $a$. Show that $(a,b)\in S(p^\alpha)$ if and only if $$b = ja \quad \text{or} \quad b = -ja.$$

Assume that $p$ is a prime number congruent to 1 modulo 4, and fix $j\in\mathbb{Z}/p^\alpha\mathbb{Z}$ such that $j^2=-1$. Let $a\in\mathbb{Z}/p^\alpha\mathbb{Z}$ and $k\leq\alpha$ be the largest integer such that $p^k$ divides $a$. Show that if $k<\frac{\alpha}{2}$, then $(a,b)\in S(p^\alpha)$ if and only if $$b\equiv\pm ja\bmod p^{\alpha-k}$$ and that if $k\geq\frac{\alpha}{2}$, then $(a,b)\in S(p^\alpha)$ if and only if $p^{\lceil\frac{\alpha}{2}\rceil}$ divides $b$.

Let $a, b, c$ be positive integers with $a^2 + b^2 = c^2$. Which of the following must be true?
(A) 3 divides exactly one of $a, b$ (B) 3 divides $c$ (C) $3^3$ divides $abc$ (D) $3^4$ divides $abc$

Let the sequence $\left\{ a _ { n } \right\} _ { n \geq 1 }$ be defined by
$$a _ { n } = \tan ( n \theta )$$
where $\tan ( \theta ) = 2$. Show that for all $n , a _ { n }$ is a rational number which can be written with an odd denominator.

Let $a , b , c \in \mathbb { N }$ be such that $$a ^ { 2 } + b ^ { 2 } = c ^ { 2 } \text { and } c - b = 1$$ Prove that ( i ) $a$ is odd, ( ii ) $b$ is divisible by 4 ,
(iii) $a ^ { b } + b ^ { a }$ is divisible by $c$.

A particle is allowed to move in the $XY$-plane by choosing any one of the two jumps:

1. move two units to right and one unit up, i.e., $( a , b ) \mapsto ( a + 2 , b + 1 )$ or
2. move two units up and one unit to right, i.e., $( a , b ) \mapsto ( a + 1 , b + 2 )$.

Let $P = ( 30,63 )$ and $Q = ( 100,100 )$. If the particle starts at the origin, then
(A) $P$ is reachable but not $Q$.
(B) $Q$ is reachable but not $P$.
(C) both $P$ and $Q$ are reachable.
(D) neither $P$ nor $Q$ is reachable.

Prove that the positive integers $n$ that cannot be written as a sum of $r$ consecutive positive integers, with $r > 1$, are of the form $n = 2^{l}$ for some $l \geq 0$.