About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
July 2021 - Challenge
A simple primality test is based on Fermat's little theorem: If is prime,
. Thus, by choosing a random
and computing
in that group, one can sometimes detect that
is composite when the result is not 1.
However, the test always fails for Carmichael numbers, composite numbers that satisfy for every
. The Miller-Rabin primality test addresses this by building on the Fermat test and adding another check during the computation of
: square roots of unity. If
, then
is a square root of unity modulo
. For every
, we have the trivial roots
. Additional roots exist only if
is composite.
The smallest Carmichael number is . The largest non-trivial square root of unity modulo 561 is 494.
Your goal: Find a Carmichael number with at least 100 digits and the largest non-trivial square root of unity modulo
. 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 with the following property: For every prime divisor
of
, the digits in the base-
representation of
sum to
(it can be shown that this property implies
must be a Carmichael number).
- For example, Ramanujan's taxicab number
- 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)