On Prime number varieties and their applications

1. Introduction

It is widely acknowledged that mathematics is a base for all science and engineering concepts and number theory is the base for mathematics. A vital and challenging task of answering questions in number theory depends heavily on finding an integer’s unique factor decomposition. When researchers show involvement, new research approaches emerge. Number theory is largely classified as elementary number theory dealing with divisibility and congruence; analytic number theory supported by complex analysis; algebraic number theory due to the evolution of the study on ring of integers; geometric number theory depending on the perspectives of geometry to explain the pattern of distribution and computational number theory that uses computer algorithms to solve certain mind boggling problems. The universe now witness the rapid use of the concepts of number theory in applied fields such as physics, biology, chemistry, communication, acoustics, electronics, cryptography, computing etc, [1].

2. Prime numbers

A positive integer p which is larger than 1 is called a prime number if \(\forall \ \ n\in N, n|p\Rightarrow n=1 \bigvee n=p\). A number which is not a prime is called a composite number. The Fundamental Theorem of Arithmetic (FTA) says every integer larger than 1 can be expressed as a product of primes in a unique manner apart from their order. Prime numbers are used in cryptography to calculate the public and private keys. Its strength heavily depends on the difficulty of decomposing large integers into their factors. For instance, Diffie-Hellman used prime numbers in his key exchange. He made use of a huge prime number p as a common modulus through which two persons A1 and A2 can communicate in secured way with their undisclosed private keys. That is, if A1 and A2 possess their private key respectively a1 and a2 and publicly share upon a key say b which is smaller than p then one can send a message to the other as: \( A_{1}’s\) message\(=m_1\equiv b^{a_1}\) (mod p)and \( B’s\) message\(=m_2\equiv b^{a_2}\) (mod p) then \(m_{2}^{a_2}\) (mod p)\(=m_{1}^{a_2}\) (mod p)\(=b^{a_{1}.a_{2}}\) (modp) \(\equiv x\) is the message shared. The security aspect in this communication depends on the difficulty to know the shared message without knowing \(a_1\) and \(a_2\).

3. Mersenne prime numbers

An integer that is positive and denoted \(M_p = 2^p-1\) is called a Mersenne prime if \(M_p\) is a prime integer. It was already established in the literature that if \(2^p-1\) is a prime then \(p\) is a prime integer as well. But the reverse implication is false. For example, \(\hat{p}= 11\) is a prime integer but \(2^{11}-1 = 2047\) is not a prime integer. These Mersenne primes can be easily represented in binary form without requiring additional space as a p-digit integer can hold upto \(2^p-1\) digits in a binary system. Nishimura and Matsumoto found an efficient pseudorandom generating algorithm by making a good use of Mersenne primes [2].

4. Some results

Proposition 1. Suppose that \(p\) is a prime. Then \(p^2 + p + 1 \neq r^3\) for some \(r \in Z^+\).

Proof. Suppose that \(p^2 + p + 1 \neq r^3\) for some \(r \in Z^+\) then \(r^3-1=p(p+1)\) implies \(p(p+1)=(r-1)(r^2+r-1)\). As \(p\) is a prime, by one of the properties of primes, we have either \(p | r -1\) or \(p | r2 + r + 1\). . If \(p | r -1\) then clearly \(p \leq r -1\). So \(p + 1\) \(r \rightarrow r^3\) \((p + 1)^3 > p^2 + p + 1 = r^3\), a contradiction. Next if \(p | r^2 + r + 1\) implies \(p = 3\) and \(r = 1\), else, \(p = 3\mathcal{L} + 1\) for some \(\mathcal{L} \in Z^+\). Hence \(p^2 + p + 1 \equiv 3 (mod 9)\). But it can be easily seen that a perfect cube cannot be written as \(9t -3\) for some \(t \in Z^+\).

Proposition 2. Let \(p_1\), \(p_2\), \(p_3\) be odd primes and \(p_{1}^2 + p_1+ 1 = (p_{2}^2 + p_2+ 1)( p_{3}^2 + p_3+ 1)\) then either \(p_{2}^2 + p_2+ 1\) or \(p_{3}^2 + p_3+ 1\) is not a prime.

