 mersenneforum.org July 2021
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2021-07-01, 11:54 #1 Xyzzy   Aug 2002 3×2,837 Posts July 2021   2021-07-06, 14:53 #2 bsquared   "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.   2021-07-06, 22:10   #3
bsquared

"Ben"
Feb 2007

3,671 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 3·11 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 22×3×499 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

E5716 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 22×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 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 97 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

10111011001002 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  Thread Tools Show Printable Version Email this Page 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 04:53.

Sat Oct 1 04:53:49 UTC 2022 up 44 days, 2:22, 0 users, load averages: 1.53, 1.33, 1.20

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