Prime

Prime numbers are the fundamental of number theory, stated by the fundamental theorem of arithmetic, that each positive integer except can be decomposed into the product of one or more primes.

The proof of the theorem is intuitive and easy to prove, given a number , you first iterate through the primes less than or equal to , and divide by each primes until they are coprime, repeat the process until is remained. The decomposition is unique otherwise it will be contrary to every number we divide is prime.

In this article, we will not be talking about those we've already learned in elementary school, but the properties of integer modulo with primes and coprime numbers.

Fermat's little theorem

The Fermat's little theorem states that given an positive integer and a prime number , there will always be:

While Fermat hadn't given a proof for that, Euler studied his statement and generalized it into Euler's theorem, which is also applicable to coprime numbers. We will walk through both Fermat's little theorem and Euler's theorem in this article, step by step.

There's a simple proof for the Fermat little theorem, using binomial theorem:

The binomial coefficient , is always divisible by for : is prime and cannot be factorized into number smaller than it, so the binomial coefficient is an integer always containing as one of its factor.

Descending from to with the same methodology, it terminates at , and accumulating back from to will yield , which concludes the proof.

Notice that expression is also equivalent to , so when and are coprime, it is only possible that , so the Fermat's little theorem can also be restated as:

Many people's eyes may be grasped by the lucky coincidence of how prime number appears in the binomial coeffient, forming a divisible factor by the prime number itself. It seems to be a dedicated property for prime number, and is quite acceptable since prime number itself is special in number theory.

And this is how Euler's theory is great, he's shown that both prime number and coprime numbers can have such a relationship, not by lucky coincidence of divisible term, but by destined consequence of repermutation of reduced residue system.

Euler's theorem

The Euler's theorem states that given integer such that and are coprime, there will be

It is common and elegant to use group theory, or properties of the multiplicative group of integers modulo- , to prove the Euler's theorem. But since we've not met the concept of group by now, let's prove it in some homebrew manner.

Reduced residue system

The integers modulo- relation, or congruent relation, is the equivalence relation that partitions integers into partitions, where properties of the equivalence relation holds. And the reduced residue system further more picks partitions that are relatively prime to the divisor out, it is the subset of the quotient set partitioned by congruence.

The size of the reduced residue system of is denoted as , which is a function of called Euler totient function. For prime number , since all numbers less than it will be relatively prime to , . ¹

The is the identity in the reduced residue system. Consider another element from the reduced residue system, so that , which means .

Consider a number in reduced residue system of , according to the Bezout's identity, there must be holds, which means is also in the reduced residue system, , is always invertible, and and are a pair of inverse elements to each other.

The multiply operation of reduced residue system is closed. Taking from the reduced residue system of , since , we just need to so is also relatively prime to . By the properties of coprime we have:

By multiplying them we will get , which is effectively a non-trivial solution for Bezout's identity regarding and , showing they are coprime.

Proof

Now we've known the basic properties of the reduced residue system, and we can jump into the proof.

Let's represent all elements from the reduced residue system as , and choose an element from the reduced residue system. We need to show is a permutation of them, or in other word, forms a bijection.

The transformation is obviosly surjective, since every element could be inverted by , according to invertibility.

For the injectivity of the transformation, please notice that and have the same number of elements, which means mapping different and to will render some of the 's element unmapped, which is a contradiction to surjectivity. This concludes the proof of multiplying by is a mapping that is a bijection.

To prove the theorem, multiply all of the and , and we will get:

Finally, multiply the expression by and we will get:

Thus concludes the proof of the theorem.

The proof of the Euler's theorem shows us it is the algebraic relationships of the elements in reduced residue system that determines the behaviour of integers' power modulo-, which is applicable to both primes and coprime numbers. And this has shed a light on the potential of how group theory will aid us in studying number theory.

Primality test

Determining whether an arbitrary number is prime is prime is a crucial and widely required task for computer. The Fermat's theorem innovates us to use it to judge whether a given number might be prime.

To test, we randomly picks up some numbers , and use them as bases to compute , which could be done quickly using a fast modular exponentiation algorithm. If the value is for all selected , then it is likely for to be prime.

Carmichael number

While the Fermat's little theorem specifies a necessary condition for tested number to be prime, it does not mean all composite numbers does not exhibit such behaviour.

As the Fermat's primality test is kind of probabilistic, an intuitive idea is to expand the range of chosen bases. So the thing remains on how many numbers must be chosen in order to ensure we are getting right answer at a high probability. Being rival to this case, the Carmichael numbers are composite numbers whose witnessing bases are so sparse that we might have to test a proportion of bases in order to detect its compositeness.

A Carmichael number is a number that has the following properties ²:

1. It is square-free, which means for all its prime factors .
2. For all its prime factors , always divides .

Now we will show how such numbers cheat Fermat's primality test. Let's pick some number ranged from to .

Let's iterate through all prime factors of , it is the case that either or is possible.

When , since is also prime, there will be , and since is divisible by , there will also be , so there's holds.

