How can we know if a number is prime?
To Fernanda
There are two methods — that I am aware of — to test if a number is prime, I am going to show you both of them. Both of them have their bad side and their good side. Perhaps using both of them in conjuction will help to identify easier weather a number is prime or not.
The first method is what is called “Fermat’s Little Theorem” which I have made a post about but I will prove it here again too so that you can have a better idea of it. The problem with this method is that it does not only work with prime numbers but it is easier to calculate than the other one.
The second method is what is called “Wilson’s Theorem” which works only for prime numbers, but it becomes hyper exponentially harder to use it as the numbers get large.
First I will show and prove the first method and use it to prove the second one. The theorem states that if p is a prime number and n a positive integer, then:
For example we can say n=4 and p=3, then, we have that:
And as you can see clearly, 60 is a multiple of 3. Now as for the proof of this I will show a quite easy one to understand. We can clearly see that n, 2n, 3n, 4n, 5n, …, (p-1)n are going to form a system of residues with regards to p, that are going to be some reordering of 1,2,3,4,5,…,p-1 if p not a prime factor of n, thus, if we were to multiply all of them out its modularity regarding p, is going to be just the (p-1)! because it will just be the multiplication of all of these numbers, such that:
Thus we have proven for when p is not a prime factor of n. Now, clearly, when p is a prime factor of n, it is obvious that nᵖ-n is going to be divisible by p as well. Thus we have proven the first method, which as you can see will work for prime numbers, but it is not necessary that the number p has to be a prime number for it to hold, there are some other cases for which it will hold of which I will not show here.
Now, for the second method which is called “Wilson’s Theorem” says that if and only if p is a prime number, (p-1)!+1 is a multiple of p. To prove this is not so hard as well, if p is composite, then the gcd((p-1)!,p)>1 so it cannot happen that (p-1)!+1 is a multiple of p, because it will not be divisible by any of the numbers <p. But when it is a prime number, we can see that for all numbers a in {2,3,…,p-2}, there will be another number among them a* such that aa*, and this number will be unique. Because of that, we can see that the multiplication of all of the numbers 2,3,…,p-2 will result in a number with residue 1 modulo p because they will al have an inverse. Thus:
Which thus proves the theorem. This is a quite usual proof given in most textbooks actually. Now, as you can see the factorial grows astronomically fast (but not as much as aₙ which is a sequence I show on a post in MatRel). As you can see, both of these methods have their problems, and they are somewhat of brothers to eachother (so much so that there are some proofs of Wilson’s Theorem that uses Fermat’s Little Theorem).
Soli Deo Gloria