Proof. Suppose that both \(p_{2}^2 + p_2+ 1\) and \(p_{3}^2 + p_3+ 1\) are primes. Then one of (a) \(p_1\equiv p_2(mod p_{2}^2 + p_2+ 1 )\) or \(p_1\equiv p_{2}^2(mod p_{2}^2 + p_2+ 1 )\) or (b) \(p_1\equiv p_3(mod p_{3}^2 + p_3+ 1 )\) or \(p_1\equiv p_{3}^2(mod p_{3}^2 + p_3+ 1 )\) hold good. Without loss of generality assume that a) holds good. As \(p_1 > p_2\) and \(p_1\) is a prime it readily follows that \(p_1 \neq p_{2}^2\). Further, the other choice for \(p_1\) is \(p_{2}^2+p_{2}+1+p_{2}=(p_2+1)^2\). As \(p_2\) is an odd prime \((p_2 + 1)\) is even and hence \((p_2 + 1)^2\) is also even, and contradiction. Finally, \(p_1\) also cannot be equal \(p_{2}^2+p_{2}+1+p_{2}^2=2p_{2}^2+p_2+1\) as \(2p_{2}^2+p_2+1\) is even. From this it follows that \(p_1\geq 2(p_{2}^2+p_{2}+1)+p_2 > 2(p_{2}^2+p_{2}+1)\). On similar lines we can also get \(p_2 \geq 2(p_{3}^2+p_{3}+1). So 3(p_{2}^2+p_{2}+1)(p_{3}^2+p_{3}+1)=p_{1}^2+p_1+1 >p_{1}^2 > 4(p_{2}^2+p_{2}+1)(p_{3}^2+p_{3}+1)\). This is again absurd. Hence one of the two \(p_{2}^2+p_{2}+1\), \(p_{3}^2+p_{3}+1\) is not a prime.

Proposition 3. Let \(p_1\), \(p_2\) be two distinct odd primes and \(p_{1}^2+p_{1}+1\) is also a prime. If \(p_{1}^2+p_{1}+1|p_{2}^2+p_{2}+1\) then \(p_{1}^2+p_{1}+1 < p_{2}/2\).

Proof. It is easy to see that \(p_2=k(p_{1}^2+p_{1}+1)-p_{1}\) or \(p_2=k(p_{1}^2+p_{1}+1)-p_{1}^2\). Also \(p_{2}\) cannot be equal to \(p_{1}^2\). Moreover \(P_{2}\) canot be equal to \((p_{1}^2+p_{1}+1)-p_{1}\) and \((p_{1}^2+p_{1}+1)-p_{1}^2\) as both these terms are even. So we have \(p_{2}\geq p_{1}+2(p_{1}^2+p_{1}+1) > p_{1}^2+p_{1}+1\).

Proposition 4. It is not possible to produce three odd primes \(p_1\), \(p_2\), and \(p_3\) with \(p_{1}^2+p_{1}+1\) and \(p_{2}^2+p_{2}+1\) primes such that \(p_{3}^2+p_{3}+1=3(p_{1}^2+p_{1}+1)(p_{2}^2+p_{2}+1)\).

Proof. Suppose we assume the contrary then by invoking Proposition 3 one can deduce \((p_{1}^2+p_{1}+1)< p_{3}/2\) and \((p_{2}^2+p_{2}+1)< p_{3}/2\). So, \(p_{3}^2+p_{3}+1=3(p_{1}^2+p_{1}+1)(p_{2}^2+p_{2}+1) < 3(p_{3}/2)(p_{3}/2)=\frac{3p_{3}^2}{4}< p_{3}^2+p_{3}+1\) yields a contradiction to conclude the proof.

5. Perfect numbers

We call a positive integer, a perfect number if it equals the sum of its proper divisors. Euclid about three centuries before the Jesus Christ showed that \(2^{p-1} (2^p-1)\) is perfect if \(2^p-1\) is a prime number. After this one has to wait for almost 2000 years to get one Euler to establish all perfect numbers that are even must be of Euclid’s form. It is too wonderful to record that even till date we do not know how many such even perfect numbers are there and also nothing is known about the existence or otherwise of an odd perfect number. See [3,4]. Zelinsky [5] showed the following;

5.1. Wonderful result

Suppose that \(n\) is a perfect number that is odd. Let the distinct prime divisors of n be \(\omega(n)\) in number and let the total number of prime divisors of \(n\) by \(\Omega(n)\). If \(gcd(3,n)=1\) then \((302/113)(\omega(n))-(285/113)(\Omega(n))\). If \(n\equiv 0(mod3)\) then \((66/25)(\omega(n))-5 \leq \Omega(n) \).

5.2. Amicable number pairs

