Difference between revisions of "Fermat pseudoprime"

From Number
Jump to: navigation, search
(Created page with '{{base-relative pseudoprimality property}} ==Definition== Suppose <math>n</math> is a composite natural number and <math>a</math> is relatively prime to <math>n</math>. <math>n...')
 
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
{{base-relative pseudoprimality property}}
 
{{base-relative pseudoprimality property}}
 
+
{{nottobeconfusedwith|[[Fermat prime]]}}
 
==Definition==
 
==Definition==
  
Line 9: Line 9:
 
In other words, <math>n</math> divides <math>a^{n-1} - 1</math>, or, the order of <math>a</math> mod <math>n</math> divides <math>n - 1</math>.
 
In other words, <math>n</math> divides <math>a^{n-1} - 1</math>, or, the order of <math>a</math> mod <math>n</math> divides <math>n - 1</math>.
  
 +
==Facts==
 +
 +
* [[Formula for number of bases to which a number is a Fermat pseudoprime]]
 
==Relation with other properties==
 
==Relation with other properties==
  
Line 19: Line 22:
 
===Property when applied to one or more choice of base===
 
===Property when applied to one or more choice of base===
  
* [[Absolute pseudoprime]] is a number that is a Fermat pseudoprime for every (relatively prime) base.
+
* [[Carmichael number]] is a number that is a Fermat pseudoprime for every (relatively prime) base.
 
* [[Poulet number]] is a Fermat pseudoprime to base <math>2</math> (in particular, it needs to be an odd number).
 
* [[Poulet number]] is a Fermat pseudoprime to base <math>2</math> (in particular, it needs to be an odd number).

Latest revision as of 21:36, 3 January 2012

Template:Base-relative pseudoprimality property This is not to be confused with Fermat prime

Definition

Suppose is a composite natural number and is relatively prime to . is termed a Fermat pseudoprime relative to base if we have:

.

In other words, divides , or, the order of mod divides .

Facts

Relation with other properties

Stronger properties

Property when applied to one or more choice of base

  • Carmichael number is a number that is a Fermat pseudoprime for every (relatively prime) base.
  • Poulet number is a Fermat pseudoprime to base (in particular, it needs to be an odd number).