Approfondissements de lycée/ES Premiers

Nombres premiers et Arithmétique modulaire[modifier | modifier le wikicode]

Exercices de décomposition[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

$(-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⁹ = 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.
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$
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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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.