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)

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$

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$

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

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. $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⁹ = 6 et 2¹⁰ = 1, nous pouvons calculer 6² facilement : 6² = 2¹⁸ = 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.
4. 0² = 0, 1² = 1, 2² = 4, 3² = 9,
   4² = 16 = 5, 5² = 25 = 5, 6² = 36 = 3, 7² = 49 = 3,
   8² = 64 = 5, 9² = 81 = 4, 10² = 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. x² = -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.

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

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.