4 ms·
Consider n = 1729 = 7 * 13 * 19. (n-1)/2 = 864 = 2^5 * 3^3. For any value 0 < a < n, a^((n-1)/2) = (a^6)^144 = 1^144 = 1 mod 7. For any value 0 < a < n, a^((
by cperciva 15y ago
Consider n = 1729 = 7 * 13 * 19. (n-1)/2 = 864 = 2^5 * 3^3.
For any value 0 < a < n, a^((n-1)/2) = (a^6)^144 = 1^144 = 1 mod 7.
For any value 0 < a < n, a^((n-1)/2) = (a^12)^72 = 1^72 = 1 mod 13.
For any value 0 < a < n, a^((n-1)/2) = (a^18)^48 = 1^48 = 1 mod 19.
Thus 1729 will pass the Lehmann test for all a. (Unsurprisingly 1729 is a Carmichael number; not all Carmichael numbers will pass all Lehmann tests, but any number which passes all Lehmann tests will be Carmichael.)
- cperciva 15y agoAnd this gives us an infinite-under-random-primes class, too: If 12n+7, 24n+13, and 36n+19 are all primes, then their product will pass all Lehmann tests. I'm pretty sure that the Alford-Granville-Pomerance proof of n^(2/7) Carmichael numbers can be extended to give the same order result for "Lehmann-Carmichael" numbers, but I'm not going to do it at 5:30 AM when I'm struggling with a 102F fever.
- dpkendal 15y agoThanks! However, I'm not quite convinced. I ran the given Scheme implementation with k=10000 and it correctly reported all the numbers at http://www.kobepharma-u.ac.jp/~math/notes/note02.html http://www.kobepharma-u.ac.jp/~math/notes/note02.html less than 4294967087 as composite. (4294967087 is the largest random number Racket can give.) However, running it with k=50 gave a random set of them each time. So perhaps the probability data I gave was not right.
- cperciva 15y agoI can't tell you what your code is doing wrong, but I promise 1729 should pass the test you described. EDIT: And of course I forgot about non-relatively-prime values. But those are asymptotically sparse; you're seeing a random set of pseudoprimes for k=50 because with that many trials you have a good chance of catching small primes, but for larger Carmichael numbers you'll need a very large number of trials to get good odds.
- jgeralnik 15y agoThe calculations you described are wrong. If a is a multiple of 7 (or 13 or 19), then (a^6)^144 = (0^6)^144 = 0 mod 7. We can confirm this (using python): >>> (7864)%1729 742L
- lbolla 15y agoConsider n = 1729. Pick a = 1722. a^[(n-1)÷2] mod n = 742 Therefore 1729 is composite. The test seems to hold, here.
- shasta 15y agoLooks like a good proof that any 'a' relatively prime to 7, 13 and 19 should pass the test. Why don't you try a=7 and see what happens?
- deleted 15y ago[deleted]
- lisper 15y ago? (expt-mod-n 7 (/ (1- 1729) 2) 1729) 742