Ponder This Challenge - July 2021 - Square roots of unity modulo Carmichael numbers

A simple primality test is based on Fermat's little theorem: If $n$ is prime, $a^{n-1}\equiv 1(\text{mod }n)$. Thus, by choosing a random $a\in\mathbb{Z}^*_n$ and computing $a^{n-1}$ in that group, one can sometimes detect that $n$ is composite when the result is not 1.

However, the test always fails for Carmichael numbers, composite numbers that satisfy $a^{n-1}\equiv 1(\text{mod }n)$ for every $a\in\mathbb{Z}^*_n$. The Miller-Rabin primality test addresses this by building on the Fermat test and adding another check during the computation of $a^{n-1}$: square roots of unity. If $b^2\equiv 1 (\text{mod }n)$, then $b$ is a square root of unity modulo $n$. For every $n$, we have the trivial roots $1, n-1$. Additional roots exist only if $n$ is composite.

The smallest Carmichael number is $561=3\cdot 11\cdot 17$. The largest non-trivial square root of unity modulo 561 is 494.

Your goal: Find a Carmichael number $n$ with at least 100 digits and the largest non-trivial square root of unity modulo $n$. Supply your answer in the following format:

Where n is the Carmichael number, p1, p2, ..., pn are all the prime factors of n, and b is the largest non-trivial square root of unity modulo n.

A bonus "*" will be given for finding a solution that is also a primary Carmichael number:
Primary Carmichael numbers are numbers $n$ with the following property: For every prime divisor $p$ of $n$, the digits in the base-$p$ representation of $n$ sum to $p$ (it can be shown that this property implies $n$ must be a Carmichael number).

For example, Ramanujan's taxicab number $1729=7\cdot13\cdot19$ can be written in the following bases:* 5020 in base 7, (5+0+2+0=7)

• A30 in base 13, (10+3+0=3)
• 4F0 in base 19 (4+15+0=19) Thus it is an example of a primary Carmichael number.

Solution

• Click here to view the solution

  A simple way to determine if a given number is a Carmichael number is by using Korselt's criterion: $n$ is Carmichael if it is square-free and for every prime divisor $p$ of $n$, $p-1$ divides $n-1$. This allows us to easily determine if a number is Carmichael (and primary Carmichael) given its factorization.

  A simple method by Chernick to generate Carmichael primes is as follows: if for any $k$ we have that $6k+1, 12k+1,18k+1$ are all primes, then their product is Carmichael.

  To generate the maximal nontrivial root of unity, one can use the Chinese remainder theorem to compute all roots, since for a prime the roots are $\pm 1$ then the solution of the system $x\equiv_p a_p$ where for every factor $p$, we have that $a_p$ is one of the roots of unity modulo $p$.

  A sample solution found in this way:
  1296000000000000000000000000002498627160000000000000000000001605745289271600000000000000000343977948543716641
  600000000000000000000000000000385591, 1200000000000000000000000000000771181, 1800000000000000000000000000001156771
  1296000000000000000000000000002498625000000000000000000000001605742513020600000000000000000343977056463900091

Solvers

