Calculate the sum of the digits of the sum of the digits of the sum of the digits of $A:=4444^{4444}$.
Let $S(n)$ denote the sum of the digits of an integer $n$. Then our trick says that for all $n, S(n) \equiv n[9]$. Thus, $S(S(S(A))) \equiv A[9]$. Let's calculate $A$ modulo 9. We have $4444 \equiv 4+4+4+4 \equiv -2$ [9], so we need to calculate $(-2)^{4444}$ modulo 9. We notice that $(-2)^{3} \equiv 1[9]$. We deduce that $(-2)^{3 k+i} \equiv\left((-2)^{3}\right)^{k} \cdot(-2)^{i} \equiv(-2)^{i}[9]$. In particular, since $4444 \equiv 4+4+4+4 \equiv 1[3]$, then $(-2)^{4444} \equiv(-2) \equiv 7[9]$.

Thus, we know $S(S(S(A)))$ modulo 9. To find its actual value, the idea is that $S(n)$ is generally much smaller than $n$. Thus, $S(S(S(A)))$ is much, much, much smaller than $A$, and with a bit of luck, it will be small enough to determine. We write that $A \leqslant\left(10^{4}\right)^{5000}=10^{20000}$, so $A$ has at most 20000 digits, so
$S(A) \leqslant 20000 \cdot 9 \leqslant 200000$. Thus, $S(S(A)) \leqslant 1+9 \cdot 5=46$, and then $S(S(S(A))) \leqslant 3+9=12$. Since it is 7 modulo 9, it must necessarily be 7.

The second part of the session was devoted to the study of linear equations modulo $n$. We examined the equations $5 x \equiv 10$ [16] and $5 x \equiv 10$ [15]. In each case, we are tempted to "divide by 5". THIS MAKES NO SENSE, AND YOU MUST NOT DO IT. The only operations we are allowed to perform modulo $n$ are addition and multiplication; do not invent other rules like a possible division by 5, as in most cases, it will be wrong.

Let's solve these systems explicitly. For the first one, the equation can be rewritten as $5 x=16 k+10$. In particular, 5 must divide 16k, but since it is coprime with 16, it must divide $k$ by Gauss's lemma: we write $k=5 k^{\prime}$ and then divide by 5, leaving $x=16 k^{\prime}+2$. Conversely, we verify that the $x \equiv 2$ [16] are solutions: in this case, the "division by 5" would have given the correct result.

For the second one, it can be rewritten as $5 x=15 k+10$: we divide by 5 and get $x=3 k+2$. Conversely, the $x \equiv 2$ [3] are solutions. In this case, the "division by 5" would not have worked.

The results 3.1.2 and 3.1.3 of the course specify all of this. In fact, the "division by 5" that we want to perform can be seen as a multiplication by $1 / 5$, and Theorem 3.1.2 precisely states that, in certain cases, we have a notion of an inverse modulo $n$. Thus, 5 has an inverse modulo 16 (for example, -3), so we can multiply the equation $5 x \equiv 10$ [16] by -3, yielding $x \equiv 5 \cdot(-3) \cdot x \equiv 10 \cdot(-3) \equiv 2[16]$. This is the essence of Proposition 3.1.3. On the other hand, 5 does not have an inverse modulo 15 (if you want to prove it, start from the fact that $5 \cdot 3 \equiv 0$ [15]). When we examine the proof of these results, we notice that it is just an application of Bézout's theorem. In particular, if we know a Bézout pair for the integers $c$ and $N$ (i.e., $x$ and $y$ such that $x c+y N=1$), then we know an inverse of $c$ modulo $N: x$. The part 2.3 of the course is therefore fundamental: it explains how, from the Euclidean division, we can construct Bézout pairs. Thus, we have a very practical algorithm for determining inverses modulo $N$.

I then moved on to systems of several equations, giving the example of the system $\left\{\begin{array}{l}x \equiv 5[7] \\ x \equiv 8[11]\end{array}\right.$. We can solve this system explicitly, so the first equation allows us to write $x$ in the form $7 k+5$, and then we need $7 k+5 \equiv 8$ [11], i.e., $7 k \equiv 3[11]$ and then $k \equiv 2[11]$ by multiplying by the inverse 8 of 7 modulo 11. Thus, $k$ is of the form $11 k^{\prime}+2$, and then $x$ is of the form $7(11 k^{\prime}+2)+5$, i.e., $77 k^{\prime}+19$. Conversely, these numbers are indeed solutions.

In fact, a theorem, called the Chinese theorem, 3.4.1 in the course, states that this kind of method is very general: if $m$ and $n$ are two coprime numbers, if $u m+v n=1$ is a Bézout relation between these two integers, then the solutions of the system $\left\{\begin{array}{l}x \equiv a[m] \\ x \equiv b[n]\end{array}\right.$ are exactly the numbers congruent to $s:=u m b+v n a$ modulo $m n$. Indeed, this number is clearly a solution (note that $u m \equiv 1[n]$, which is the meaning of the Bézout relation), and if $x$ is another solution, then $m$ and $n$ divide $x-s$, so their product divides $x-s$ (since $m$ and $n$ are coprime), so $x \equiv s[m n]$. Note again the great usefulness of the Euclidean algorithm: it allows us to find the Bézout coefficients, and thus to solve such systems of equations directly.

## 3 Arithmetic TD

## - Exercise statements -