Math Study | Takezaki's Math Study

Abstruct

Based on the axiomatic fact that any composite number is a product of two integers, I have found a new primality test and prime factorization of integer which can simply be done solely by multiplication (hereinafter called “Primality Test by Multiplication”). Unlike the well-known Sieve of Eratosthenes, trial division, Miller-Rabin primality test (probabilistic primality tests) and the other primality tests, “Primality Test by Multiplication” is a simple, less laborious and extremely timesaving primality test because of using solely multiplication.

I have found that there can be determined all prime numbers originally existing at given numerical range between 2 and an integer 2N by use of a multiplication table made of the products of each of the integers from 2 to a given integer N multiplied by each of the integers from 2 to an integer L nearest to and smaller than $\sqrt{2N}$ (the intiger L ≤ $\sqrt{2N}$ ). In this multiplication table (from 2×2 to N×an integer L), there appear without any exception all composite numbers originally existing at the range between 4 and 2N, while integers not appearing in this table are all prime numbers originally existing at the range between 4 and 2N.

With respect to prime factorization, it goes without saying that any composite number appearing in the multiplication table is a product of known multiplier and multiplicand, which means that both of multiplier and multiplicand are factors of the composite number. These factors of the composite number are automatically factorized into a product of prime numbers by tracing back to its multiplier and multiplicand until each of the multiplier and multiplicand reaches respective prime numbers by use of the multiplication table.

Detailed Explanation

1. Primality Test and Prime Factorization by "the Primality Test by Multiplication" for integers in series

For convenience, a multiplication table made of products of each integer (i) multiplied by each integer (j) is hereinafter called P_ij , where the integer (i) is natural number 2,3,4,5,6,7,・・・・a given integer N in series and the integer (j) is natural number 2,3,4,5,6,7,・・・・N in series. Therefore, the familiar and well-known multiplication table showing the products of each of the integers from 1 to 12 with each of the integers from 1 to 12 is indicated as P_ij (i=1~12, and j=1~12).

“Primality Test by Multiplication” enable us to find prime numbers and at the same time, give even prime factorization of integer solely by multiplication. For easy explanation taking the well-known multiplication table P_ij (i=2~12, and j=2~12) as a simple example, there appear all composite numbers, that is, 4,6,8,9,10,12,14,15,16,18,20,21,22,24 while 5,7,11,13,17,19,23 do not appear in the multiplication table above. It reaches conclusion that in the well-known multiplication table above, integers 4,6,8,9,10,12,14,15,16,18,20,21,22,24 are all of composite numbers and 5,7,11,13,17,19,23 are all of prime numbers originally existing within the range of 2 to 24.

The abovementioned example shows generalization of the “Primality Test by Multiplication”. If you need or find all prime numbers originally existing within the range of 2 to an integer 2N, you may make multiplication table P_ij (i=2~2N, and j=2~an integer L nearest to and smaller than $\sqrt{2N}$ (the intiger L ≤ $\sqrt{2N}$ ) ). The multiplication table is made of the products of each of the integers from 2 to N by each of the integers from 2 to the integer L . In this multiplication table P_ij (i=2~2N, and j=2~ the integer L), there appear without any exception all composite numbers originally existing within the range of 4 to 2N, while integers not appearing in this table are all prime numbers originally existing within the range of 4 to 2N.

With respect to prime factorization, it goes without saying that any composite number appearing in the multiplication table is a product of a known multiplier and a known multiplicand, which means that both of the multiplier and the multiplicand are factors of the composite number. These factors of the composite number are automatically factorized into a product of prime numbers by tracing back to its multiplier and multiplicand until each of the multiplier and multiplicand finally reaches respective prime numbers by sole use of the multiplication table.

As I explained above, primality test and prime factorization by “Primality Test by Multiplication” is applicable for all integers being in series not larger than any given integer N. Likewise, primality test and prime factorization can be done by “Primality Test by Multiplication” for any given number N of all integers being in series within the narrow range of any given integers $\ N_{ a }$ and $\ N_{ b }$, that is, $\ N_{ a }$≤N≤$\ N_{ b }$. Therefore, “Primality Test by Multiplication” is useful for finding whether a given number N is a prime number or composite number.

2. The “Primality Test by Multiplication” for odd integers

If priority is put to find and determine prime numbers originally existing within the range of given integers, a multiplication table is made of the products of each of the odd numbers from such as 3,5,7,9,11,13,15,17,19,21 to a given odd number N multiplied by each of odd numbers from 3 to an integer L nearest to $\sqrt{3N}$ . In this multiplication table P_ij (i=3~ odd number N, and j=3~integer L), there appear without any exception all odd composite numbers originally existing within the range of 9 to 3N, while integers not appearing within the range of 9 to 3N are all prime numbers originally existing within the range of 9 to 3N.

With respect to prime factorization, in the same way as stated above, factors of the odd composite number are automatically factorized into a product of prime numbers by use of the multiplication table. In order to find out prime numbers, primality test by “Primality Test by Multiplication” for odd integers is less laborious than primality test by “Primality Test by Multiplication” for integers in series because every integer except for 2 (two) is odd number and products of even number are not necessary for finding out prime numbers.

3. Examples of the Primality Test and Prime Factorization by multiplication for integers in series

Numbers written in light blue in Table 1 below are all composite numbers originally existing within the range of 4 to 50. Red numbers in Table 1 below are not necessary because relationship between a×b is equal to b×a (ab=ba) in multiplication according to commutative law.

