Question

Imagine I chose 10-digit prime numbers p,q and r, such that n=pqr happened to be a Carmichael number. Write down an exact formula for the probability that a random a∈ {0,1, . . . , n−1} detects the compositeness of n when used in Fermat’s compositeness test. That is, how many of these a fail to satisfy a^(n−1)≡1 modn. Show that the probability that a random a will detect the compositeness of n is less than 1 in a billion

Answer 1