Un livre de Wikilivres.
Décomposer les nombres suivants. (note : ceci est juste pour ceux qui sont curieux)
13 est premier
26
=
13
⋅
2
{\displaystyle 26=13\cdot 2}
59 est premier
82
=
41
⋅
2
{\displaystyle 82=41\cdot 2}
101 est premier
121
=
11
⋅
11
{\displaystyle 121=11\cdot 11}
2187
=
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
{\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}
Décomposer en utilisant la récursivité.
45
=
3
⋅
3
⋅
5
{\displaystyle 45=3\cdot 3\cdot 5}
4050
=
2
⋅
3
⋅
3
⋅
3
⋅
3
⋅
5
⋅
5
{\displaystyle 4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5}
2187
=
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
⋅
3
{\displaystyle 2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3}
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 :
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
{\displaystyle {\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
(
−
1
)
⋅
(
−
5
)
mod
11
=
5
{\displaystyle (-1)\cdot (-5)\mod {11}=5}
de manière alternative, -1 = 10, -5 = 6: 10 x 6 = 60 = 5 x 11 + 5 = 5
3
⋅
7
mod
11
=
21
=
10
{\displaystyle 3\cdot 7\mod {11}=21=10}
2
1
=
2
,
2
2
=
4
,
2
3
=
8
,
2
4
=
16
=
5
{\displaystyle 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
{\displaystyle 2^{5}=32=10,2^{6}=64=9,2^{7}=128=7}
2
8
=
256
=
3
,
2
9
=
512
=
6
,
2
10
=
1024
=
1
{\displaystyle 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
{\displaystyle 2^{10}}
pour trouver
2
10
{\displaystyle 2^{10}}
mod 11. Si vous connaissez
2
9
{\displaystyle 2^{9}}
mod 11 = 6. Vous pouvez trouver
2
10
{\displaystyle 2^{10}}
mod 11 = (2*(
2
9
{\displaystyle 2^{9}}
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
6
1
=
6
,
6
2
=
36
=
3
,
6
3
=
6
∗
3
=
18
=
7
,
{\displaystyle 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
,
{\displaystyle 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.
{\displaystyle 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.
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
4
=
2
and
4
=
9
{\displaystyle {\sqrt {4}}=2{\mbox{ and }}{\sqrt {4}}=9}
x2 = -2 = 9 Regardez simplement la liste ci-dessus et vous verrez que
−
2
=
8
et
−
2
=
3
{\displaystyle {\sqrt {-2}}=8{\mbox{ et }}{\sqrt {-2}}=3}
1.
x
=
2
−
1
=
4
{\displaystyle x=2^{-1}=4}
x
=
3
−
1
=
5
{\displaystyle x=3^{-1}=5}
x
=
4
−
1
=
2
{\displaystyle x=4^{-1}=2}
x
=
5
−
1
=
3
{\displaystyle x=5^{-1}=3}
x
=
6
−
1
=
6
{\displaystyle x=6^{-1}=6}
x
=
7
−
1
=
0
−
1
{\displaystyle x=7^{-1}=0^{-1}}
Par conséquent, l'inverse n'existe pas
2.
x
=
28
7
=
4
(mod 29)
{\displaystyle x={\frac {28}{7}}=4\ \ {\mbox{(mod 29)}}}
7
−
1
=
25
(mod 29)
{\displaystyle 7^{-1}=25\ \ {\mbox{(mod 29)}}}
x
=
28
⋅
25
=
4
(mod 29)
{\displaystyle x=28\cdot 25=4\ \ {\mbox{(mod 29)}}}
3.
x
=
5
99
×
(
40
+
1
3
)
(mod 11)
{\displaystyle x=5^{99}\times (40+{\frac {1}{3}})\ \ {\mbox{(mod 11)}}}
x
=
5
99
×
(
40
+
4
)
(mod 11)
{\displaystyle x=5^{99}\times (40+4)\ \ {\mbox{(mod 11)}}}
x
=
5
99
×
0
(mod 11)
{\displaystyle x=5^{99}\times 0\ \ {\mbox{(mod 11)}}}
x
=
0
(mod 11)
{\displaystyle 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.
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.