# Difference between revisions of "Fermat pseudoprime"

From Number

(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=== | ||

− | * [[ | + | * [[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*

## Contents

## 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

- Strong pseudoprime to a given base.
- Euler pseudoprime to a given base.
- Euler-Jacobi pseudoprime to a given base.

### 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).