CHAPTER 4

On the history of the problem of recognizing prime numbers by two sided theorem in particular Wilsonís theorem and its consequences


4.1. Wilsonís theorem

In order to a non-one natural number "m>1" be prime, the necessary and sufficient condition is that "m" aliquot (m-1)

Proof. At first, we prove theorem inverse. We suppose that

†††††††††††† (1)

If "m" is not prime number, a natural number like "d" is one of numbers. d| (m-1)! . In other words, according to the thesis . So, according to (1), it is impossible. Now, we conclude Wilsonís theorem from Dirichletís theorem.

4.1.1. Lemma

Suppose that "p" is odd prime number and. If a number like "b" exists so that †then, congruence †has two non- congruent answers whit module "p" exactly.

Proof. At least two non- congruent answers exists for congruence. Because:

,

For we show that congruence hasnít another answers except these two answers. For this purpose suppose that. Therefore . So then †or . In first case is †and in second case is:

.

4.1.2. Dirichletís theorem (1828)

†Suppose that "" be prime number and If congruence hasnít answered, then and if has answer.

Proof. If "", then assertion is obvious. So suppose "" is prime number. According to theorem, if , then there will be an individual number "n", so that 1 and . Now, we call number "m" and "n" as corresponding. If hasnít answer, then for corresponding numbers "m" and "n" we will have . Therefore, we can classify the integer numbers in the interval "1" up to to couples of corresponding numbers. Multiplication of all these corresponding numbers is congruent with †to module "p" and obviously it is also congruent with. Therefore . If the congruence †is solvable so there is an answer like "b" that "".

Another answer of this congruence is. Now we consider †as residual number. It is obvious that these †number, arenít answers for congruence. Therefore we can convert them to corresponding pairs.

Multiplication of these pairs is congruent to module "p" with and, so:

We see that grand result of Dirichlet's theorem is Wilsonís theorem. In 1771, Lagrange presented a very complicated proof of Wilsonís theorem. But Wilsonís theorem is obtained simply from theorem (4.1.2).

4.1.3. Wilsonís theorem

If "p" be prime number, then ""

Proof. In (4.1.2) theorem we set, especially has answer. So:

Therefore, Wilsonís theorem is a test for primality of considered number.

Although this test is unusable, because †is a very big number.

4.1.4 Euler's test

†Consider that "p" be prime and. So congruence †is (is not) solvable

 

if:

Proof. Consider that congruence has answer. Therefore, according to Wilsonís theorem:

†† ;††

Now, factorize result is obtained by multiplication of both side in "Ė1". If congruence hasnít answer, proof it the same.

4.2. Remarks concerning Wilsonís theorem and
its converse and corollaries†

I. First time, Werring in his book "thoughts in algebra" (1770) concerned theorem to sir john Wilson (1741-1793), so this theorem is known as Wilsonís theorem Although Leibniz had said an equivalent assertion. The inverse of theorem was propounded by Lagrange (1771) who also proved.

II. Wilson's theorem gives a simple criterion for investigation the investigating the primality of non-one natural number "m". It is enough to identify that is divisible by "m" or not. But this criterion has no practical advantage. Because †in crease with "m", rapidly.

III. According to Wilson's theorem, for each prime number "p" number is a natural number. Every prime number like "p" so that is a natural number, has called as a Wilsonís prime number. By testing, itís clear that only 5, 13, 563 are Wilsonís prime numbers among prime numbers:

†††††††††††††††††††††††


4.3. Corollaries of Wilsonís theorem

4.3.1. Example 1

If "p" is a prime number and , then:

Proof. Congruence (1) is established for †by Wilsonís theorem and it is provocations for p=2.

We suppose that and congruent are in module "p". Since, so:

.

According to and Wilsonís theorem:

††††††††††† .

4.3.2. Benefit

Suppose that "p" is an odd prime number. Order (1) in last example results for :

††††††††††††† (2)

So, if "p" be †or †then:

†† ()†††††† (3)

††† ()†††† (4)

For example:

†††† †† ()

4.3.3. Example

If and only if odd prime number "p" to be in form of "" then.

4.3.4. Example

†The number of natural numbers like "n" that †is composite for them is infinite.

4.3.5 Example

If †and , then "m" is composite. Conversely, if "m" is composite and distinguished from 4, it adapts in (*).

4.3.6. Liouvilleís theorem

If be prime number and greater than "5", for every natural number of :

††††††† (5)

4.3.7. Leibnizís theorem

The condition of necessary and sufficient in order that natural number of †be prime:

†††††††††† (6)

4.3.8. Remark

If multiply expression of †in the two side relation (6), then to obtain Wilson's theorem:

†††† ;†††† ††††††††††††(7)

Here, we present some determinate function formula by Wilson's theorem:

4.3.9 Remark

According to Wilsonís theorem, supposing that "k" is an integer number, for every †and :

†††††††††† (5)

It is necessary to mention that we can build a lot of identification functions by using the Wilsonís theorem, that for example, we present one of them:

[1]†††††††† (6)

(: Number integer part)

4.3.10. Explanation

