Connect with us:

# Ponder This

Welcome to our monthly puzzles.
You are cordially invited to match wits with some of the best minds in IBM Research.

## July 2021 - Solution

July 2021 Challenge

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