20210701, 11:54  #1 
Aug 2002
3×2,837 Posts 
July 2021

20210706, 14:53  #2 
"Ben"
Feb 2007
3,671 Posts 
I've learned some things about Carmichael numbers from researching this puzzle, and unless I've misunderstood something 100 digit primary Carmichael numbers seem to be pretty easy to find. So far the largest I've found is a 620 digit primary solution.

20210706, 22:10  #3 
"Ben"
Feb 2007
3,671 Posts 
A little more optimization and up to a 2470 digit solution. Not searching any more until I hear something from the puzzle admins about whether these solutions are correct.

20210707, 05:33  #4 
Jul 2015
3·11 Posts 
did you also find b
"and b is the largest nontrivial square root of unity modulo n." 
20210707, 13:03  #5 
Feb 2017
Nowhere
2^{2}×3×499 Posts 
I submitted a solution on the 2^{nd} in the suggested format. I had never heard of "primary Carmichael numbers." Apparently a new thing. I learned something!
I only submitted a single example, a primary Carmichael number just greater than 10^100 and called it good. Inspired by this thread, I adjusted my script to find one just greater than 10^620. In theory, my script could find solutions of any size, but in practice it's so mindless it would take a long long time to find a really large solution. 
20210707, 13:26  #6  
"Ben"
Feb 2007
E57_{16} Posts 
Quote:
Quote:


20210811, 11:29  #7 
Feb 2017
Nowhere
2^{2}×3×499 Posts 
I was dissatisfied with the published solution  in particular, the failure to address the question of being primary. Also, the link in the August puzzle to July's solution doesn't work because it wasn't updated when the solution was posted.
So I'm posting my own solution. Solution: The example [1729 = 7*13*19] is suggestive, in that it is the smallest of a well known family of 3factor Carmichael numbers n = p1*p2*p3 where (*) p1 = 6*k + 1, p2 = 12*k + 1, and p3 = 18*k + 1, k = positive integer. It is easily shown that in this case 36*k divides n  1, so that when p1, p2, and p3 are all prime, n satisfies Korselt's criterion, so is a Carmichael number. If p is a prime factor of n, the basep digits of n are those of n/p, with a zero appended. Here we have p2 = 2*p1  1 and p3 = 3*p1  2, so that p2*p3 = 6*p1^2  7*p1 + 2, which may be rewritten 5*p1^2 + (p1  7)*p2 + 2. Since p1 > 5, the basep1 digits are 5, p1  7, and 2; their sum is p1. Similarly, p1 = (p2 +1)/2 and p3 = (3*p2  1)/2, so that p1*p3 = (3*p2^2 + 2*p2  1)/4 = (3*p2 + 1)/4 *p2 + (p2  1)/4; it is easy to see see that (3*p2 + 1)/4 and (p2  1)/4 are integers in [0, p2  1], hence the basep2 digits of n/p2, and their sum is p2. Finally, p1 = (p3 + 2)/3 and p2 = (2*p3 + 1)/3, so p1*p2 = (2*p3^2 + 5*p3 + 2)/9, which may be written (2*p3  2)/9 * p3 + (7*p3 + 2)/9. As before, it is easy to see that (2*p3  2)/9 and (7*p3 + 2) are the basep3 digits of p1*p2, and their sum is p3. Thus, if p1, p2, and p3 as in (*) are all prime, n = p1*p2*p3 is a primary Carmichael number. Finding a k for which 6*k + 1, 12*k + 1, and 18*k + 1 are all prime such that n > 10^100, computing the square roots of 1 mod n, and finding the largest of these that is not 1 or 1 (mod n) is then a routine matter. Code:
? { t=ceil((10^100/6/12/18)^(1/3)); d=5*7*11*13*17*19*23*29*31*37; for(k=t,t+1000000, p1=6*k+1; p2=12*k+1; p3=18*k+1; n=p1*p2*p3;if(gcd(n,d)==1&&ispseudoprime(p1)&&ispseudoprime(p2)&&ispseudoprime(p3), t=k; break)); p1=6*t+1; p2=12*t+1; p3=18*t+1; s=1; for(i=0,1, for(j=0,1, for(k=0,1, b=lift(chinese([Mod((1)^i,p1),Mod((1)^j,p2),Mod((1)^k,p3)])); if(b>s&&b<n1,s=b)))); print(n); print(p1,", ",p2,", ",p3); print(s) } 10000000000000000000000000000405929367865700162694655745350302085810080768959837103297359653235421369 1185631101496687602002051540762347, 2371262202993375204004103081524693, 3556893304490062806006154622287039 10000000000000000000000000000405920933539047145202227288252787796834022398216461136785946154423067343 ? 
20210811, 18:01  #8 
May 2013
Germany
97 Posts 
Is it possible to "compute" p2*p31 as smallest and n(p2*p31) as largest nontrivial root?
Last fiddled with by Alfred on 20210811 at 18:02 
20210812, 15:03  #9  
Feb 2017
Nowhere
1011101100100_{2} Posts 
Quote:
I believe so, yes. With p1, p2, and p3 defined as above, obviously A = p2*p3  1 is congruent to 1 (mod p2 and mod p3), and is easily shown to be congruent to 1 (mod p1). The "trivial" square roots of 1 are congruent to 1, or congruent to 1 modulo all of p1, p2, and p3. Scribbling with paper and pencil, I found that B = 8*p1*p3 + 1 is congruent to 1 (mod p1 and mod p3) and congruent to 1 (mod p2). Similarly, C = 9*p1*p2  1 is congruent to 1 (mod p1 and mod p2) but congruent to 1 (mod p3). Clearly 1 and n1; A and n  A; B and n  B; and C and n  C are all the square roots of unity (mod n). Now A < n  A, B < n  B, and C < n  C. Also, from the formulas it is clear that A < B and A < C. EDIT: I was a bit careless. The inequality B < n  B is only valid if p2 > 16, which is not the case with k = 1 (p1 = 7, p2 = 13, p3 = 19). Last fiddled with by Dr Sardonicus on 20210812 at 17:47 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
July 2020  tgan  Puzzles  6  20200831 11:30 
July 2016  Xyzzy  Puzzles  4  20160806 22:51 
July 2015  Xyzzy  Puzzles  16  20150819 16:13 
July 2014  Xyzzy  Puzzles  6  20141102 19:05 
Happy July 4th  LaurV  Lounge  8  20120706 00:13 