Approfondissements de lycée/ES Premiers

Un livre de Wikibooks.

Sections

[modifier] Nombres premiers et Arithmétique modulaire

[modifier] Exercices de décomposition

Décomposer les nombres suivants. (note : ceci est juste pour ceux qui sont curieux)

  1. 13 est premier
  2. 26 = 13 \cdot 2
  3. 59 est premier
  4. 82 = 41 \cdot 2
  5. 101 est premier
  6. 121 = 11 \cdot 11
  7. 2187 = 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3

[modifier] Exercice de décomposition récursive

Décomposer en utilisant la récursivité.

  1. 45 = 3 \cdot 3 \cdot 5
  2. 4050 = 2 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 5 \cdot 5
  3. 2187 = 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3

[modifier] Exercices sur le crible de nombres premiers

  1. 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

[modifier] Exercices d'arithmétique modulaire

  1. (-1) \cdot (-5)\mod{11} = 5 de manière alternative, -1 = 10, -5 = 6: 10 x 6 = 60 = 5 x 11 + 5 = 5
  2. 3 \cdot 7 \mod{11} = 21 = 10
  3. 21 = 2,22 = 4,23 = 8,24 = 16 = 5
    25 = 32 = 10,26 = 64 = 9,27 = 128 = 7
    28 = 256 = 3,29 = 512 = 6,210 = 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
    210 pour trouver 210 mod 11.
    Si vous connaissez 29 mod 11 = 6.
    Vous pouvez trouver 210 mod 11 = (2*(29 mod 11)) mod 11 = 2*6 mod 11 = 12 mod 11 = 1.
    Nous pouvons noter que 29 = 6 et 210 = 1, nous pouvons calculer 62 facilement : 62 = 218 = 2^8 = 3. Ou par la méthode précédente
    61 = 6,62 = 36 = 3,63 = 6 * 3 = 18 = 7,
    64 = 6 * 7 = 42 = 9,65 = 6 * 9 = 54 = 10,66 = 6 * 10 = 60 = 5,
    67 = 6 * 5 = 30 = 8,68 = 6 * 8 = 48 = 4,69 = 6 * 4 = 24 = 2,610 = 6 * 2 = 12 = 1.
    Une liste plus facile : 6, 3, 7, 9, 10, 5, 8, 4, 2, 1.
  4. 02 = 0, 12 = 1, 22 = 4, 32 = 9,
    42 = 16 = 5, 52 = 25 = 5, 62 = 36 = 3, 72 = 49 = 3,
    82 = 64 = 5, 92 = 81 = 4, 102 = 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
  5. x2 = -2 = 9
    Regardez simplement la liste ci-dessus et vous verrez que \sqrt{-2}=8\mbox{ et }\sqrt{-2}=3

[modifier] 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.

0 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

[modifier] 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.
Récupérée de « http://fr.wikibooks.org/wiki/Approfondissements_de_lyc%C3%A9e/ES_Premiers »