The sum of divisors is the function \(\sigma=\sum_{dn}\), where d varies over all positive factors of n including 1 and n. For example \(\sigma(5)=1+5=6\), \(sigma(6)=1+2+2+3+6=12\). We call n a perfect number if \(\sigma(n)=2n\). The case when \(sigma(n) 2n\), we call n abundant. We can also call n, perfect if \(sigma(n)=n\) in which case we consider only proper divisors of n that excludes n. Note that \(\sigma(mn)=\sigma(m)\sigma(n)\). This is because if \(d | mn\) then by unique decomposition we can write d uniquely as the product of factor of m and a factor of n. So every term in \(\sigma(mn)\) occurs exactly once in \(\sigma(m)\) \(\sigma (n)\). Also every such product is a factor of \(mn\) so they yield the same sum. Observe that if \(d | n\) then \(\sigma(d) < \sigma (n)\).

Proposition 5. If \(d^{*}|n\) then \(\frac{\sigma(d^{*})}{d^{*}}\leq \frac{\sigma(n)}{n}\) and equality holds good only if \(d^{*}=n\).

Proof. If \(d|n\) then \(n=\mathcal{L}d\) for some \(\mathcal{L}\), so \(\mathcal{L}=(n/d)|n\). Hence \(\sigma (n)=\sum _{d|n}d=\sum _{d|n}\frac{n}{d}=n\sum_{d|n}\frac{1}{d}\). If \(d^{*}\) is proper factor of \(n\) then \(\sigma(n)/n=\sum _{d|n}(1/d)>\sum_{d’|d^{*}}\frac{1}{d’}=\frac{\sigma (d^{*})}{d^{*}}\).