• *Lazar Ilic (30/6/2021 10:36 PM IDT)
• *Bert Dobbelaere (1/7/2021 1:18 AM IDT)
• *Bertram Felgenhauer (1/7/2021 3:28 AM IDT)
• *Uoti Urpala (1/7/2021 3:41 AM IDT)
• *Sean Egan (1/7/2021 4:18 AM IDT)
• *Keith Schneider (1/7/2021 4:42 AM IDT)
• *Franciraldo Cavalcante (1/7/2021 9:13 AM IDT)
• *Alper Halbutogullari (1/7/2021 7:46 AM IDT)
• *Paul Revenant (1/7/2021 12:00 PM IDT)
• *Dan Dima (1/7/2021 3:48 PM IDT)
• *Giorgos Kalogeropoulos (1/7/2021 4:34 PM IDT)
• *Dominik Reichl (1/7/2021 5:45 PM IDT)
• *Andreas Stiller (1/7/2021 5:45 PM IDT)
• *Kennedy (2/7/2021 12:35 AM IDT)
• *David Greer (2/7/2021 1:41 AM IDT)
• *Dieter Beckerle (2/7/2021 9:05 AM IDT)
• *Daniel Chong Jyh Tar (2/7/2021 9:03 PM IDT)
• *Kurt Foster (3/7/2021 4:43 AM IDT)
• *Yuping Luo (3/7/2021 10:17 AM IDT)
• Hakan Summakoğlu (3/7/2021 1:08 PM IDT)
• *Raymond Lo (3/7/2021 8:40 PM IDT)
• *Guillaume Escamocher (3/7/2021 9:07 PM IDT)
• *Michael Liepelt (4/7/2021 2:03 PM IDT)
• *Walter Schmidt (4/7/2021 4:36 PM IDT)
• *JJ Rabeyrin (4/7/2021 7:14 PM IDT)
• Arthur Vause (4/7/2021 7:31 PM IDT)
• *Tomer Vromen (4/7/2021 7:42 PM IDT)
• *Wang Longbu (5/7/2021 6:02 AM IDT)
• *Luke Pebody (5/7/2021 9:57 AM IDT)
• *Tongyang Song (5/7/2021 11:53 AM IDT)
• *Michael Schuresko (5/7/2021 10:28 PM IDT)
• *George Wahid (6/7/2021 12:07 AM IDT)
• *Tim Walters (6/7/2021 2:41 AM IDT)
• *Marco Bellocchi (6/7/2021 2:47 PM IDT)
• *Benjamin Buhrow (6/7/2021 5:46 PM IDT)
• *Thomas Pircher (7/7/2021 1:20 AM IDT)
• Vladimir Volevich (8/7/2021 12:21 PM IDT)
• *Benjamin Lui (9/7/2021 8:14 PM IDT)
• *Joaquim Carrapa (10/7/2021 12:19 PM IDT)
• *Nyles Heise (11/7/2021 3:59 AM IDT)
• *Fabio Michele Negroni (11/7/2021 6:45 PM IDT)
• *Todd Will (11/7/2021 8:13 PM IDT)
• *Joaquim Carrapa (11/7/2021 9:56 PM IDT)
• *Reiner Martin (12/7/2021 2:25 AM IDT)
• *Alfred Reich (12/7/2021 9:46 AM IDT)
• *Liubing Yu (12/7/2021 11:42 PM IDT)
• *Tamir Ganor & Shouky Dan (13/7/2021 11:23 AM IDT)
• Prashant Wankhede (14/7/2021 2:55 AM IDT)
• *Thomas Egense (14/7/2021 9:43 PM IDT)
• *Vladimir Volevich (15/7/2021 8:34 PM IDT)
• *Albert Stadler (16/7/2021 12:13 AM IDT)
• *Soham Sud (16/7/2021 11:53 AM IDT)
• *Govind Jujare (17/7/2021 4:49 AM IDT)
• *Harald Bögeholz (17/7/2021 10:02 AM IDT)
• *Latchezar Christov (17/7/2021 1:28 PM IDT)
• *Clive Tong (18/7/2021 2:42 PM IDT)
• *Daniel Bitin (20/7/2021 12:19 AM IDT)
• *Andreas Knüpfer (20/7/2021 11:29 PM IDT)
• *Yusuf AttarBashi (20/7/2021 1:21 PM IDT)
• *Ahmet Yüksel (20/7/2021 2:40 PM IDT)
• *Sanandan Swaminathan (23/7/2021 5:22 AM IDT)
• *Eran Vered (23/7/2021 6:52 PM IDT)
• *Kang Jin Cho (25/7/2021 7:45 PM IDT)
• Reda Kebbaj (26/7/2021 10:47 AM IDT)
• *Daniel Scheinerman (26/7/2021 6:12 PM IDT)
• *Jose Coelho (28/7/2021 10:22 PM IDT)
• *James Muir (31/7/2021 7:14 AM IDT)
• *Li Li (1/8/2021 10:00 AM IDT)
• Chiho Haruta (1/8/2021 5:15 PM IDT)
• Radu-Alexandru Todor (2/8/2021 3:41 AM IDT)
• *Oscar Volpatti (2/8/2021 7:36 AM IDT)
• *Gürkan Koray Akpınar (3/8/2021 12:13 AM IDT)