Vipul: Created page with '{{base-relative pseudoprimality property}} ==Definition== Let $n$ be a composite natural number and $a$ be an integer relatively prime to $n$ . ...'

2009-04-19T23:05:46Z

Created page with '{{base-relative pseudoprimality property}} ==Definition== Let <math>n</math> be a composite natural number and <math>a</math> be an integer relatively prime to <math>n</math>. ...'

New page

{{base-relative pseudoprimality property}}

==Definition==

Let <math>n</math> be a composite natural number and <math>a</math> be an integer relatively prime to <math>n</math>. We say that <math>n</math> is an '''Euler-Jacobi pseudoprime''' with respect to the base <math>a</math> if <math>n</math> is odd and:

<math>a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod n</math>,

where the expression on the right is the [[Jacobi symbol]] of <math>a</math> mod <math>n</math>. Note that the analogous statement ''is'' true for all primes, because for a prime, the Jacobi symbol equals the [[Legendre symbol]].

==Relation with other properties==

===Weaker properties===

* [[Stronger than::Euler pseudoprime]]
* [[Stronger than::Fermat pseudoprime]]

===Other related properties===

* [[Strong pseudoprime]]

Euler-Jacobi pseudoprime - Revision history

Vipul: Created page with '{{base-relative pseudoprimality property}} ==Definition== Let n be a composite natural number and a be an integer relatively prime to n. ...'

Vipul: Created page with '{{base-relative pseudoprimality property}} ==Definition== Let $n$ be a composite natural number and $a$ be an integer relatively prime to $n$ . ...'