Note: Some browsers may not display symbols such as root properly. (Recommended browser: Google Chrome)

13th August 2019

# A New Primality Test and Prime Factorization by Multiplication

Natoshi Takezaki

## 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{\mathrm{2N}}$(the intiger L ≤ $\sqrt{\mathrm{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{\mathrm{2N}}$(the intiger L ≤
$\sqrt{\mathrm{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{\mathrm{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{\mathrm{(2\times 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
${{\left(\left\{,{a}_{n},\right\}\right)}^{N}}_{\mathrm{n=4}}$
of the thus picked-up and rearranged numbers in a smaller order to larger. In the integer sequence
${{\left(\left\{,{a}_{n},\right\}\right)}^{N}}_{\mathrm{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^{2}×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{\mathrm{3N}}$
=
$\sqrt{\mathrm{(3N\; \times \; 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 ${{\left(\left\{,{a}_{n},\right\}\right)}^{N}}_{\mathrm{n=9}}$ of the thus picked-up and rearranged numbers from smaller to larger.

In the integer sequence
${{\left(\left\{,{a}_{n},\right\}\right)}^{N}}_{\mathrm{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^{6}×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.