Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Functiones et Approx...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Project Euclid
Other literature type . 2000
Data sources: Project Euclid
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article
Data sources: zbMATH Open
Functiones et Approximatio Commentarii Mathematici
Article . 2000 . Peer-reviewed
Data sources: Crossref
versions View all 3 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Lucas pseudoprimes

Lucas pseudoprimes.
Authors: Rotkiewicz, Andrzej;

Lucas pseudoprimes

Abstract

In the paper under review, the author continues his investigation on the occurrence of various kinds of pseudoprimes with respect to a fixed Lucas sequence in arithmetical progressions. Recall that if \(a\) is an integer different from \(0,\pm1\), then a composite integer \(n\) which is coprime to \(a\) is called a base \(a\) pseudoprime if \(a^{n-1}\equiv 1\pmod a\). If \(n\) is odd, composite, and coprime to \(a\), and if \(a^{(n-1)/2}\equiv (a|n)\pmod n\) holds, then \(n\) is called an Euler pseudoprime to base \(a\). The analogous concepts of pseudoprimes with respect to Lucas sequences lead to four types of pseudoprimes. That is, Let \(P\) and \(Q\) be two integers with \(D= P^2-4Q\neq 0\), and let \((U_n)_{n\geq 0}\) and \((V_n)_{n\geq 0}\) be the Lucas sequences of first and second kind, respectively, with parameters \(P\) and \(Q\), and let \(n\) be composite and coprime to \(2QD\). Then, \(n\) is a Lucas pseudoprime, a Dickson pseudoprime, a Lucas pseudoprime of the second kind, or a Dickson pseudoprime of the second kind, according to whether \(n\) satisfies the congruence \(U_{n-(D|n)}\equiv 0\pmod n\), or \(U_n\equiv (D|n)\pmod n\), or \(V_n\equiv P\pmod n\) or \(V_{n-(D|n)}\equiv 2Q^{(1-(D|n))/2}\pmod n\), respectively. The odd composite number \(n\) is an Euler-Lucas pseudoprime if \(U_{(n-(D|n))/2}\equiv 0\pmod n\), when \((Q|n)=1\), or \(V_{(n-(D|n))/2}\equiv 0\pmod n\), when \((Q|n)=-1\). The author's first three theorems point out that some of the above pseudoprimality conditions imply some of the other ones. For example, if \(n\) is coprime to \(P\) and is simultaneously an Euler-Lucas pseudoprime (with parameters \(P\) and \(Q\)) and an Euler pseudoprime to base \(Q\), then \(n\) verifies all four pseudoprimality conditions (Theorem 1). If \(n\) is coprime to \(P\) and is simultaneously an Euler-Lucas pseudoprime and a Dickson pseudoprime (with parameters \(P\) and \(Q\)) then \(n\) is also an Euler pseudoprime to base \(Q\) (Theorem 2), while if \(n\) is square-free and is both a Dickson pseudoprime of the second kind and an Euler pseudoprime to base \(Q\), then \(n\) is a Lucas-Euler pseudoprime (Theorem 3). The proofs of these three theorems are elementary and rely on algebraic manipulations with the two Lucas sequences \((U_n)_{n\geq 0}\) and \((V_n)_{n\geq 0}\) in question. Finally, using his Theorem 1, a result of \textit{R. Baillie} and \textit{S. S. Wagstaff jun.} [ Math. Comput. 35, 1391--1417 (1980; Zbl 0458.10003)], and a result of the present author with \textit{A. Schinzel} [Bull. Pol. Acad. Sci., Math. 48, No.~1, 77--80 (2000; Zbl 0951.11002)], the author deduces that if \(Q=\pm1\), and for \(\varepsilon\in\{\pm1\}\), every arithmetic progression \(ax+b\) with \(a\) and \(b\) coprime containing an odd integer \(n_0\) with \((D|n_0)= \varepsilon\) contains infinitely many Lucas pseudoprimes \(n\) (in fact, even infinitely many strong Lucas pseudoprimes) satisfying \((D|n)= \varepsilon\) and which also satisfy all four types of pseudoprimality conditions, and, in fact, for a large positive real number \(x\), the number of such \(n\) is \(\gg\log x/\log\log n\), where the constant understood in \(\gg\) is computable and depends on \(a\), \(b\) and \(P\). The notion of a strong Lucas pseudoprime which we do not reproduce here is defined in the paper and it has been investigated by this author in some of his previous work [Math. Comput. 39, 239--247 (1982; Zbl 0492.10002)].

Keywords

Dickson pseudoprime of the second kind, Euler-Lucas pseudoprime, 11A51, Lucas pseudoprime of the second kind, 11A07, 11B39, Lucas pseudoprime, Lucas sequence in arithmetical progressions, Euler pseudoprime, pseudoprimality conditions, strong Lucas pseudoprimes, Dickson pseudoprime, Congruences; primitive roots; residue systems, Factorization; primality, pseudoprime, Lucas sequence

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green
hybrid