1980/01/01 by Robert Baillie, Samuel S. Wagstaff · 3 citations
Mathematics · Physics and Astronomy · #Advanced Mathematical Identities #Advanced Mathematical Theories and Applications #Algorithm #Analytic Number Theory Research #Artificial intelligence #Combinatorics #Computer science #Linguistics #Mathematics #Parenthesis #Philosophy #Prime (order theory)
paper · pdf · doi:10.1090/s0025-5718-1980-0583518-6
openalex publication_date 1980/01/01 · openalex created_date 2022/05/12 · openalex updated_date 2026/08/01
We define several types of pseudoprimes with respect to Lucas sequences and prove the analogs of various theorems about ordinary pseudoprimes. For example, we show that Lucas pseudoprimes are rare and we count the Lucas sequences modulo <italic>n</italic> with respect to which <italic>n</italic> is a Lucas pseudoprime. We suggest some powerful new primality tests which combine Lucas pseudoprimes with ordinary pseudoprimes. Since these tests require the evaluation of the least number <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for which the Jacobi symbol <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis f left-parenthesis n right-parenthesis slash n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>f</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(f(n)/n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is less than 1, we evaluate the average order of the function <italic>f</italic> .