# Approfondissements de lycée/ES Premiers
## Nombres premiers et Arithmétique modulaire
### Exercices de décomposition

Décomposer les nombres suivants. (note : ceci est juste pour ceux qui sont curieux)
* 13 est premier
* $26=13\cdot 2$
* 59 est premier
* $82=41\cdot 2$
* 101 est premier
* $121=11\cdot 11$
* $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

### Exercice de décomposition récursive

Décomposer en utilisant la récursivité.
* $45=3\cdot 3\cdot 5$
* $4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5$
* $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

### Exercices sur le crible de nombres premiers

* Utiliser le résultat ci-dessus pour éliminier rapidement les nombres qui doivent encore être rayés dans la table ci-dessous, sachant que 5 est le prochain nombre premier :
    ${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$
    Le nombre premier suivant est 5. Parceque 5 est un nombre premier non marqué, et que 5 * 5 = 25, rayer 25. De même, 7 est un nombre premier non marqué, et 5 * 7 = 35, donc éliminer 35. Néanmoins, 5 * 11 = 55, est trop haut, donc marquer 5 comme premier et passer à 7. Le seul nombre suffisamment bas pour être enlevé est 7 * 7, qui est égal à 49. Vous ne pouvez pas aller plus haut.
2. Trouver tous les nombres premiers inférieurs à 200.
    La méthode précédente est trop longue. Tous les nombres premiers inférieurs à 200 sont :
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

### Exercices d'arithmétique modulaire

* $(-1)\cdot (-5)\mod {11}=5$ de manière alternative, -1 = 10, -5 = 6: 10 x 6 = 60 = 5 x 11 + 5 = 5
* $3\cdot 7\mod {11}=21=10$
* $2^{1}=2,2^{2}=4,2^{3}=8,2^{4}=16=5$ $2^{5}=32=10,2^{6}=64=9,2^{7}=128=7$ $2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1$ Une liste plus facile : 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 Noter qu'il n'est pas nécessaire de calculer $2^{10}$ pour trouver $2^{10}$ mod 11. Si vous connaissez $2^{9}$ mod 11 = 6. Vous pouvez trouver $2^{10}$ mod 11 = (2*($2^{9}$ mod 11)) mod 11 = 2*6 mod 11 = 12 mod 11 = 1. Nous pouvons noter que 2$^9$ = 6 et 2$^{10}$ = 1, nous pouvons calculer 6$^2$ facilement : 6$^2$ = 2$^{18}$ = 2^8 = 3. Ou par la méthode précédente $6^{1}=6,6^{2}=36=3,6^{3}=6*3=18=7,$ $6^{4}=6*7=42=9,6^{5}=6*9=54=10,6^{6}=6*10=60=5,$ $6^{7}=6*5=30=8,6^{8}=6*8=48=4,6^{9}=6*4=24=2,6^{10}=6*2=12=1.$ Une liste plus facile : 6, 3, 7, 9, 10, 5, 8, 4, 2, 1.
* 0$^2$ = 0, 1$^2$ = 1, 2$^2$ = 4, 3$^2$ = 9, 4$^2$ = 16 = 5, 5$^2$ = 25 = 5, 6$^2$ = 36 = 3, 7$^2$ = 49 = 3, 8$^2$ = 64 = 5, 9$^2$ = 81 = 4, 10$^2$ = 100 = 1 Une liste plus facile : 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 Ainsi${\sqrt {4}}=2{\mbox{ and }}{\sqrt {4}}=9$
* x$^2$ = -2 = 9 Regardez simplement la liste ci-dessus et vous verrez que ${\sqrt {-2}}=8{\mbox{ et }}{\sqrt {-2}}=3$

### Exercices sur la division et les inverses

1.
    $x=2^{-1}=4$
    $x=3^{-1}=5$
    $x=4^{-1}=2$
    $x=5^{-1}=3$
    $x=6^{-1}=6$
    $x=7^{-1}=0^{-1}$ Par conséquent, l'inverse n'existe pas
2. $x={\frac {28}{7}}=4\ \ {\mbox{(mod 29)}}$
    $7^{-1}=25\ \ {\mbox{(mod 29)}}$
    $x=28\cdot 25=4\ \ {\mbox{(mod 29)}}$
3.
    $x=5^{99}\times (40+{\frac {1}{3}})\ \ {\mbox{(mod 11)}}$
    $x=5^{99}\times (40+4)\ \ {\mbox{(mod 11)}}$
    $x=5^{99}\times 0\ \ {\mbox{(mod 11)}}$
    $x=0\ \ {\mbox{(mod 11)}}$
4.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| 1 | | | | | | | | | | | | | | | | | | mod 2 |
| 1 | 2 | | | | | | | | | | | | | | | | | mod 3 |
| 1 | | 3 | | | | | | | | | | | | | | | | mod 4 |
| 1 | 3 | 2 | 4 | | | | | | | | | | | | | | | mod 5 |
| 1 | | | | 5 | | | | | | | | | | | | | | mod 6 |
| 1 | 4 | 5 | 2 | 3 | 6 | | | | | | | | | | | | | mod 7 |
| 1 | | 3 | | 5 | | 7 | | | | | | | | | | | | mod 8 |
| 1 | 5 | | 7 | 2 | | 4 | 8 | | | | | | | | | | | mod 9 |
| 1 | | 7 | | | | 3 | | 9 | | | | | | | | | | mod 10 |
| 1 | 6 | 4 | 3 | 9 | 2 | 8 | 7 | 5 | 10 | | | | | | | | | mod 11 |
| 1 | | | | 5 | | 7 | | | | 11 | | | | | | | | mod 12 |
| 1 | 7 | 9 | 10 | 8 | 11 | 2 | 5 | 3 | 4 | 6 | 12 | | | | | | | mod 13 |
| 1 | | 5 | | 3 | | | | 11 | | 9 | | 13 | | | | | | mod 14 |
| 1 | 8 | | 4 | | | 13 | 2 | | | 11 | | 7 | 14 | | | | | mod 15 |
| 1 | | 11 | | 13 | | 7 | | 9 | | 3 | | 5 | | 15 | | | | mod 16 |
| 1 | 9 | 6 | 13 | 7 | 3 | 5 | 15 | 2 | 12 | 14 | 10 | 4 | 11 | 8 | 16 | | | mod 17 |
| 1 | | | | 11 | | 13 | | | | 5 | | 7 | | | | 17 | | mod 18 |
| 1 | 10 | 13 | 5 | 4 | 16 | 11 | 12 | 17 | 2 | 7 | 8 | 3 | 15 | 14 | 6 | 9 | 18 | mod 19 |

### Exercices sur les nombres premiers entre eux et PGDC

1.
    1.
| Plus petit | Plus grand |
| 5050 | 5051 |
| 1 | 5050 |
| 0 | 1 |
       5050 et 5051 sont premiers entre eux
    2.
| Plus petit | Plus grand |
| 59 | 78 |
| 19 | 59 |
| 2 | 19 |
| 1 | 2 |
| 0 | 1 |
       59 et 79 sont premiers entre eux
    3.
| Plus petit | Plus grand |
| 111 | 369 |
| 36 | 111 |
| 3 | 36 |
| 0 | 3 |
       111 et 369 ne sont pas premiers entre eux
    4.
| Plus petit | Plus grand |
| 2021 | 4032 |
| 2011 | 2021 |
| 10 | 2011 |
| 1 | 10 |
| 0 | 1 |
       2021 et 4032 sont premiers entre eux
2.Nous calculerons d'abord le PGDC pour toutes les combinaisons
| Plus petit | Plus grand |
| 15 | 510 |
| 0 | 15 |
| Plus petit | Plus grand |
| 15 | 375 |
| 0 | 15 |
| Plus petit | Plus grand |
| 375 | 510 |
| 135 | 375 |
| 105 | 135 |
| 30 | 105 |
| 15 | 30 |
| 0 | 15 |
    Le PGDC pour toute combinaison des nombres est 15 donc le PGDC est 15 pour les trois nombres.