By Wilsonís theorem even can not testing number "100001" limit of †defines in below form:

††††††††††† (11)

Of course, we sow important results of this theorem. Very mathematicians presented a lot of theorems and testing for characteristic of prime numbers that we will attempt which showing on the history of obtained results.

Here, with present other formula for characteristic of numbers that very interesting and it express by Eulerís arithmetic function namely we follow subject:

We can determine number †by below determinant:

 

 

 

 

 

 

 

4.3.11. Explanation

In these functions number ofexist. It is obvious that working with it is impossible and even for a number near to, it is also unfaultable. For this reason, these identification functions canít be useful in real and in fact we can use them to present pure theories, because for example the number" 69!" is greater than †(a 99 digits number).

4.4. Some of if theorems for recognizing prime numbers

4.4.1. Lemma

†The congruence is establish for every prime value of "n" and no natural composite number adapts in that , except of 4, 6, and 22.

4.4.2. Subbarao`s Theorem (1974)

If, then "n" is a prime number, if and only if :

4.4.3 Lemma

If "p" is a prime number then for every natural number "n":

4.4.4. Theorem

†If and only if natural number †to be prime number then for every natural number "n", so that :

4.4.5. Theorem

†If and only if natural number †to be prime number then for every natural number "n":

4.4.6. Introduction to Mann and shanks criterion for primality

At first we express this interesting criterion with language which its discoverers said and then by mathematics language as a theorem.

In Pascal mathematical triangle, we transfer every row two cell toward right, so that the coefficients in "n" the row, namely the numbers:

Start from "2n" column and finish in "3n" column. Then mentioned triangle changes some part of it is shown below:

 

††††††† k

† n

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

0

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

1

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2

 

 

 

 

1

2

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

1

3

3

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

 

1

4

6

4

1

 

 

 

 

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

1

5

10

10

5

1

 

 

 

 

 

 

 

 

6

 

 

 

 

 

 

 

 

 

 

 

 

1

6

15

20

15

6

1

 

 

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

7

21

35

35

21

7

1

 

 

8

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

8

28

56

70

56

28

8

9

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

9

36

84

126

126

10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

10

45

120

11

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

11

 

In this new table, in "n" row, entries which are divisible by "n", has been printed in bold letters. Like "1" and "1" in row "1" and "2" in row "2", "3" and "3" in row "3" and etc.

4.4.7. Theorem

†If and only if the numbers of column "1" in above table to be prime then all coefficients this column, become printed in bold letters. According to the structure of the table, only and only an entry of "n" row is in "k" column that. In other word only and only an entry of "n" row is in a specific "k" column when .

4.4.8. Theorem (Mann and Shanks)

†If and only if for every non-one natural number "k" to be prime number, then for every "n" ():

4.4.9. Theorem (Montferrier)

†If "N" is odd and greater than 9 and if and only if "N" is prime number then below numbers:

arenít perfect square.

Because, it is obvious:

.

4.4.10. Eulerís method

†Some numbers are representable as sum of two perfect squires in two different ways. For example:

representations which their difference is just in arranging of factors arenít distinct. We can factorization these numbers to multiplication of two factors. Fernekle and Mersenne discovered this thought but widely. Apparently we express solution of factorization problem we say some primary observation.

I. necessary condition for an odd number to be sum of two squares is that it be in "" form.

II. We consider that††††††††

†††† (1)

If †then †repeating the above reasoning relation (1) will result a relation like and.

 

III. If equality (1) is established and †but, then, †so: .

4.4.11. Theorem

†Every natural number is composite if it has two different representations of sum of two squares.

Also:

So:††††

4.4.12. Remark

†The mentioned decomposition method in above theorem is Eulerís method. For using in decomposition of an odd number like "N", at first we must sure that this number is in the form of "". (For example:).

Because If "", then "".

For example:

.

Attention. Prime numbers which are in form of"" aren't present in sum of two square.

4.4.13. Remark

All of numbers which are in form of "" are composite except of 5. Because

So, "" may be prime number only when one of below equalities is established:

I) †††††††††,††††††††† II)

It is resulted from (1) that †and in this case †is equal to "5" as a prime number. And it is resulted from (2) that and †that is a composite number.

4.4.14. Theorem

†For every two natural numbers "a" and "b" and every prime number "p", has just one representation as:

.

4.5. Factorization of composite numbers

4.5.1. Example

†The number 16000001 which is equal to 10402+38602 is decomposable to multiplication of two factors or multiplication of three factors, because:

4.5.2.

If we suppose that †so that "a", "b", "c" and "d" are natural numbers and †then it is possible to prove that If "", then "".

4.5.3.

According to and two mentioned factorization be distinct, so we can prove:

I)

II)

4.5.4.

†It is clear that multiplication of two numbers in "" form is: †††††††† †††††††††††

Number "N" is convertible to different forms namely "" and "" that, so we can prove:

†For example, we can convert the number 4361 to "" and we can factorization it.

4.5.5. Attention

Now, dispense with expression another ways and ways can be useful for identification "N", comparatively greater number.

Now we express certain solution of identification number problem by identification formula.

 



*. These identification functions have been proposed by the author.