Proposition 5 implies that \(\sigma (n)=\sum _{d|n}d=\sum _{d|n}\frac{n}{d}=n\sum_{d|n}\frac{1}{d}=2n\). So \(\sum_{d|n}1/d=2\) is \(n\) is perfect. Euclid established that if \(2^n-1\) is a prime then \(2^{n-1}(2^n-1)\) is a perfect number. This is because, the only prime divisors of \(2^{n-1}(2^n-1)\) are \(2^n-1\) and \(2\). So \(\sigma[2^{n-1}(2^n-1)\sigma(2^{n-1})\sigma(2^n-1)=\left(\frac{2^n-1}{2-1}\right)2^n=2\{2^{n-1}(2^n-1)\}\). Similarly, \(2^n-1\) is a prime then \(n\) itself is a prime. This is because, \(y^n-1=(y-1)(y^{n-1}+y^{n-2}+…+y+1)\). If \(n=\mathcal{L}n\) then \(2^n-1=(2^{\mathcal{L}})^{m}-1=(2^{\mathcal{L}}-1)(1+2^{\mathcal{L}}+…+(2^{\mathcal{L}})^{m-1})\). Hence \((2^{\mathcal{L}}-1)|2^n-1\), which is a prime, a contradiction. Its converse is not true. For example, 11 is a prime but \(2^{11}-1=2047=23 \times 89\) is not a prime. Perfect numbers have some interesting properties. We call a number a triangular number if it can be arranged as a triangular lattice.

Proposition 6. If \(n\) is an even perfect number then it is triangular.

Proof. We deem \(\mathcal{L}\) as a triangular number if \(\mathcal{L}=\sum_{j=1}^{t-1}j=1+2+…+(t-1)t/2\) for some t. However note here that \(n^{*}=2^{n-1}(2^n-1)=\frac{1}{2}(2^n)(2^n-1)\). So an even perfect number is triangular.

Proposition 7. \(n^{*}=2^{n-1}(2^n-1)\) is perfect then \(n=1^3+3^3+…+(2^{(n-1)/2}-1)^3\).

Proof. We know that \(\sum_{j=1}^{n}=n^{2}(n+1)^2/4\). Let \(\mathcal{L}=2^{(n-1)/2}\). Then \(n=1^3+3^3+…+(2\mathcal{L}-1)^3=(1^3+2^3+…+(2\mathcal{L})^3)-(2^3+4^3+…+(2\mathcal{L})^3) =[(2\mathcal{L})^2(2\mathcal{L}+1)^2]/4-2^3[(\mathcal{L})^2(\mathcal{L}^2+1)^2]/4 (\mathcal{L})^2(\mathcal{L}^2-1)\). Put \(\mathcal{L}=2^{(n-1)/2}\) to complete the proof.

Proposition 8. All even perfect numbers have its unit digit as 6 or 8.

Proof. Note that if \(p\) is an odd prime then it is either congruent to 1 (mod 4) or congruent to 3 (mod 4). Let it be first congruent to 1 (mod 4). Then \(2^{n-1}(2^n-1)=2^{4\mathcal{L}}(2^{4\mathcal{L}+1}-1)=16^{\mathcal{L}}(2\times 16^{\mathcal{L}}-1)\equiv 6^{\mathcal{L}}(2\times 6^{\mathcal{L}}-1)\equiv 6(12-1) \equiv 6(mod 10) \). In a similar way, \(2^{n-1}(2^n-1)=4\times 16^{\mathcal{L}}(8\times 16^{\mathcal{L}}-1)\equiv 4 \times 6 (8\times 6-1)\equiv 4(8-1)\equiv 8(mod10)\). In both instances we made use of the fact that \(6^{\mathcal{L}}\equiv 6(mod 10)\).

A pair of integers \((r, s)\) with \(r, s \in Z^+\) and \(r < s\) is called amicable if each of \(r\) and \(s\) is the sum of the proper divisors of the other. Euler was the first mathematician to investigate amicable pairs in a systematic manner. He looked at amicable pairs of the form \((rm, rn)\) where \(r\) is a given known factor and m, n are unknowns with \(gcd(m, n) = 1\). By setting \(r = 2^s\), \(s \in Z^+\), \(m = pq\), \(n = t\) with \(p, q, t\) are distinct primes, one can obtain the forms of Thabit period. By taking \(r = 3^2 \times 7 \times 13, m = pq\) and \(n = t,\) Euler got the first amicable pair whose elements are odd, \((3^2 \times 7 \times 13 \times 5 \times 17 = 69615, 3^2 \times 7 \times 13 \times 107 = 87633)\). A pair of positive numbers \((r_1, r_2)\) is called a breeder if \(r_1 + r_2x = \sigma (r_1) = \sigma (r_2) (x + 1)\) have a positive integer solution x. Borho suggested a rule to find an amicable pair by using breeders. Suppose that \((rd, r)\) be a breeder, with integer solution x. If a pair of distinct prime numbers \(p_1, p_2\) exist with \(gcd(r, p_1p_2) = 1\), fulfilling the bilinear equation \((p_1 -x) (p_2 -x) = (x + 1) (x + d)\) and if a third prime \(p_3\) exists with \(gcd(rd, p_3) = 1\) such that \(p_3 = p_1 + p_2 + d\) then \((rdp_3, rp_1p_2)\) is an amicable pair. Another great mathematician Erdos suggested: for a given \(s \in Z^+\) if \(x_j, j = 1, 2, … \)are solutions of \(\sigma(x) = s\) then any pair \((x_i, x_k), i \neq k\) for which \(x_i + x_k = s\) is an amicable pair.

We call a set of three integers \(m_1, m_2, m_3\) form an amicable triple if \(\sigma(m_1) = m_1 + m_2\), \(\sigma(m_2) = m_2 + m_2\) and \(\sigma(m_3) = m_3 + m_1\), and a set of four integers \(m_1, m_2, m_3\) and \(m_4\) is said to form an amicable quadruple if \(\sigma(m1) = m2, \sigma(m2) = m3, \sigma(m3) = m4\) and \(\sigma(m4) = m1\). Fig. 1 shows a python program to find perfect numbers, amicable pairs, amicable triples and amicable quadruples. Accordingly we record that \(6, 28, 496, 8128\) are perfect numbers, \((220, 284), (1184, 1210), (2620, 2924), (5020, 5564)\) are amicable pairs, \((1980, 2016, 2556), (9180, 9504, 11556)\), are amicable triples and \((1236402232, 1369801928, 1603118392, 1412336648)\) is an amicable quadruple.

It is worth to re-publicize the following open questions. 1) Are there an infinite number of amicable pairs 2) Is there an amicable pair whose elements are of different parity 3) Is there an amicable pair whose elements are relatively prime 4) Are there amicable pairs whose elements have smallest but different prime divisors Some of the amicable pairs are (\(1184, 1210), (2620, 2924), (5020, 5564)\) etc. These numbers have the feature that one represents the other. This stands for love, harmony, friendship etc. There numbers have lot of applications in astrology in casting horoscopes and magic.

6. Semiprimes

A semiprime number is a number that can be expressed as a product of two prime numbers [6]. Look at 35, it is easy to see that 5 and 7 are the only factors other than 1 and itself. Determination of prime factors of a large number with millions of digits is a huge task. The difficulty in factoring forms the basis of security in RSA encryption algorithms. The semiprime number serves as a public key to encrypt a message and its prime factors act as private keys to decrypt a message.

