Talk:Carmichael number/Archive 1

This is an archive of past discussions about Carmichael number. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

"If Carmichael numbers did not exist..."

If Carmichael numbers did not exist, this primality test could always be used to prove compositeness of a number. -- Is this true? Both primes and Carmichael numbers pass the Fermat primality test, so it would follow that if Carmichael numbers did not exist, this test could always be used to prove the primalty of a number (which could otherwise be a Carmichael composite). When the Fermat test fails, the number must be a composite. Am I missing something? OwenX 16:10, 29 July 2005 (UTC)

Carmichael numbers exist. So, that question ist obsolete. We could imagine, that if there is exist no fermat pseudoprime number (include the Carmichael numbers), that there exist no Cryptography with prime numbers, or stronger there would exist no prime numbers. Perhaps it would be like that, perhaps not. Fact is, fermat Pseudoprime numbers exist. --Arbol01 22:45, 29 July 2005 (UTC)

Fair enough. I changed the statement to avoid the hypothetical, and also corrected the compositeness/primality mistake. OwenX 16:13, 30 July 2005 (UTC)

Some deletions

I removed the Moebius function values since it is clear if you list the different prime factors, that an even number of factors will give +1 and an odd number of factors will give -1. This doesn't provide any insight; it's just the definition of the Moebius function. I removed the term "super Carmichael number" since it is non-standard. AxelBoldt 03:13 Sep 25, 2002 (UTC)

What something is standard is very relative term. Negative numbers or even vorse, the imaginary numbers would be quite strange, let us say, for Ancient Egiptian mathematicians. The "super" suffix just shows some properties which are related to other numbers and not something 'super' special. Kindest regard. --XJam 09:20 Oct 16, 2002 (UTC)

higher-order Carmichael numbers are not defined in the article (or did I miss their definition ?) What are they ? --FvdP 09:31 Oct 16, 2002 (UTC)

Yes, it is true. You didn't miss any definition. I've put them in for now just for the curiosity and to think a little bit more about 'ordinary' Carmichael numbers. Their usage is, as it seems, one of mathematical open questions. More to come, when dear time permits. --XJam 00:30 Oct 17, 2002 (UTC)

I put the paragraph here for now:

We can introduce "higher-order" Carmichael numbers. One of Erdos' results shows that there should be infinitely many Carmichael numbers of order m for every m> 0. But we do not know whether there exist any Carmichael numbers of order 3.

Without a definition, this paragraph does not help. AxelBoldt 02:43 Oct 17, 2002 (UTC)

Hey guys, this is an encyclopedia not some mathematical textbook. Why every mathematical term always needs a definition itself? An informative character of one term is also very much interesting and useful and that is not just on Talk pages. Recently I've read one excellent text from a high valued mathematician Maxim Kontsevich and I do believe that many of his words would be thrown away to Talk pages in Wikipedia. I think that someone is exaggerating too much here. If Georg Cantor would be Wikipedian today, I deeply believe that many of his revolutionary ideas would also be thrown to Talk pages. And so on. I can number many similar examples, but I guess my argument won't be much in force. Pure definition can satisfy just an educational needs. Can you give me the definition of the Europe, for example? I guess not. So you put a map of it and some more words about. And these have purely informative character. That's my opinion. Math is 'infinitely much more' than just pure and dull definitions and theorems. In the same manner I can eventually prove that Euler, Gauss or Srinivasa Aaiyangar Ramanujan never existed. But these are just my blowings in the wind as Mr. Dylan would sing ... --XJamRastafire 11:41 Oct 17, 2002 (UTC)

Mathematicians just want to know what they're talking about. It's not much use hearing about higher-order carmichael numbers if you don't have a clue what they are. The case of "Europe" is different: even if you have no formal definition, you informally know what Europe means.

Anyway here is a definition, by Everett W. Howe in his paper Higher-order Carmichael numbers:

"We define a Carmichael number of order m to be a composite integer n such that nth-power raising defines an endomorphism of every Z/nZ-algebra that can be generated as a Z/nZ-module by m elements." There is a more elementary but less natural equivalent definition in article, see Theorem 1. Howe says: "We give a simple criterion to determine whether a number is a Carmichael number of order m, and we give a heuristic argument (based on an argument of Erdos for the usual Carmichael numbers) that indicates that for every m there should be infinitely many Carmichael numbers of order m. (...)" (I hope I'm not infringing any copyright by publishing this here; but it's a paper abstract, so "fair use" should allow for it.) --FvdP 21:08 Oct 17, 2002 (UTC)

