A Review of Prime Numbers, Squaring Prime Pattern, Different Types of Primes and Prime Factorization Analysis

Abstract

The study of prime numbers and their properties has always been an intriguing and fascinating topic for mathematicians. Primes can be considered the “basic building blocks,” the atoms, of the natural numbers. They play a significant role in number theory. Also, prime numbers, in this current world of computers and digitalization, have paramount significance for the computer programmers and scientists to tackle relevant real-life problems. Since long time, many studies and researches have been conducted regarding prime numbers pattern. In this paper, a squaring prime pattern is presented. Moreover, fifteen different types of primes with their Python code to generate them is included within. In cryptographic encryption system, prime numbers play a major role for security systems in which prime factorization is necessary. Therefore, prime factorization of composite numbers using Sieve of Eratosthenes algorithm on different platforms and time analysis based on that has been presented in the paper. Also, factorization analysis of primes by five different algorithms has been shown and comparison of prime factorization of composite numbers vs time taken graph has been plotted. Two major applications of primes are also covered.

Introduction

I. INTRODUCTION

A prime number, or simply a prime, is a natural number greater than 1 that has no positive divisors other than 1 and itself. Symbolically, a number p is said to be prime if

(i) p > 1

(ii) p has no positive divisors except 1 and p.

A prime number is an integer greater than 1, only having two factors: 1 and itself. the fundamental theorem of arithmetic, also called the unique factorization theorem and prime factorization theorem, states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors [3]. For  example, 21 is an integer greater than 1, which is not a prime number, but it can be represented using the product of primes, i.e., 3 x 7. “1 is a prime number or not” remains confusing for people. This can be understood by the fundamental theorem of arithmetic. One can also be written as 1 = 1 x 1 x …… x 1 x 1. This doesn’t obey the fundamental theorem of arithmetic, so it is not a prime.

Another definition for prime numbers has been given by Borevich and Shafarevich as an element p of the ring D, nonzero and not a unit, that cannot be decomposed into factors p=ab, neither of which is a unit in D, in their classic text "Number Theory". It is well known that 2, 3, 5, 7, 11, 13, etc. are the first few primes. A natural number greater than 1 that is not a prime is called a composite number. The property of being a prime is known as primality. And two numbers, a and b, are said to be relatively prime if they have no prime factors in common [2].

Prime numbers and their pattern are a subject of fascination to the mathematicians since the very earliest time. There are numerous publications and different theories made by different mathematicians all over the world, seeking out ways to find to find the exact patterning. The inability to find an order has been eloquently documented, such as in Havil's book:

 “The succession of primes is unpredictable. We don't know if they will obey any rule or order that we have not been able to discover still. For centuries, the most illustrious minds tried to put an end to this situation, but without success. Leonhard Euler commented on one occasion. Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. In a lecture given by D.

 Zagier in 1975, he said, "There are two facts about the distribution of prime numbers that I hope to convince you so overwhelmingly that they will be permanently engraved in your hearts. The first is that [they are] the most arbitrary and ornery objects studied by mathematicians: they grow like weeds among the natural numbers, seeming to obey no other law than that of chance, and nobody can predict where the next one will sprout. The second fact is even more astonishing, for it states just the opposite: that the prime numbers exhibit stunning regularity, that there are laws governing their behaviour, and that they obey these laws with almost military precision.” (Havil 2003) [1]

To provide a bit of a historical context, prime numbers are not exactly known to be discovered at the exact time. There is speculation that some of the very earliest human civilizations had some concept of primes, but the first concrete evidence appears to be some Papyrus writings of the ancient Egyptians from over 3500 years ago [5]. The ancient Greeks were the first to include prime numbers in their academic curriculum. Since then, a lot of mathematicians have contributed in this field of mathematics. In 1640, Pierre de Fermat stated (without proof) Fermat little theorem (later proved by Leibniz and Euler) also investigated the primality of the Fermat numbers 22n+1 , and Marin Mersenne studied the Mersenne primes, prime numbers of the form 2p- 1  with p itself a prime number. Goldbach formulated Goldbach’s conjecture, that every even number is the sum of two primes in a 1742 letter to Euler [7]. Likewise, Euler, Gauss, Chebyshev, and Reimann also contributed heavily, particularly in the distribution of primes. Still, study of prime numbers is very intriguing and challenging and there are numerous unsolved problems regarding prime numbers such as The Twin Prime Conjecture, Goldbach’s Conjecture, infinitely many primes of the form n# -1?, infinitely many primes of the form n2 + 1? [6] and many more.

Prime numbers have a huge number of applications, both within mathematics and in the wider world. In fact, these days, primes are used by all of us on an almost daily basis, even if we’re not aware of it at the time. For mathematicians, primes are important because they are the atoms of multiplication [5], so many abstract problems involving multiplication can be solved if we know enough about prime numbers. In the wider world, the main uses of prime numbers are related to computers. In security system such as online transactions and communications, prime numbers are used. So, the analysis of prime generation has been carried out, and factorization of the composite numbers using Traditional, Fermat Theorem, Pollard Rho and other methods.

II. SQUARING PRIME PATTERN

Here are the prime numbers up to 151:

These are the numbers from 1 to 151 that are only divisible by 1 and themselves. On looking at these numbers superficially, we find no peculiar patterns between them. While looking at these, we won’t instantly search for patterns and we won’t find it easily as well. But guess what? There are several patterns among the prime numbers that were found by different mathematicians. In this paper, we will specifically be talking about the squaring primes pattern and proving it as well.

Consider the prime number p. Now, relying on this squaring prime pattern, we have, i.e., the square of any prime number minus one is the multiple of 24. And this pattern can be applied to all prime numbers, exclusive of 2 and 3, which can be considered sub-primes. For instance, let us take any two prime numbers, 19 and 73. Then,

Conclusion

This is a deep and detailed study about prime numbers. In this paper, there is a thorough introduction of different types of primes with the python codes embedded, squaring prime pattern, time analysis of generation of primes and comparison of different factorization methods. Moreover, important applications of prime numbers are also included.

References

[1] Porras Ferreira, J.W. (2017) The Pattern of Prime Numbers. Applied Mathematics, 8, 180-192 [2] A.R.C.De Vas Gunasekara, A.A.C.A.Jayathilake and A.A.I.Perera (2015) Survey on Prime Numbers. Elixir Appl. Math. 88 (2015) 36296-36301 [3] .https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic [4] https://youtu.be/ZMkIiFs35HQ [5] https://serious-science.org/prime-numbers-6114 [6] J J O’Connor and E F Robertson, Prime Numbers, MacTutor. School of Mathematics and Statistics; University of St Andrews, Scotland [7] https://en.wikipedia.org/wiki/Prime_number [8] .https://en.wikipedia.org/wiki/List_of_prime_numbers [9] https://en.wikipedia.org/wiki/Category:Classes_of_prime_numbers [10] Masum Billal, Amir Hossein Parvardi (August 28, 2018), Topics in Number Theory: An Olympiad-Oriented Approach [11] .https://www.researchgate.net/deref/http%3A%2F%2Fconnellybarnes.com%2Fdocuments%2Ffactoring.pdf [12] Mathematics of Computation, Vol. 64, No. 209 (Jan., 1995), pp. 397-405, Published by: American Mathematical Society, Article Stable URL: http://www.jstor.org/stable/2153343. [13] A Gentle Introduction To Number Theory And Cryptography [Notes For The Project Grad 2

Copyright

Copyright © 2023 Prabhat Mahato, Aayush Shah. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.