When analyzing the logic gates, one can analyze both AND gate and OR gate together. This is because both generate almost identical information. For any given state of AND or OR there is a 22% probability that the state could be an error. This occurs when at least two I/O’s are defined at the same time. If one of the I/O is defined there is 50% probability that at least one more I/O will be deduced. Given a gate with random inputs and no error there is 62% chance that the gate is fully define. It is wonderful to observe that the probability of error do not get altered while changing from the Full-Adder to Array Multiplier Cell. As the I/O count increases, the ability to generate new information decreases. This is crucial to factorize the semiprime numbers, because as the semiprimes grows, the complexity and I/O count of the array multiplier will grow and result in lesser quantity of information generation. With a fully operating reversible array multiplier, one can test a huge quanta of possibilities for the semiprime number and perform data analysis to quantity the information generated. Python code is involved to generate prime numbers for various binary lengths, from 2 bits to 512 bits. The prime numbers are then multiplied and fed into the output of the reversible array multiplier. After deducing all information, it can be saved as a CSV file. Then one can depict it as a graph to show the information as a function of the size of the semiprime number.

7. 7\(\Pi\) and primes

The most precious gem of India, Srinivasa Ramanujan in one of his shocking revelation formulae have said that: \[1/\pi=(2\sqrt{2}9801)\sum_{n=0}^{\infty}\frac{4n!(1103+26390n)}{(n!)^4(306)^{4n}}.\] The first term in the r.h.s of the above equation gives 7 digits of \(\pi\). That is \(\pi=\frac{9801}{2206\sqrt{2}}\approx 3.14159273…\) (7digits). Note that one can add eight correct digits with each additional term. The rate of convergence is also unbelievably fast. Some more of wonderful expressions for \(\pi\) are \(\pi \approx (3/\sqrt{163}ln(640320))=3.14159273…\) (15 digits) \(\pi \approx (3/\sqrt{67}ln(5280))=3.141592653…\) (9 digits). It is amazing to observe that the first six digits \(3.14159\) is a prime. Infact, the first 38 digits of is also a prime. \(3, 31, 314159, 31415926535897932384626433832795028841\) are all primes. Here the reverse of first three primes viz., \(3, 13, 951413\) are also primes. It was checked up to first \(432\) digits of and only the above four numbers are primes. It is till date unknown whether there is another prime for more digits of . It is strikingly shocking that \(314159\) is a very unusual peculiar prime. The complement number of this prime obtained by replacing each digit of this number by the difference of it with \(10\), viz., \(796951\) is also a prime. If this number is split into three two digit numbers viz., 31, 41 and 59 are again prime numbers. The sum of them \(31 + 41 + 59 = 131\) is also a prime and the sum of the cube of them \(313 + 413 + 593 = 304091\) is also a prime. There are lot of coincidences among and primes. May be much more in depth relations exist between them and they are yet to be found.

8. Prime numbers as a physical system

Marshall and Smith [6] explored the prime numbers from different viewpoint. They treated prime numbers as a physical system and represented it as a differential equation \(f'(x)=-f(xf(x\sqrt{x}))/2x\). \(f(x)\) stands for the “density of primes at x”. It predicts the known results regarding the distribution of primes. They have said a deeper relation between number theory and feedback & control, a field in Engineering. They assumed that the density of primes said above is a point density and not average density. They considered two intervals. IA is the interval on R given by \([x, x + dx]\). IB is the square of IA: \([x^2, (x + dx)^2]\). Now approximate the quantity \(f((x + dx)^2) -f(x^2)\). Consider only the effect of primes on IA on the density along IB. Every prime in IA changes the density on IB by a factor of \(1 -1/x\). So every prime subtracts \(f(x^2)/x\) from density. There are \(f(x)\) dx primes in IA. The first approximation of the change in density on IB is \(f((x+dx)^2)-f(x^2)\approx \frac{f(x^2)f(x)dx}{x}\). Another way to calculate the change in density on IB is through derivatives. \((x + dx)^2- x^2 = 2x dx + (dx)^2\). Change in density in IB is roughly evaluated at x2 times the length of IB. So \(f((x+dx)^2)-f(x^2)\approx f'(x^2)x2dx\) By comparing these we get \(f'(x^2)=-f(x^2)f(x)/2x^2\) and by replacing \(x^2\) with \(x\) we get \(f'(x)=-f(x)f(\sqrt{x})/2x.\)

9. Conclusion

We have briefly discussed about the prime numbers and its variations and how their properties and distribution reveal several interesting features and how they are exploited in different application areas of real life scenario. A lot of things about primes are yet to be said and it holds a huge opportunity for researchers to probe and bring out the unknown. We hope to revert more on this elsewhere.

Authorcontributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflict of Interests

The authors declare no conflict of interest.