Removed:

The Möbius function μ(n) of these numbers alternately takes values -1 and 1. 41041 is therefore the first Carmichael number for which μ(n) = 1

That property is (almost) trivial by definition of the Moebius function, and there are thousands of such properties. Unless it has a specific importance (fictional example: Wiles's proof of Fermat's last theorem relies on the fact that 41041 is...) it is not worth mentioning.

Removed:

Richard G. E. Pinch also gave and proved an upper bound for C(n), the number of Carmichael numbers less than n.

Without giving C(n) explicitly, that statement tells us exactly nothing. Perhaps somebody can dig up the relevant facts? My quick search didn't turn up anything.
—Herbee 22:04, 2004 Apr 2 (UTC)

Another reason for removing at least the attribution is that I did not prove it: Erdos did ... Richard Pinch 19:27, 31 July 2006 (UTC)

Korselt's Criterion

Could someone move the Korselt's theorem stuff to a new page? (or add a redirect+subheading to this page for Korselt's Criterion and Korselt's Theorem?

As far as I know, the theorem is typically known as 'Korselt's Criterion', by the way.134.173.200.205 (talk) 22:11, 3 April 2008 (UTC)

It's pointless to make a page of the two or so sentences, it would barely make a stub. I've added a redirect from Korselt's criterion. As for "Korselt's theorem", I think it wasn't intended as a name in the article, but as a description ("a theorem by Korselt"). — EJ (talk) 12:17, 4 April 2008 (UTC)

Is the set of Chernik-Carmichael numbers infinite ?

