2
$\begingroup$

I am currently researching on all primality tests deriving from Lucas' original paper Théorie des Fonctions Numériques Simplement Périodiques, which is of course known for its great deal of confusion. Still, I managed to make my way trough basically all of the recent tests (LLehmer, LLehmerRiesel, etc.) using publications from the authors and various sources - some of which I'll leave below, more on them in the appropriate paragraph. Note that there are various revisions from Lucas himself of the article, but every work of Lucas is a perfect source to me. I will not differentiate between them.

Back to us: time came I had to write about the original Lucas test in order to further develop it into the Lucas probable prime test and then the Bailie-PSW test. Of course those two are of no concern; there are plenty of sources. However I hardly managed to find something about the original formulation Lucas gave; lots of tests have the name "Lucas" in them, but I'm interested in that original one. It is my understanding that Lucas did not properly formulate it, but he just used it in some confused example and left it there. Still, I could not find a great deal of info.

So in short I'm trying to understand what Lucas did on its original paper - no reworks as in Carmichael; I am interested in the original for historical reasons. The article is known to be kind of a mess, and what's more it's in French -- I can't understand it nor find a translation. I do not know what version of the test he used; from what I read I suppose it was just a one-time procedure on an example which was then further developed in most of the "Lucas" tests. Specifically, my question is

  • does anyone have a better idea on how he exactly used his sequences in primality testing on the original paper?
  • are there some examples, especially from his paper, you could share?
  • are there some better sources? of every kind: papers, videos, etc...

Thank you all in advance and sorry for the long post / weird formatting, it's my first time on SE!


Duplicate(?)

While this is a well discussed topic, I hardly found discussions about the original test by Lucas and I thought it would be useful for the community to put here all my sources and ask for more insight on the original work - not the latter ones. That I did not find, and I'd like to help out people in my situation.

For example, I encountered this discussion which gave a book by Hans Riesel itself as an interesting source. Fact is, I do not have access to that book.

I also posted this same question on Mathematics stackexchange, and was advised to cross-post it here due to its historical focus. I modified my post a little since it seemed kinda ambiguous on the nature of the test I'm interested in.


Useful sources

The original article can be found in French on JSTOR, divided into two parts:

  1. American Journal of Mathematics , Vol. 1, No. 2 (1878), pp. 184-196. http://www.jstor.org/stable/2369308
  2. American Journal of Mathematics , Vol. 1, No. 4 (1878), pp. 289-321. http://www.jstor.org/stable/2369373

and I leave for posterity an English translation and revision of the first part -- it could be of great help for someone. If anyone manages to find the second part I'll be glad to add it too -- I couldn't and I'm not sure it does exist.

  1. Sidney Kravitz, Douglas Lind: “The theory of simply periodic numerical functions”, Fibonacci Association (1969). https://www.mathstat.dal.ca/FQ/Books/Complete/simply-periodic.pdf.
  2. [?]

Last but not least, the famous Carmichael did a great job revising the original article; sadly he modified it to make it work better, which is awesome but not what I need. As before, I leave it here for posterity - it's a life saver.

  1. R. D. Carmichael. “On the Numerical Factors of the Arithmetic Forms $α^n±β^n$”, Annals of Mathematics15 1/4 (1913), pp.30–48. http://www.jstor.org/stable/1967797.
  2. R. D. Carmichael. “On the Numerical Factors of the Arithmetic Forms $α^n±β^n$”, Annals of Mathematics15 1/4 (1913), pp. 49–70. http://www.jstor.org/stable/1967798.

$\endgroup$
12
  • 1
    $\begingroup$ As far as secondary literature, Lehmer discusses Lucas's tests in section 5 of An Extended Theory of Lucas' Functions. See also Dickson's History of the theory of numbers, ch. XVII. $\endgroup$
    – Conifold
    Jul 7 at 23:49
  • $\begingroup$ I think the latter source has the answer I'm searching for (page 397)! I shall study it better in a few days and post an answer so people don't have to search too much. As far as the first source goes, I was aware of Lehmer's work (~1930) but it was ambiguous to me if it referred to Lucas' original paper or Carmichael's revision. Thank you, and sorry but I can't upvote your comment - too little reputation on hsm.SE, I think. $\endgroup$ Jul 8 at 10:05
  • $\begingroup$ The name "Bailie-PSW test" is so strange, since it puts the first name on a rather different footing than the other three. I am surprised this is the standard name when "BPSW test" seems more reasonable. Nobody speaks of the Lucas-L test or the L-Lehmer test. $\endgroup$
    – KCd
    Jul 27 at 22:10
  • 1
    $\begingroup$ If there is sufficient interest, I can translate the second part, I've translated several French papers in the past. $\endgroup$ Jul 28 at 13:02
  • $\begingroup$ Was Lucas a high school teacher? Is this a homework question? $\endgroup$ Jul 28 at 19:03
0
$\begingroup$

User @Conifold provided a perfect source, I shall briefly report the information it contains to close the question. I hope answering myself is fine in these situations, feel free to correct or post another answer.

See Dickson's History of the theory of numbers, chapter XVII for the full content.


After defining his sequences $u_n$ and $v_n$, Lucas studied relations between their terms and gave some properties of purely algebraic nature. These were then properly demonstrated.

What I was searching for can be found starting from page 397:

Lucas stated that, if $4m+3$ is prime, $p = 2^{4m+3} — 1$ is prime if the first term of the series 3, 7, 47,..., defined by $r_{n+1} = r_n^2 — 2$, which is divisible by $p$ is of rank $4m+2$; but $p$ is composite if no one of the first $4m +2$ terms is divisible by $p$.

This will of course be later reformulated in the famous Lucas-Lehmer test. The formulation Lucas gave, albeit weaker than Lehmer's, can find some divisors if the number is composite.

Lucas then proceeds giving some examples: see page 399 for a primality test for numbers in the form $p = 2^{4q+1} — 1$, note that more can be found. Important paragraphs are conveniently marked with a pencil.

The chapter then proceeds with more applications and examples of historical relevance, like exchanges with other mathematicians of the time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.