---
# System prepended metadata

title: CHIFF-TD1

---

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