The article doesn't say whether the set of Chernick-Carmichaël numbers of the form (6k + 1)(12k + 1)(18k + 1) is (in)finite. I'd assume it is infinite, by an plausible extension (which I'm just conjecturing, not affirming !) of the theorem on primes in arithmetic progressions. Can someone with access to knowledge/documentation settle the question, and add a mention to the main article ? Of course Chernik numbers would be a lesser interest if there were only a finite set of them... Ninho (talk) 10:06, 11 April 2008 (UTC)

IIRC the question is an open problem, it is not even known whether there are infinitely many Carmichael numbers with a bounded number of prime factors. Notice that the basic question of infinitude of Carmichael numbers was only settled in 1994, so problems of this sort are terribly difficult to solve. — EJ (talk) 15:31, 11 April 2008 (UTC)

Thanks, EJ. When first seing that nice, one parameter formula of Chernik's, I'm sure many readers will assume without further thinking that it yields an infinite number of charmicaels; I would suggest a notice should be added that this is not proven yet. /Done : adding the phrase : "Whether this formula produces an infinite quantity of Carmichael numbers is an open question." Although arguably the openness is also implied in the rest of the article./ As to the question itself, is there no hope for Dirichlet's method to be extended to show that 6k+1, 12k+1 and 18k+1 must be prime simultaneously for an infinite set of k-values ? Pardon my naïveté... Ninho (talk) 08:35, 12 April 2008 (UTC)

I'm not an expert in this area, but I do not see much connection to Dirichlet's theorem. I'd guess that showing that 6k + 1, 12k + 1, 18k + 1 are prime for infinitely many k is rather a problem akin to showing that 2k – 1 and 4k + 1 are prime for infinitely many k (in other words, there are infinitely many Sophie Germain primes), or that 2k – 1 and 2k + 1 are prime for infinitely many k (the twin prime conjecture). — EJ (talk) 10:07, 13 April 2008 (UTC)

OK I take your word it will be very difficult to prove. OTOH, some googling found compiled tables of carmichaels, including the cherniks, over a wide range, and while tables can't proove their infinity, they do suggest even more, viz the observed distribution of Czernikian prime triples looks conform to what would expect on the assumption of statistical independance. Looks reasonable to /conjecture/ their number is infinite, and twin primes as well :=) —Preceding unsigned comment added by Ninho (talk • contribs) 09:14, 15 April 2008 (UTC)

This sort of proposition is an example of Schinzel's hypothesis H, which asserts that any finite collection of polynomials will be infinitely often simultaneously prime unless there is a congruence condition obstructions (for example, n and n+1). Richard Pinch (talk) 06:47, 20 September 2008 (UTC)

A very interesting, very broad, almost frightening, hypothesis indeed ! Thanks.Ninho (talk) 11:34, 3 December 2008 (UTC)

Twin Prime factors of Carmichael numbers

Can Carmichael numbers have twin primes among their factors ? This autoassigned problem I answer in the negative when restricted to 3-prime-factors (I wished to email the problem and short elementary proof to the maintainer of the primepuzzles.net page, but his email form doesn't seem to work. Does someone have his email or is interested in this ? I have no idea if it's new). In the general case (Carmichael numbers with 4 factors or more), inspection of a list shows the result does not hold; on the opposite a fair proportion has twin prime factors, at least among the (relatively) small members of the set. C3 numbers stand apart !

Apologies if this spell was off rules - I've now posted the result and proof to my talk page at Wikipedia. Shall appreciate comments, even the negative ones.Ninho 11:47, 3 December 2008 (UTC)

Korselt's 1899 theorem

The following is attributed to Korselt 1899:

A positive composite integer n is a Carmichael number if and only if n is square-free, and for all prime divisors p of n, it is true that p − 1 divides n − 1.

However, if Carmichael numbers only came to be known as Carmichael numbers in 1910 (see the article), then shouldn't the above be written more like this?:

A positive composite integer n is [a Carmichael number] if and only if n is square-free, and for all prime divisors p of n, it is true that p − 1 divides n − 1.70.112.115.176 17:29, 31 October 2005 (UTC)

Very old comment, but the first wording is fine and standard. Very often people originally state results in different or obscure ways. They later get clarified, notation gets modernized, etc., and later authors are welcome to restate old results in a modern way. If the translation is particularly involved some people add something like "(in modern terminology)", but you're not obligated to. 138.51.117.144 (talk) 23:11, 18 July 2016 (UTC)

Er, if a Carmichael number is defined as given, then the statement "Since Carmichael numbers exist, this primality test cannot be relied upon to prove the primality of a number" should be "Since Carmichael numbers that aren't prime exist, ...". So are Carmichael numbers the numbers given by the property in the definition, or the numbers given by that property which also aren't prime? I'd fix it, but I don't know which way is right. Maybe this is being too picky over wording, but this is a math article, after all. --140.180.128.44 14:25, 5 February 2007 (UTC)

The definition in the article quite explicitly states that Carmichael numbers are composite, so where is the problem? -- EJ 15:29, 5 February 2007 (UTC)

Did Korselt actually miss any examples ?

"Korselt was the first who observed these properties, but he could not find an example. "

This sentence strikes me as extraordinary, and a possible myth. Having come by his criterion, any other guy would have looked for the possibility of examples involving small factors, and the smallest ones are far from being out of reach of a researcher equipped with pencil and paper - even as an exercise in mental calculation it is possible for a moderately gifted individual to find quite a few (admittedly, it helps knowing that small examples do exist beforehand).

Did Korselt explicitly state or give a clue that he could find no examples, in the original paper or later on ? Ninho (talk) 21:08, 19 September 2008 (UTC)

A good question. I have seen this stated in several places, but Dickson's History does not say so. I'll try to find the original reference. Richard Pinch (talk) 06:48, 20 September 2008 (UTC)

Dickson vol. 1 p 93 has the same reference to Korselt's paper. The original paper is just a small paragraph, in response to a question of Gaston Tarry, about the non-existence of weak pseudo-primes in base 2, stated in a book by W. W. Rouse Ball as coming from China ("le problème chinois"). All is on https://archive.org/details/lintermdiairede03lemogoog : the question in vol. 5 (1988) p 266, the response in vol 6 (1999) p 143 (there are responses from others persons from p 142 to p 144). Korselt gives his criterion as a remark, but there is no evidence here that he does not find examples (the only example is a pseudo-prime in base 2, that is response to the question from Tarry). Proz (talk) 18:17, 23 November 2015 (UTC)

The criterion isn't particularly important; he may just not have cared enough to do any computations. Given the above research, I've reworded that part of the article to say Korselt merely did not give any examples, rather than saying he *couldn't*.138.51.117.144 (talk) 23:17, 18 July 2016 (UTC)

In the news

The news media reported some potentially important results involving Carmichael numbers in mid-2016, although the details apparently haven't been published yet.

In the months ahead, keep an eye out for the names Yu Jianchun and Cai Tianxin, perhaps. —Patrug (talk) 17:22, 18 July 2016 (UTC)

http://www.odditycentral.com/news/real-life-good-will-hunting-chinese-delivery-man-discovers-simpler-solution-to-complex-math-problem.html

Looks like a repost of the CNN article. DFH (talk) 18:12, 1 August 2016 (UTC)