Does there exist an integer $n$ such that $21 n \equiv 1[74]$?
We apply the extended Euclidean algorithm:

$$
\begin{array}{r}
74=21 \times 3+11 \\
21=11 \times 1+10 \\
11=10 \times 1+1
\end{array}
$$

21 and 74 are coprime, so we can find $u$ and $v$ such that $21 u + 74 v = 1$. The integer $u$ will then work.

$$
\begin{gathered}
1=11-10 \\
1=11-(21-11)=-21+2 \times 11 \\
1=-21+2 \times(74-21 \times 3)=2 \times 74-7 \times 21
\end{gathered}
$$

Thus, we have: $21 \times (-7) \equiv 1 \pmod{74}$. We say that -7 is an inverse of 21 modulo 74 (don't forget that the class of -7 modulo 74 is the same as the class of 67!).

Proposition 142. If $a$ and $b$ are coprime, then $a$ has an inverse modulo $b$.

## - $p$-adic Valuation -

Definition 143 ($p$-adic Valuation). If $p$ is a prime number, and $n$ is a non-zero integer, the $p$-adic valuation of $n$, denoted $v_{p}(n)$, is the greatest integer $k$ such that $p^{k}$ divides $n$ (we agree that $v_{p}(0)=+\infty$).

If $n$ is non-zero and decomposes as $n=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \ldots p_{k}^{\alpha_{k}}$, then $v_{p_{i}}(n)=\alpha_{i}$ for all $1 \leq i \leq k$, and $v_{p}(n)=0$ if $p$ is different from the $p_{i}$. Thus, $v_{p}(n)=0$ except for a finite number of prime $p$. If $a$ and $b$ are two integers, then for any prime number $p$:

$$
\begin{gathered}
v_{p}(a b)=v_{p}(a)+v_{p}(b) \\
v_{p}(a+b) \geq \min \left(v_{p}(a), v_{p}(b)\right)
\end{gathered}
$$

and the last inequality is an equality whenever $v_{p}(a) \neq v_{p}(b)$.

Example 144. $v_{3}(54)=v_{3}\left(3^{3} \times 2\right)=3$

Theorem 145 (Legendre's Formula). We denote $[x]$ the integer part of the real number $x$. Show that if $p$ is a prime number and $n$ is a positive integer, then

$$
v_{p}(n!)=\sum_{i=1}^{\infty}\left[\frac{n}{p^{i}}\right]=\left[\frac{n}{p}\right]+\left[\frac{n}{p^{2}}\right]+\ldots
$$

When $p^{i}>n$, we have $\left[\frac{n}{p^{i}}\right]=0$. This ensures that there are only a finite number of non-zero terms in the above sum.

Proof. For a non-negative integer $i$, let $n_{i}$ be the number of integers between 1 and $n$ whose $p$-adic valuation is exactly $i$. Then we have:

$$
v_{p}(n!)=n_{1}+2 n_{2}+3 n_{3} \ldots
$$

The integers whose $p$-adic valuation is at least $i$ are the multiples of $p^{i}$, there are $\left[\frac{n}{p^{i}}\right]$ of them between 1 and $n$, that is:

$$
\left[\frac{n}{p^{i}}\right]=n_{i}+n_{i+1}+\ldots
$$

This leads to the result.