ntt@dciem.UUCP (Mark Brader) (05/09/84)
I like George Fisher's calling 1729 "Ramanujan's Number"! Incidentally, some fun is had with the story behind this in Hofstadter's "Godel, Escher, Bach: An Eternal Golden Braid". I'll say no more here. But the really interesting thing about 1729 is that in addition to being expressible as the sum of two cubes in two different ways, it has ANOTHER very rare property. It is a Carmichael number. Let F(m,n) = (m^n - m) % n, where ^ is exponentiation and % is modulus. Then if n is prime, F(m,n)=0 for all m. [Fermat.] Well, it turns out that the converse is also true for MOST numbers m and n. That is, if F(m,n)=0, n is USUALLY prime. If it isn't, it is called a pseudoprime to the base m. If n is composite but F(m,n)=0 for all m, that is, if n is a pseudoprime to all bases, then n is called a Carmichael number, after R. D. Carmichael. The above is from an article in Scientific American by Carl Pomerance, which was in the December 1982 issue. The article casually mentions 1729 as an example of a Carmichael number without saying why that example was picked. Both examples of Carmichael numbers in the article had exactly 3 prime factors. I wrote a program to find all the Carmichael numbers up to 2^16, and factorize them, to see if the pattern continued. Results: 561 = 3x11x17 1105 = 5x13x17 1729 = 7x13x19 2465 = 5x17x29 2821 = 7x13x31 6601 = 7x23x41 8911 = 7x19x67 10585 = 5x29x73 15841 = 7x31x73 29341 = 13x37x61 41041 = 7x11x13x41 Mark Brader
tan@iwu1d.UUCP (William Tanenbaum) (05/10/84)
I have a question for Mark Brader or anyone else. I always thought that Fermat's theorem (n to the p'th power is equal to n modulo p for any n if p is a prime) was THE fast way for testing a large number for primality. In other words, if p is chosen composite, Fermat's theorem fails for some n. Now we are told that there are some composite values of p (Carmichael numbers) for which Fermat's theorem always holds. Ok, now will someone tell me how to quickly test a large number for primality. There must be such a test, or the public key cryptography system based on factoring large numbers would not work. What am I missing?
gmf@uvacs.UUCP (05/11/84)
>> I like George Fisher's calling 1729 "Ramanujan's Number"!
Thanks on behalf of the shades of Ramanujan and Hardy. I'll
look up the reference in Hofstadter (spelling?). But my
name is Gordon, not George!
Gordon Fisher