When , obviously there will be holds.

Finally, since is the simple product of all its prime factors, according to the Chinese remainder theorem, there will be:

It would be really bad if you use the Fermat's little theorem in the form of to test 's primality, all numbers ranging from to will be strong liar in such form. Condition will be less severe while using the Fermat's little theorem in the form of .

Since , or divides , when and are coprime we will get:

For the cases that and are not coprime, will yield an answer containing the since modulo operation is also a linear combination of and , rendering as a witness of in this case.

The problem remains as how sparse are the witnesses for Carmichael number's compositeness. This depends on the factorization of a Carmichael number. For instance, is a Carmichael number, if you randomly pick a number, the probability for it to be witness will be , so you have a probability as high as to misjudge as prime each test round. Things might be even more hideous if we encounter some Carmichael number whose prime factors are also large.

Miller-Rabin primality test

Noted that given an odd number, it can always be written as . Any congrunces satisfying the form of could always be furtherly translated info . And when is prime, it must divide exactly one of them.

If divides , then there will be . Please notice we can continue the quadratic decomposition recursively whenever holds.

If divides , then there will be .

Noted that when is prime, it is impossible that . Otherwise there will be , so must divide either or . Since , both of them are in the reduced residue system of , which is a contradiction.

So when is prime, exactly one of the following holds:

1. .
2. .

Its contrapositive statement, given that none of the conditions above is satisfied, is used by the Miller-Rabin primality test to confirm given number 's compositeness. Miller first came up with Miller primality test which is deterministic and relies on the unproven extended Riemann hypothesis. And later Rabin ameliorated it into Miller-Rabin primality test, which is undeterministic but does not relies on Riemann hypothesis.

Compared to the Fermat's primality test, Miller-Rabin's merely adding more conditions (without rationale) is unconvincing and doesn't look appealing to us. We are eager to know whether adding more such conditions increases the chance of encountering some witnesses, and does it provides some mitigation for Carmichael numbers.

Rabin had proved that testing primality of number using the conditions above yields a witness with probability more than , which means we can reach arbitrary confidence after sufficient test of different bases.

However, proving it to be the original requires excessive knowledge of group theory. So we would show the probability to be more than , which is much simpler but still convincing nonetheless.

Suppose is a liar for Miller-Rabin's test. It must be a Fermat's liar in the first place, which requires to be true, so and must be coprime, by the fact that . And according to the Euler's theorem, there will also be .

Suppose is the smallest number such that holds. It is impossible that , otherwise since , there will , which is a contradiction to is the smallest. So obviously must divide both and , which leads to 's dividing .

Let's consider a case that where is prime and . In this case ³, noted that , so , which means must also be true. Like what we have done above, rewrite , and , due to the fact that is a factor of , there must be and divides holds.

Let . Obviously there will be and divides . When since divides , there'll be and turns out to be a liar. When , it requires otherwise will be a witness for 's compositeness. Let , since there will be dividing . Noted that is odd prime (noted that we've eliminated the case of being even numbers before entering the test) so either divides or divides , but not at the same time. So there will be either or . And it is not the case that otherwise it will be a contradiction to is the smallest. Now , and since is odd, there will also be .

So when , inside the reduced residue system of , the sufficient and necessary condition for an element to be Miller-Rabin's liar will be . The problem remains as how large is the portion of these liars relative to the reduced residue system.

Consider an element which is inside the reduced residue system of , there will be . When , , so must divide . When , . So there must be . Noted that , there must be . So there's element from the reduced residue system that is not liar.

Given every liar of , we can construct a witness , according to the fact that , and since multiplying by is a bijection for elements in the reduced residue system, at most of them could be a liar ⁴.

Let's consider another case that , which is the prime factorization of . Please notice that this case conjuncted with the case of which we have discussed cover all cases of composites.

Let , To be a Miller-Rabin's liar in this case, either or must hold. Find and its corresponding such that and . Please notice that since is an odd prime, is relatively prime to by the Bezout's identity, and so such and should always exist.

There's a way to construct witness from . Without losing generality, let's choose a prime power from 's prime factorization so . Since and is coprime, by using Chinese remainder theorem, it's always possible to find such that:

Noted that is relatively prime to and by Bezout's identity, so it is also relatively prime to . Since congrunce is compatible with power, there will be:

So where . Noted that , is a witness of 's compositeness. Meantime there're and , rendering a witness for every liar . Since is in reduced residue system of , multiplying by is a bijection from every liars to witnesses, which also implies no more than of them can be liar.

Conjuncting the conclusion of the two cases above, we've proved that randomly select an element from 's reduced residue system, the possibility of it to be a Miller-Rabin liar is no more than . As is seen from the proof that is just a really coarse estimation, but still gives some idea of how Miller-Rabin's has improved over the Fermat's nonetheless.

So Miller-Rabin's test is truly a randomized algorithm resisting the Carmichael number and yielding a primality test result over given confidence after randomly running the test against enough different bases.