Pseudo-premier

Pseudo-premier: Nombre pseudopremier

Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n'est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la propriété qu'ils satisfont.

La plus importante classe de nombres pseudopremiers provient du petit théorème de Fermat et donc, sont appelés les pseudopremiers de Fermat. Ce théorème énonce que si p est premier et a est premier avec p, alors a^p-1 - 1 est divisible par p. Si un nombre x n'est pas premier, a est premier avec x et x divise a^x-1 - 1, alors x est appelé un pseudopremier de base a. Un nombre x pseudopremier pour toutes les valeurs de a qui sont premières avec x est appelé nombre de Carmichael.

Le plus petit nombre pseudopremier de Fermat pour la base 2 est 341. Il n'est pas premier, car il est égal à 11 · 31, mais il satisfait le petit théorème de Fermat : 2³⁴¹=2 (mod 341).

Il existe des applications en cryptographie asymétrique telles que RSA qui ont besoin de grands nombres premiers. L'algorithme commun pour générer les nombres premiers consiste en plusieurs générations de nombres aléatoires impairs et des tests concernant leur primalité. Néanmoins, les tests de primalité déterministes sont lents. Si l'utilisateur ne requiert pas que le test soit complètement exact (autrement dit, il devrait tolérer une très petite chance qu'un nombre composé soit déclaré premier), il existe des algorithmes rapides comme le test de primalité de Fermat, le test de primalité de Solovay-Strassen, et le test de primalité de Miller-Rabin.

Il existe une infinité de nombres pseudopremiers (même une infinité de nombres de Carmichael), mais ils sont plutôt rares. Il existe seulement 3 pseudopremiers de base 2 inférieurs à 1 000 et 245 inférieurs à un million. Les pseudopremiers de base 2 sont appelés nombres de Poulet ou quelquefois les nombres de Sarrus ou fermatiens (suite dans A001567 encyclopédie électronique des suites entières). Les nombres de Poulet et les nombres de Carmichael (en gras) balayés jusqu'à 41 041 sont :

n n n n n

1 341 = 11 · 31 11 2 821 = 7 · 13 · 31 21 8 481 = 3 · 11 · 257 31 15 709 = 23 · 683 41 30 121 = 7 · 13 · 331

2 561 = 3 · 11 · 17 12 3 277 = 29 · 113 22 8 911 = 7 · 19 · 67 32 15 841 = 7 · 31 · 73 42 30 889 = 17 · 23 · 79

3 645 = 3 · 5 · 43 13 4 033 = 37 · 109 23 10 261 = 31 · 331 33 16 705 = 5 · 13 · 257 43 31 417 = 89 · 353

4 1 105 = 5 · 13 · 17 14 4 369 = 17 · 257 24 10 585 = 5 · 29 · 73 34 18 705 = 3 · 5 · 29 · 43 44 31 609 = 73 · 433

5 1 387 = 19 · 73 15 4 371 = 3 · 31 · 47 25 11 305 = 5 · 7 · 17 · 19 35 18 721 = 97 · 193 45 31 621 = 103 · 307

6 1 729 = 7 · 13 · 19 16 4 681 = 31 · 151 26 12 801 = 3 · 17 · 251 36 19 951 = 71 · 281 46 33 153 = 3 · 43 · 257

7 1 905 = 3 · 5 · 127 17 5 461 = 43 · 127 27 13 741 = 7 · 13 · 151 37 23 001 = 3 · 11 · 17 · 41 47 34 945 = 5 · 29 · 241

8 2 047 = 23 · 89 18 6 601 = 7 · 23 · 41 28 13 747 = 59 · 233 38 23 377 = 97 · 241 48 35 333 = 89 · 397

9 2 465 = 5 · 17 · 29 19 7 957 = 73 · 109 29 13 981 = 11 · 31 · 41 39 25 761 = 3 · 31 · 277 49 39 865 = 5 · 7 · 17 · 67

10 2 701 = 37 · 73 20 8 321 = 53 · 157 30 14 491 = 43 · 337 40 29 341 = 13 · 37 · 61 50 41 041 = 7 · 11 · 13 · 41

Un nombre de Poulet dont tous les diviseurs d divisent 2^d - 2 est appelé supernombre de Poulet. Il existe de manière infinie beaucoup de nombres de Poulet qui ne sont pas des supernombres de Poulet.

Les premiers plus petits nombres pseudopremiers pour les bases a ≤ 200 sont donnés dans la table suivante ; les couleurs indiquent le nombre de facteurs premiers.

a le plus petit p-p a le plus petit p-p a le plus petit p-p a le plus petit p-p

51 65 = 5 · 13 101 175 = 5² · 7 151 175 = 5² · 7

2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19 152 153 = 3² · 17

3 91 = 7 · 13 53 65 = 5 · 13 103 133 = 7 · 19 153 209 = 11 · 19

4 15 = 3 · 5 54 55 = 5 · 11 104 105 = 3 · 5 · 7 154 155 = 5 · 31

5 124 = 2² · 31 55 63 = 3² · 7 105 451 = 11 · 41 155 231 = 3 · 7 · 11

6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31

7 25 = 5² 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31

8 9 = 3² 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53

9 28 = 2² · 7 59 87 = 3 · 29 109 117 = 3² · 13 159 247 = 13 · 19

10 33 = 3 · 11 60 341 = 11 · 31 110 111 = 3 · 37 160 161 = 7 · 23

11 15 = 3 · 5 61 91 = 7 · 13 111 190 = 2 · 5 · 19 161 190 = 2 · 5 · 19

12 65 = 5 · 13 62 63 = 3² · 7 112 121 = 11² 162 481 = 13 · 37

13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 163 186 = 2 · 3 · 31

14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 164 165 = 3 · 5 · 11

15 341 =" 11" · 13 65 112 = 2⁴ · 7 115 133 = 7 · 19 165 172 = 2² · 43

16 51 = 3 · 17 66 91 = 7 · 13 116 117 = 3² · 13 166 301 = 7 · 43

17 45 = 3² · 5 67 85 = 5 · 17 117 145 = 5 · 29 167 231 = 3 · 7 · 11

18 25 = 5² 68 69 = 3 · 23 118 119 = 7 · 17 168 169 = 13²

19 45 = 3² · 5 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11

20 21 = 3 · 7 70 169 = 13² 120 121 = 11² 170 171 = 3² · 19

21 55 = 5 · 11 71 105 = 3 · 5 · 7 121 133 = 7 · 19 171 215 = 5 · 43

22 69 = 3 · 23 72 85 = 5 · 17 122 123 = 3 · 41 172 247 = 13 · 19

23 33 = 3 · 11 73 111 = 3 · 37 123 217 = 7 · 31 173 205 = 5 · 41

24 25 = 5² 74 75 = 3 · 5² 124 125 = 3³ 174 175 = 5² · 7

25 28 = 2² · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19

26 27 = 3³ 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59

27 65 = 5 · 13 77 247 = 13 · 19 127 153 = 3² · 17 177 196 = 2² · 7²

28 45 = 3² · 5 78 341 = 11 · 31 128 129 = 3 · 43 178 247 = 13 · 19

29 35 = 5 · 7 79 91 = 7 · 13 129 217 = 7 · 31 179 185 = 5 · 37

30 49 = 7² 80 81 = 3⁴ 130 217 = 7 · 31 180 217 = 7 · 31

31 49 = 7² 81 ="3⁴" 85 = 5 · 17 131 143 =" 11" · 13 181 195 = 3 · 5 · 13

32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61

33 85 = 5 · 17 83 105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17

34 35 = 5 · 7 84 85 = 5 · 17 134 135 = 3³ · 5 184 185 = 5 · 37

35 51 = 3 · 17 85 129 = 3 · 43 135 221 = 13 · 17 185 217 = 7 · 31

36 91 = 7 · 13 86 87 = 3 · 29 136 265 = 5 · 53 186 187 = 11 · 17

37 45 = 3² · 5 87 91 = 7 · 13 137 148 = 2² · 37 187 217 = 7 · 31

38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 188 189 = 3³ · 7

39 95 = 5 · 19 89 99 = 3² · 11 139 161 = 7 · 23 189 235 = 5 · 47

40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47 190 231 = 3 · 7 · 11

41 105 = 3 · 5 · 7 91 115 = 5 · 23 141 355 = 5 · 71 191 217 = 7 · 31

42 205 = 5 · 41 92 93 = 3 · 31 142 143 = 11 · 13 192 217 = 7 · 31

43 77 = 7 · 11 93 301 = 7 · 43 143 213 = 3 · 71 193 276 = 2² · 3 · 23

44 45 = 3² · 5 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13

45 76 = 2² · 19 95 141 = 3 · 47 145 153 = 3² · 17 195 259 = 7 · 37

46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 3 · 7² 196 205 = 5 · 41

47 65 = 5 · 13 97 105 = 3 · 5 · 7 147 169 = 13² 197 231 = 3 · 7 · 11

48 49 = 7² 98 99 = 3² · 11 148 231 = 3 · 7 · 11 198 247 = 13 · 19

49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 5² · 7 199 225 = 3² · 5²

50 51 = 3 · 17 100 153 = 3² · 17 150 169 = 13² 200 201 = 3 · 67

Voir aussi

Articles connexes

nombre pseudopremier d'Euler

nombre pseudopremier d'Euler-Jacobi

nombre pseudopremier extra fort de Lucas

nombre pseudopremier de Fibonacci

nombre pseudopremier de Froebnius

nombre pseudopremier de Lucas

nombre pseudopremier de Perrin

nombre pseudopremier de Somer-Lucas

nombre pseudopremier fort de Froebnius

nombre pseudopremier fort de Strong

nombre pseudopremier fort

Liens et documents externes

nombres pseudopremiers de base 2 d'Euler (suite dans A006970 OEIS)

nombres pseudopremiers de base 2 d'Euler-Jacobi (suite dans A047713 OEIS)

nombres pseudopremiers de base 3 d'Euler-Jacobi (suite dans A048950 OEIS)

nombres pseudopremiers forts de base 2 (suite dans A001262 OEIS)

Portail des mathématiques

Ce document provient de « Nombre pseudopremier ».

Catégories : Nombre premier | Test de primalité

n		n		n		n		n
1	341 = 11 · 31	11	2 821 = 7 · 13 · 31	21	8 481 = 3 · 11 · 257	31	15 709 = 23 · 683	41	30 121 = 7 · 13 · 331
2	561 = 3 · 11 · 17	12	3 277 = 29 · 113	22	8 911 = 7 · 19 · 67	32	15 841 = 7 · 31 · 73	42	30 889 = 17 · 23 · 79
3	645 = 3 · 5 · 43	13	4 033 = 37 · 109	23	10 261 = 31 · 331	33	16 705 = 5 · 13 · 257	43	31 417 = 89 · 353
4	1 105 = 5 · 13 · 17	14	4 369 = 17 · 257	24	10 585 = 5 · 29 · 73	34	18 705 = 3 · 5 · 29 · 43	44	31 609 = 73 · 433
5	1 387 = 19 · 73	15	4 371 = 3 · 31 · 47	25	11 305 = 5 · 7 · 17 · 19	35	18 721 = 97 · 193	45	31 621 = 103 · 307
6	1 729 = 7 · 13 · 19	16	4 681 = 31 · 151	26	12 801 = 3 · 17 · 251	36	19 951 = 71 · 281	46	33 153 = 3 · 43 · 257
7	1 905 = 3 · 5 · 127	17	5 461 = 43 · 127	27	13 741 = 7 · 13 · 151	37	23 001 = 3 · 11 · 17 · 41	47	34 945 = 5 · 29 · 241
8	2 047 = 23 · 89	18	6 601 = 7 · 23 · 41	28	13 747 = 59 · 233	38	23 377 = 97 · 241	48	35 333 = 89 · 397
9	2 465 = 5 · 17 · 29	19	7 957 = 73 · 109	29	13 981 = 11 · 31 · 41	39	25 761 = 3 · 31 · 277	49	39 865 = 5 · 7 · 17 · 67
10	2 701 = 37 · 73	20	8 321 = 53 · 157	30	14 491 = 43 · 337	40	29 341 = 13 · 37 · 61	50	41 041 = 7 · 11 · 13 · 41

a	le plus petit p-p	a	le plus petit p-p	a	le plus petit p-p	a	le plus petit p-p
		51	65 = 5 · 13	101	175 = 5² · 7	151	175 = 5² · 7
2	341 = 11 · 31	52	85 = 5 · 17	102	133 = 7 · 19	152	153 = 3² · 17
3	91 = 7 · 13	53	65 = 5 · 13	103	133 = 7 · 19	153	209 = 11 · 19
4	15 = 3 · 5	54	55 = 5 · 11	104	105 = 3 · 5 · 7	154	155 = 5 · 31
5	124 = 2² · 31	55	63 = 3² · 7	105	451 = 11 · 41	155	231 = 3 · 7 · 11
6	35 = 5 · 7	56	57 = 3 · 19	106	133 = 7 · 19	156	217 = 7 · 31
7	25 = 5²	57	65 = 5 · 13	107	133 = 7 · 19	157	186 = 2 · 3 · 31
8	9 = 3²	58	133 = 7 · 19	108	341 = 11 · 31	158	159 = 3 · 53
9	28 = 2² · 7	59	87 = 3 · 29	109	117 = 3² · 13	159	247 = 13 · 19
10	33 = 3 · 11	60	341 = 11 · 31	110	111 = 3 · 37	160	161 = 7 · 23
11	15 = 3 · 5	61	91 = 7 · 13	111	190 = 2 · 5 · 19	161	190 = 2 · 5 · 19
12	65 = 5 · 13	62	63 = 3² · 7	112	121 = 11²	162	481 = 13 · 37
13	21 = 3 · 7	63	341 = 11 · 31	113	133 = 7 · 19	163	186 = 2 · 3 · 31
14	15 = 3 · 5	64	65 = 5 · 13	114	115 = 5 · 23	164	165 = 3 · 5 · 11
15	341 =" 11" · 13	65	112 = 2⁴ · 7	115	133 = 7 · 19	165	172 = 2² · 43
16	51 = 3 · 17	66	91 = 7 · 13	116	117 = 3² · 13	166	301 = 7 · 43
17	45 = 3² · 5	67	85 = 5 · 17	117	145 = 5 · 29	167	231 = 3 · 7 · 11
18	25 = 5²	68	69 = 3 · 23	118	119 = 7 · 17	168	169 = 13²
19	45 = 3² · 5	69	85 = 5 · 17	119	177 = 3 · 59	169	231 = 3 · 7 · 11
20	21 = 3 · 7	70	169 = 13²	120	121 = 11²	170	171 = 3² · 19
21	55 = 5 · 11	71	105 = 3 · 5 · 7	121	133 = 7 · 19	171	215 = 5 · 43
22	69 = 3 · 23	72	85 = 5 · 17	122	123 = 3 · 41	172	247 = 13 · 19
23	33 = 3 · 11	73	111 = 3 · 37	123	217 = 7 · 31	173	205 = 5 · 41
24	25 = 5²	74	75 = 3 · 5²	124	125 = 3³	174	175 = 5² · 7
25	28 = 2² · 7	75	91 = 7 · 13	125	133 = 7 · 19	175	319 = 11 · 19
26	27 = 3³	76	77 = 7 · 11	126	247 = 13 · 19	176	177 = 3 · 59
27	65 = 5 · 13	77	247 = 13 · 19	127	153 = 3² · 17	177	196 = 2² · 7²
28	45 = 3² · 5	78	341 = 11 · 31	128	129 = 3 · 43	178	247 = 13 · 19
29	35 = 5 · 7	79	91 = 7 · 13	129	217 = 7 · 31	179	185 = 5 · 37
30	49 = 7²	80	81 = 3⁴	130	217 = 7 · 31	180	217 = 7 · 31
31	49 = 7²	81 ="3⁴"	85 = 5 · 17	131	143 =" 11" · 13	181	195 = 3 · 5 · 13
32	33 = 3 · 11	82	91 = 7 · 13	132	133 = 7 · 19	182	183 = 3 · 61
33	85 = 5 · 17	83	105 = 3 · 5 · 7	133	145 = 5 · 29	183	221 = 13 · 17
34	35 = 5 · 7	84	85 = 5 · 17	134	135 = 3³ · 5	184	185 = 5 · 37
35	51 = 3 · 17	85	129 = 3 · 43	135	221 = 13 · 17	185	217 = 7 · 31
36	91 = 7 · 13	86	87 = 3 · 29	136	265 = 5 · 53	186	187 = 11 · 17
37	45 = 3² · 5	87	91 = 7 · 13	137	148 = 2² · 37	187	217 = 7 · 31
38	39 = 3 · 13	88	91 = 7 · 13	138	259 = 7 · 37	188	189 = 3³ · 7
39	95 = 5 · 19	89	99 = 3² · 11	139	161 = 7 · 23	189	235 = 5 · 47
40	91 = 7 · 13	90	91 = 7 · 13	140	141 = 3 · 47	190	231 = 3 · 7 · 11
41	105 = 3 · 5 · 7	91	115 = 5 · 23	141	355 = 5 · 71	191	217 = 7 · 31
42	205 = 5 · 41	92	93 = 3 · 31	142	143 = 11 · 13	192	217 = 7 · 31
43	77 = 7 · 11	93	301 = 7 · 43	143	213 = 3 · 71	193	276 = 2² · 3 · 23
44	45 = 3² · 5	94	95 = 5 · 19	144	145 = 5 · 29	194	195 = 3 · 5 · 13
45	76 = 2² · 19	95	141 = 3 · 47	145	153 = 3² · 17	195	259 = 7 · 37
46	133 = 7 · 19	96	133 = 7 · 19	146	147 = 3 · 7²	196	205 = 5 · 41
47	65 = 5 · 13	97	105 = 3 · 5 · 7	147	169 = 13²	197	231 = 3 · 7 · 11
48	49 = 7²	98	99 = 3² · 11	148	231 = 3 · 7 · 11	198	247 = 13 · 19
49	66 = 2 · 3 · 11	99	145 = 5 · 29	149	175 = 5² · 7	199	225 = 3² · 5²
50	51 = 3 · 17	100	153 = 3² · 17	150	169 = 13²	200	201 = 3 · 67

Contenu soumis à la licence CC-BY-SA. Source : Article Pseudo-premier de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

Nombre pseudo-premier — Nombre pseudopremier Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la… … Wikipédia en Français
Pseudo-Denys — l Aréopagite Le Pseudo Denys l Aréopagite est l’auteur de traités chrétiens de théologie mystique, en grec. Il est l une des sources majeures de la spiritualité chrétienne authentique. C était probablement un moine syrien qui a vécu vers 490. D… … Wikipédia en Français
Pseudo-Denys l'Areopagite — Pseudo Denys l Aréopagite Le Pseudo Denys l Aréopagite est l’auteur de traités chrétiens de théologie mystique, en grec. Il est l une des sources majeures de la spiritualité chrétienne authentique. C était probablement un moine syrien qui a vécu… … Wikipédia en Français
Pseudo-denys l'aréopagite — Le Pseudo Denys l Aréopagite est l’auteur de traités chrétiens de théologie mystique, en grec. Il est l une des sources majeures de la spiritualité chrétienne authentique. C était probablement un moine syrien qui a vécu vers 490. D inspiration… … Wikipédia en Français
Pseudo-nitzschia — Pseudo nitzschia … Wikipédia en Français
Pseudo-demonstration d'egalite entre nombres — Pseudo démonstration d égalité entre nombres Le terme Pseudo démonstration d égalité renvoie à l apparente exactitude de démonstrations d égalités qui à l évidence sont fausses. Étant donné que toute proposition fausse est équivalente à une autre … Wikipédia en Français
Pseudo-démonstration que 1 est égal à -1 — Pseudo démonstration d égalité entre nombres Le terme Pseudo démonstration d égalité renvoie à l apparente exactitude de démonstrations d égalités qui à l évidence sont fausses. Étant donné que toute proposition fausse est équivalente à une autre … Wikipédia en Français
Pseudo-démonstration que 1 est égal à 0 — Pseudo démonstration d égalité entre nombres Le terme Pseudo démonstration d égalité renvoie à l apparente exactitude de démonstrations d égalités qui à l évidence sont fausses. Étant donné que toute proposition fausse est équivalente à une autre … Wikipédia en Français
Pseudo-démonstration que 2 est égal à 1 — Pseudo démonstration d égalité entre nombres Le terme Pseudo démonstration d égalité renvoie à l apparente exactitude de démonstrations d égalités qui à l évidence sont fausses. Étant donné que toute proposition fausse est équivalente à une autre … Wikipédia en Français
Pseudo-démonstration que 3 est égal à 0 — Pseudo démonstration d égalité entre nombres Le terme Pseudo démonstration d égalité renvoie à l apparente exactitude de démonstrations d égalités qui à l évidence sont fausses. Étant donné que toute proposition fausse est équivalente à une autre … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Pseudo-premier

Nombre pseudopremier

Voir aussi

Articles connexes

Liens et documents externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Pseudo-premier

Nombre pseudopremier

Voir aussi

Articles connexes

Liens et documents externes

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link