Talk:Carmichael number

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Mid Priority  Field: Number theory

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)

Contents

[edit] "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)

[edit] 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)

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)

[edit] 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)

[edit] 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) Ninho

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) Ninho

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)