【 Table 1 】 Table of the Primality Test by Multiplication for integers in series(from 2×2 to 25×25) for Primality Test and Prime Factorization

A multiplication table necessary to find all prime numbers originally existing within the range of 4 to an integer 50, is made of a multiplication table by multiplying integers from 2×2 to 25×7 (7 is an integer nearest to and smaller than $\sqrt{(2×25)}$ ). Numbers written in light blue in Table 1 above are all composite numbers originally existing within the range of 4 to an integer 50.

【１】 Result of picking up composite numbers and finding prime numbers within the range of 4 to an integer 50

Pick up numbers written in light blue in Table 1 and rearrange the numbers in a smaller order to larger. Then, the thus picked-up numbers are all composite numbers originally existing within the range of 4 to 50. Therefore, numbers written in red in List A below which do not appear are all prime numbers originally existing within the range of 4 to 50.

In the event of picking up composite numbers and finding prime numbers within the range of 4 to a very large integer, it is recommendable and less laborious to use an integer sequence ${({a_{n}})}^{N}_{n=4}$ of the thus picked-up and rearranged numbers in a smaller order to larger. In the integer sequence ${({a_{n}})}^{N}_{n=4}$ , a difference a_n+1−a_n=2 means that a_n+1 is a prime number.

List A

【 2 】 Method for Prime Factorization of the composite numbers in Table 1

Prime factorization of the composite numbers in Table 1 is automatically done by tracing a given composite number back to its multiplicand and multiplier until each of the multiplier and multiplicand finally reaches respective prime numbers by use of the multiplication table.

《 e.g. 》 In Table 1, composite number 306=18×17=3×6×17=2×3²×17
《 e.g. 》 In Table 1, composite number 529=23×23
《 e.g. 》 In Table 1, composite number 339=21×19=3×7×19

4. Examples of The Prime Factorization by multiplication for odd integers

【 Table2 】 Products of odd number i×odd number j（i=3,5,7,9,~199 j=3,5,7,9,~35）

For finding out any and all prime numbers originally existing within the range from 9 to 597, it is necessary and sufficient to make a multiplication table P_ij(i=3~ odd number 199, and j=3~odd integer 23= L≤ $\sqrt{3N}$ = $\sqrt{(3N × 199)}$ ≤24.3). Table 2 above is the thus made multiplication table by use of Microsoft Excel application soft.

As shown in Table 1, Pick up all numbers existing within the range of 9 to 597 in Table 2 and rearrange the numbers from smaller to larger. Then, the thus picked-up numbers are all composite numbers originally existing within the range of 9 to 597.

In the event of picking up composite numbers and finding prime numbers within the range of 9 to a very large integer, it is recommendable and less laborious to use an integer sequence ${({a_{n}})}^{N}_{n=9}$ of the thus picked-up and rearranged numbers from smaller to larger.

In the integer sequence ${({a_{n}})}^{N}_{n=9}$ , a difference a_n+1−a_n=4 means that there is one prime number between a_n+1 and a_n, that is, a_n+2 is a prime number. On the other hand, a difference a_n+1−a_n=6 means that there are two prime numbers between a_n+1 and a_n, that is, a_n+2 and a_n+4 are the two prime numbers.

【 Example1 】
Result of picking up odd composite numbers and finding prime numbers within the range of 105 to 203 (for a given number of all integers being in series within the range of given integers N1 to N2, that is, N1≦N≦N2).

Pick up numbers written in light blue in Table 2 and rearrange the numbers from smaller to larger. Then, the thus picked-up numbers are all composite numbers originally existing within the range of 105 to 203. Therefore, numbers written in red in List B below which do not appear are all prime numbers originally existing within the range of 105 to 203.

List B

【 Example2 】
Result of picking up odd composite numbers and finding prime numbers within the range of 501 to 561

Pick up numbers written in light green in Table 2 and rearrange the numbers from smaller to larger. Then, the thus picked-up numbers are all composite numbers originally existing within the range of 501 to 561. Therefore, numbers written in red in List C below which do not appear are all prime numbers originally existing within the range of 501 to 561.

List C

【 Example3 】
Method for Prime Factorization of the odd composite numbers in Table 2

《 e.g. 》 In Table 2 composite number 5103=189×27=21×9×27=3×7×9×9×3=3⁶×7
《 e.g. 》 In Table 2 composite number 5363=173×31
《 e.g. 》 In Table 2 composite number 6169=199×31

Postscript

In order to find prime numbers or to factor composite numbers of gigantic integers such as 100-digit numbers~1000-digit numbers by the “Primality Test by Multiplication”, it is, of cause, necessary to use a computer for making a multiplication table of gigantic integers by the “Primality Test by Multiplication”. However, once such multiplication table of gigantic integers is made, it is easy to find prime numbers or to factor composite numbers automatically.

Unlike the well-known Sieve of Eratosthenes, trial division, Miller-Rabin primality test and the other primality tests, “Primality Test by Multiplication” I have presented here is a simple, less laborious and extremely timesaving algorithm for primality test and prime factorization at the same time.

References

[REN´E SCHOOF]＂Algorithmic Number Theory MSRI Publications Volume 44, 2008″, Four primality testing algorithms.

Concluded.

A New Primality Test and Prime Factorization by Multiplication