July 2021 - Challenge
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:
n p1, p2, ..., pn b
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.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
30/06/2021 @ 12:00 PM EST
Solution:
04/08/2021 @ 12:00 PM EST
List Updated:
03/08/2021 @ 12:00 PM EST
People who answered correctly:
*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)