FACTOID # 120: Nepal’s flag isn’t square or rectangular. It’s a double triangle.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Pseudoprime" also viewed:
RECENT ARTICLES
More Recent Articles »
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Pseudoprime

A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. Pseudoprimes can be classified by according to which property they satisfy.


The most important class of pseudoprimes come from the Fermat's little theorem and hence they are called Fermat pseudoprimes. This theorem states that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. If a number x is not prime, a is coprime to x and x divides ax-1 - 1, then x is called a pseudoprime to base a. A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number.


The smallest Fermat pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, nevertheless it satisfies Fermats little theorem; 2341=2 (mod 341).


There are applications in public-key cryptography such as RSA that need large prime numbers. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a very small chance that a composite number is declared to be prime), there are fast algorithms such as the Fermat primality test, the Solovay-Strassen primality test, and the Miller-Rabin primality test.


There are infinitely many pseudoprimes (in fact infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudo-primes to base 2 below 1000, to a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians (sequence A001567 in OEIS). Poulet numbers and Carmichael numbers (in bold) till 41041 are:

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 · 331
2 561 = 3 · 11 · 17 12 3277 = 29 · 112 22 8911 = 7 · 19 · 67 32 15841 = 7 · 31 · 73 42 30889 = 17 · 23 · 79
3 645 = 3 · 5 · 43 13 4033 = 37 · 109 23 10261 = 31 · 331 33 16705 = 5 · 13 · 257 43 31417 = 89 · 353
4 1105 = 5 · 13 · 17 14 4369 = 17 · 257 24 10585 = 5 · 29 · 73 34 18705 = 3 · 5 · 29 · 43 44 31609 = 73 · 433
5 1387 = 19 · 73 15 4371 = 3 · 31 · 47 25 11305 = 5 · 7 · 17 · 19 35 18721 = 97 · 193 45 31621 = 103 · 307
6 1729 = 7 · 13 · 19 16 4681 = 31 · 151 26 12801 = 3 · 17 · 251 36 19951 = 71 · 281 46 33153 = 3 · 43 · 257
7 1905 = 3 · 5 · 127 17 5461 = 43 · 127 27 13741 = 7 · 13 · 151 37 23001 = 3 · 11 · 17 · 41 47 34945 = 5 · 29 · 241
8 2047 = 23 · 89 18 6601 = 7 · 23 · 41 28 13747 = 59 · 233 38 23377 = 97 · 241 48 35333 = 89 · 397
9 2465 = 5 · 17 · 29 19 7957 = 73 · 109 29 13981 = 11 · 31 · 41 39 25761 = 3 · 31 · 277 49 39865 = 5 · 7 · 17 · 67
10 2701 = 37 · 73 20 8321 = 53 · 157 30 14491 = 43 · 337 40 29341 = 13 · 37 · 61 50 41041 = 7 · 11 · 13 · 41


A Poulet number all of whose divisors d divide 2d - 2 is called super-Poulet number. There are an infinitely many Poulet numbers which are not super-Poulet Numbers.


The first smallest pseudoprimes for bases a ≤ 200 are given in the following table; the colors mark the number of prime factors.

a smallest p-p a smallest p-p a smallest p-p a smallest p-p
    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 = 52 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31
8 9 = 32 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 = 112 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 = 52 68 69 = 3 · 23 118 119 = 7 · 17 168 169 = 132
19 45 = 32 · 5 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11
20 21 = 3 · 7 70 169 = 132 120 121 = 112 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 = 52 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 = 72 80 81 = 34 130 217 = 7 · 31 180 217 = 7 · 31
31 49 = 72 81 = 34 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 = 132 197 231 = 3 · 7 · 11
48 49 = 72 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 = 132 200 201 = 3 · 67

See also:

  • Euler pseudoprime
    • base-2 Euler pseudoprimes (sequence A006970 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=006970) in OEIS)
  • Euler-Jacobi pseudoprime
    • base-2 Euler-Jacobi pseudoprimes (sequence A047713 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=047713) in OEIS)
    • base-3 Euler-Jacobi pseudoprimes (sequence A048950 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=048950) in OEIS)
  • Extra strong Lucas pseudoprime
  • Fibonacci pseudoprime
  • Frobenius pseudoprime
  • Lucas pseudoprime
  • Perrin pseudoprime
  • Somer-Lucas pseudoprime
  • Strong Frobenius pseudoprime
  • Strong Lucas pseudoprime
  • Strong pseudoprime
    • base-2 strong pseudoprimes (sequence A001262 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001262) in OEIS)

External links

  • Pseudoprimes up to 15,999 (http://wikisource.org/wiki/Pseudoprime_numbers)

  Results from FactBites:
 
Symmetric Pseudoprimes (379 words)
This is why 341 is called a pseudoprime relative to the base 2.
We could also define symmetric pseudoprimes in terms of Newton's sums for the roots of a polynomial.  Let f denote a monic polynomial of degree d with integer coefficients, and let s(k) denote the sum of the kth powers of the roots of f.  Lucas observed that if p is a prime then s(p
Symmetric pseudoprimes tend to be more rare relative to polynomials with larger Galois groups.
NationMaster - Encyclopedia: Lucas pseudoprime (234 words)
In the specific case of the Fibonacci sequence, where D = 5, the first pseudoprimes are 323 and 377; (5/323) and (5/377) are both −1, the 324th Fibonacci number is a multiple of 323, and the 378th is a multiple of 377.
A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime.
A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number.
  More results at FactBites »


 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments
Please enter the 5-letter protection code

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.