mersenneforum.org July 2021
 Register FAQ Search Today's Posts Mark Forums Read

 2021-07-01, 11:54 #1 Xyzzy     Aug 2002 2×3×5×277 Posts July 2021
 2021-07-06, 14:53 #2 bsquared     "Ben" Feb 2007 DFA16 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.
2021-07-06, 22:10   #3
bsquared

"Ben"
Feb 2007

2·1,789 Posts

Quote:
 Originally Posted by bsquared 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.
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.

 2021-07-07, 05:33 #4 tgan   Jul 2015 22×7 Posts did you also find b "and b is the largest non-trivial square root of unity modulo n."
 2021-07-07, 13:03 #5 Dr Sardonicus     Feb 2017 Nowhere 137816 Posts I submitted a solution on the 2nd 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.
2021-07-07, 13:26   #6
bsquared

"Ben"
Feb 2007

2×1,789 Posts

Quote:
 Originally Posted by tgan did you also find b "and b is the largest non-trivial square root of unity modulo n."
Yes I'm finding them by construction so I know the factors, and knowing those it's straightforward to find the non-trivial roots of unity.

Quote:
 Originally Posted by Dr Sardonicus I submitted a solution on the 2nd 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.
Yeah I've also learned some things - the mark of a good puzzle. Also I lied earlier and kept my script running over night. This morning I saw that it found a solution of size 4936 digits.

 2021-08-11, 11:29 #7 Dr Sardonicus     Feb 2017 Nowhere 10011011110002 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 3-factor 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 base-p 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 base-p1 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 base-p2 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 base-p3 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
 2021-08-11, 18:01 #8 Alfred     May 2013 Germany 3×29 Posts Is it possible to "compute" p2*p3-1 as smallest and n-(p2*p3-1) as largest non-trivial root? Last fiddled with by Alfred on 2021-08-11 at 18:02
2021-08-12, 15:03   #9
Dr Sardonicus

Feb 2017
Nowhere

498410 Posts

Quote:
 Originally Posted by Alfred Is it possible to "compute" p2*p3-1 as smallest and n-(p2*p3-1) as largest non-trivial root?

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 n-1; 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 2021-08-12 at 17:47

 Similar Threads Thread Thread Starter Forum Replies Last Post tgan Puzzles 6 2020-08-31 11:30 Xyzzy Puzzles 4 2016-08-06 22:51 Xyzzy Puzzles 16 2015-08-19 16:13 Xyzzy Puzzles 6 2014-11-02 19:05 LaurV Lounge 8 2012-07-06 00:13

All times are UTC. The time now is 18:03.

Wed Oct 20 18:03:30 UTC 2021 up 89 days, 12:32, 0 users, load averages: 0.90, 1.15, 1.16