{%hackmd theme-dark %}
# CHIFF-TD1

## Exercice 1
### 1. GCD(315,540):
On commence par appliquer la division euclidienne :
$$
540 = 315 \times 1 + 225 \\
315 = 225 \times 1 + 90 \\
225 = 90 \times 2 + 45 \\
90 = 45 \times 2 + 45
$$
Le PGCD entre 315 et 540 est 45.
#### Bonus : coefficient de Bezout de (315, 540):
$$
\begin{align}
45 &= 225 - 90 \times 2 \\
45 &= 225 - (315 - 225) \times 2 \\
45 &= 225 \times 3 - 315 \times 2 \\
45 &= (540 - 315) \times 3 - 315 \times 2 \\
45 &= 540 \times 3 - 315 \times 5
\end {align}
$$
On a donc $u = 3$ et $v = -5$.
### 2. Coefficient de Bezout de (122, 246):
On commence par calculer le PGCD de (122,246)
$$
246 = 122 \times 2 + 2 \\
122 = 2 \times 61 + 0
$$
Donc PGCD(122, 246) = 2
On utilise l'algorithme de d'Euclide :
$$
2 = 246 - 122 \times 2
$$
On a donc $u = 1$ et $v = -2$.
### 3. $99^{-1} = 101$
La notation est trompeuse le -1 signifie inverse modulaire, soit $x$ l'inverse modulaire de $99$.
$$
99\times x \equiv 1 [100] \\
99 \times x - 1 = 100k \\
99x = 1 + 100k
$$
Pour $k = 1$ on a bien $99^{-1} = 101$.

## Exercice 2
### 1.
Avec le théorème des restes chinois associé à un modulo unique M, on a :
$$
x = a_1M_1y_1 + ... + a_nM_ny_n
$$
On trouve l'unique solution modulo du système d'equation M :
$$
M = 25 \times 26 \times 27 \\
M = 17550
$$
On cherche ensuite les $M_i$ associé.
$$
M_1 = M / m_1 \\
M_1 = 17550 / 25 = 702\\
M_2 = 17550 / 26 = 675 \\
M_3 = 17550 / 27 = 650 \\
$$
On trouve ensuite les inverse modulaire grace à l'algorithme d'Euclide:
$$
y_1 = 13 \\
y_2 = 25 \\
y_3 = 14 \\
$$
On applique ensuite le théorème :
$$
x = 12 \times 702 \times 13 + 9 \times 675 \times 25 + 23 \times 650 \times 14 \\
x = 470 687 [17550] \\
x = 14387 \\
$$

# CHIFF-TD2
## Exercice 1

| x | $f(x)$ | $x^2$ | Solution |
| --- | ------ | ----- | ---------------²'t YAQZISOETP89RYU%¨M' |
| 0 | 6 | 0 | N |
| 1 | 8 | 1 | N |
| 2 | 5 | 4 | (2, 4), (2, 7) |
| 3 | 3 | 9 | (3, 5), (3,6) |
| 4 | 8 | 5 | N |
| 5 | 4 | 3 | (5, 2), (5, 9) |
| 6 | 9 | 9 | N |
| 7 | 4 | 5 | (7,2), (7, 9) |
| 8 | 9 | 9 | (8,5), (8, 8) |
| 9 | 7 | 4 | N |
| 10 | 4 | 1 | (10, 2), (10, 9)|
Methode : regarder la colone $f(x)$ et voir si dans la colone $x^2$ s'il y a le même nombre. Si oui, constituer les paires (x,x).