Fermat pseudoprime: Difference between revisions

Revision as of 15:09, 7 November 2007

A composite number n is called Fermat pseudoprime to a natural base a, coprime to n, so that $a^{n-1}\equiv 1{\pmod {n}}$

It is sufficient, that the base a satisfy $2\leq a\leq n-2$ because every odd number n satisfy for $a=n-1\$ that $a^{n-1}\equiv 1{\pmod {n}}$ ^[1]

If n is a Fermat pseudoprime to base a, then n is a Fermat pseudoprime to base $b\cdot n+a$ for every integer $b\geq 0$

↑ Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2.

Revision as of 14:52, 7 November 2007 (view source) imported>Karsten Meyer m (Fermat Pseudoprime moved to Fermat pseudoprime: mistake) ← Older edit		Revision as of 15:09, 7 November 2007 (view source) imported>Karsten Meyer mNo edit summary Newer edit →
Line 4:		Line 4:

	It is sufficient, that the base ''a'' satisfy <math>2 \le a \le n-2</math> because every odd number ''n'' satisfy for <math>a = n-1\ </math> that <math>a^{n-1} \equiv 1 \pmod n</math><ref>Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2. </ref>		It is sufficient, that the base ''a'' satisfy <math>2 \le a \le n-2</math> because every odd number ''n'' satisfy for <math>a = n-1\ </math> that <math>a^{n-1} \equiv 1 \pmod n</math><ref>Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2. </ref>

	If ''n'' is a Fermat pseudoprime to base ''a'', then ''n'' is a Fermat pseudoprime to base <math>b\cdot n+a</math> for every integer <math>b \ge 0</math>		If ''n'' is a Fermat pseudoprime to base ''a'', then ''n'' is a Fermat pseudoprime to base <math>b\cdot n+a</math> for every integer <math>b \ge 0</math>