Psévdopráštevilo je celo število, ki ima določeno značilnost, vezano na praštevila, samo pa ni praštevilo.
Najpomembnejša praštevila izhajajo iz Fermatovega malega izreka in se zato imenujejo Fermatova psevdopraštevila. Izrek pravi, da če je p praštevilo in je a tuje p, potem je ap-1 - 1 deljivo s p. Če število x ni praštevilo, a je tuj x in x deli ax-1 - 1, se x imenuje praštevilo za bazo a. Število x, ki je psevdopraštevilo za vse vrednosti a, katera so x tuja, se imenuje Carmichaelovo število.
Najmanjše psevdopraštevilo za bazo 2 je 341. Ni praštevilo, ker je enako 11 · 31, vendar zanj velja Fermatov mali izrek, 2341 = 2 (mod 341).
Velika praštevila se uporabljajo na področjih kot je na primer kriptografija z javnim ključem RSA. Običajni algoritem za generiranje praštevil poišče naključna liha števila in preveri, če so praštevila. Preverjanje praštevil pa je počasno. Če ne potrebujemo natančnega testa (sestavljeno število z malo verjetnostjo smatramo za praštevilo), lahko uporabimo hitre algoritme na osnovi Fermatovega malega izreka. Na preprost način, na primer, ugotovimo ali je število x praštevilo z izbiro naključnega števila a in preverimo ali x deli a x - a. Če je odgovor nikalen, potem x ne more biti praštevilo in obratno, imamo lahko x za "verjetno praštevilo", ter tako nadaljujemo s preverjanjem za druge vrednosti a.
Izboljšane inačice tega algoritma nam dajo močno verjetna praštevila. Monier in Rabin sta pokazala, da je za izboljšan algoritem za vsak a verjetnost pojavitve napačnega praštevila vsaj 3 od 4.
Obstaja neskončno mnogo psevdopraštevil (in celo neskončno mnogo Carmichaelovih števil), vendar so zelo redka. Pod 1000 so samo 3 psevdopraštevila za bazo 2 in pod milijon samo 245. Psevdopraštevila za bazo 2 se imenujejo Pouletova števila ali včasih Sarrusova ševila ali tudi Fermatova števila. . Pouletova števila in Carmichaelova števila (krepko) pod 10000 so:
n n n n n 1 341 = 11 · 31 11 2821 = 7 · 13 · 31 21 8481 = 3 · 11 · 257 31 15709 = 23 · 683 41 30121 = 7 · 13 · 3312 561 = 3 · 11 · 17 12 3277 = 29 · 112 22 8911 = 7 · 19 · 67 32 15841 = 7 · 31 · 73 42 30889 = 17 · 23 · 793 645 = 3 · 5 · 43 13 4033 = 37 · 109 23 10261 = 31 · 331 33 16705 = 5 · 13 · 257 43 31417 = 89 · 3534 1105 = 5 · 13 · 17 14 4369 = 17 · 257 24 10585 = 5 · 29 · 73 34 18705 = 3 · 5 · 29 · 43 44 31609 = 73 · 4335 1387 = 19 · 73 15 4371 = 3 · 31 · 47 25 11305 = 5 · 7 · 17 · 19 35 18721 = 97 · 193 45 31621 = 103 · 3076 1729 = 7 · 13 · 19 16 4681 = 31 · 151 26 12801 = 3 · 17 · 251 36 19951 = 71 · 281 46 33153 = 3 · 43 · 2577 1905 = 3 · 5 · 127 17 5461 = 43 · 127 27 13741 = 7 · 13 · 151 37 23001 = 3 · 11 · 17 · 41 47 34945 = 5 · 29 · 2418 2047 = 23 · 89 18 6601 = 7 · 23 · 41 28 13747 = 59 · 233 38 23377 = 97 · 241 48 35333 = 89 · 3979 2465 = 5 · 17 · 29 19 7957 = 73 · 109 29 13981 = 11 · 31 · 41 39 25761 = 3 · 31 · 277 49 39865 = 5 · 7 · 17 · 6710 2701 = 37 · 73 20 8321 = 53 · 157 30 14491 = 43 · 337 40 29341 = 13 · 37 · 61 50 41041 = 7 · 11 · 13 · 41
Pouletovo število za katerega za vse njegove delitelje d velja d | 2d - 2 se imenuje super Pouletovo število. Za vsa ta števila velja μ(n) = 1 . Obstaja neštevno mnogo Pouletovih števil, ki niso super-Pouletova števila.
Prva najmanjša psevdopraštevila za druge baze a ≤ 200 so: a najmanjše pp a najmanjše pp a najmanjše pp a najmanjše pp 51 65 = 5 · 13 101 175 = 52 · 7 151 175 = 52 · 7 2 341 =" 11" · 13 52 85 = 5 · 17 102 133 = 7 · 19 152 153 = 32 · 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 = 22 · 31 55 63 = 32 · 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 57 65 = 5 · 13 107 133 =" 7 " · 19 157 186 = 2 · 3 · 31 8 9 58 133 = 7 · 19 108 341 =" 11" · 31 158 159 = 3 · 53 9 28 = 22 · 7 59 87 = 3 · 29 109 117 = 32 · 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 = 32 · 7 112 121 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 = 24 · 7 115 133 =" 7 " · 19 165 172 = 22 · 43 16 51 =" 3 " · 17 66 91 = 7 · 13 116 117 = 32 · 13 166 301 = 7 · 43 17 45 = 32 · 5 67 85 = 5 · 17 117 145 = 5 · 29 167 231 = 3 · 7 · 11 18 25 68 69 =" 3 " · 23 118 119 = 7 · 17 168 169 19 45 = 32 · 5 69 85 = 5 · 17 119 177 =" 3 " · 59 169 231 = 3 · 7 · 11 20 21 = 3 · 7 70 169 120 121 170 171 = 32 · 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 74 75 = 3 · 52 124 125 = 33 174 175 = 52 · 7 25 28 = 22 · 7 75 91 =" 7 " · 13 125 133 = 7 · 19 175 319 =" 11" · 19 26 27 = 33 76 77 = 7 · 11 126 247 =" 13" · 19 176 177 = 3 · 59 27 65 = 5 · 13 77 247 =" 13" · 19 127 153 = 32 · 17 177 196 = 22 · 72 28 45 = 32 · 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 80 81 = 34 130 217 = 7 · 31 180 217 = 7 · 31 31 49 81 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 = 33 · 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 = 32 · 5 87 91 = 7 · 13 137 148 = 22 · 37 187 217 = 7 · 31 38 39 = 3 · 13 88 91 = 7 · 13 138 259 =" 7 " · 37 188 189 = 33 · 7 39 95 =" 5 " · 19 89 99 = 32 · 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 = 22 · 3 · 23 44 45 = 32 · 5 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13 45 76 = 22 · 19 95 141 = 3 · 47 145 153 = 32 · 17 195 259 =" 7 " · 37 46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 3 · 72 196 205 = 5 · 41 47 65 =" 5 " · 13 97 105 = 3 · 5 · 7 147 169 197 231 = 3 · 7 · 11 48 49 98 99 = 32 · 11 148 231 = 3 · 7 · 11 198 247 =" 13" · 19 49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 52 · 7 199 225 = 32 · 52 50 51 = 3 · 17 100 153 = 32 · 17 150 169 200 201 = 3 · 67
Značilnosti psevdopraštevil
Števila 2n-1 ne računamo. Na prvi pogled se zdi, da je za vsa najmanjša psevdopraštevila v katerikoli bazi a μ(n) enaka 0 ali 1, vendar, začudujoče, temu ni tako. Prvih baz a, za katere ima njihovo najmanjše psevdopraštevilo μ(n) = -1, pod 100 je samo pet: a najmanjše pp 41 105 = 3 · 5 · 7 49 66 = 2 · 3 · 11 71 105 = 3 · 5 · 7 83 105 = 3 · 5 · 7 97 105 = 3 · 5 · 7
To je še en slikovit primer kako je potrebno biti pazljiv z domnevami, ki temeljijo na izkustvenem dokazu v matematiki. Fermatov mali izrek nam za prva števila da: n an-1-1 an-1 - 1 mod n 1 0 0 2 1 1 3 3 0 4 7 3 5 15 0 6 31 1 7 63 0 8 127 7 9 255 3 10 511 1 11 1023 0 12 2047 7 13 4095 0 14 8191 1 15 16383 3 16 32767 15 17 65535 0 18 131071 13 19 262143 0 20 524287 7 21 1048575 3 22 2097151 1 23 4194303 0 24 8388607 7 25 16777215 15 26 33554431 1 27 67108863 12 28 134217727 7 29 268435455 0 30 536870911 1 31 1073741823 0 32 2147483647 31 33 4294967295 3
Glej tudi
Eulerjevo psevdopraštevilo Eulerjeva praštevila za bazo 2 Euler-Jacobijevo psevdopraštevilo Euler-Jacobijeva psevdopraštevila za bazo 2 Euler-Jacobijeva psevdopraštevila za bazo 3 Fermatovo psevdopraštevilo Fibonaccijevo psevdopraštevilo Frobeniusovo psevdopraštevilo Lucasovo psevdopraštevilo močno Frobeniusovo psevdopraštevilo močno Lucasovo psevdopraštevilo močno psevdopraštevilo močna psevdopraštevila za bazo 2 Perrinovo psevdopraštevilo Somer-Lucasovo psevdopraštevilo zelo močno Lucasovo psevdopraštevilo
Kategorija:Praštevila