Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums

Ioannis Papadakis

doi:doi:10.11648/j.mcs.20240903.12

Research Article |

| Peer-Reviewed

Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums

Ioannis Papadakis^*

Published in Mathematics and Computer Science (Volume 9, Issue 3)

Received: 11 July 2024 Accepted: 29 July 2024 Published: 15 August 2024

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The algebraic structure and distribution of prime numbers remain two of the most fundamental problems in mathematics. The Fundamental Theorem of Arithmetic, proved by Euclid, and Goldbach’s conjecture, while universal in scope with respect to how numbers can be represented multiplicatively or additively, do not provide insights into the structure of primes. Similarly, the definition of a prime −as a number divisible only by 1 and itself− or a sieve algorithm, commonly used to generate primes by successively eliminating multiples, offer no insight into the structure of primes. The powerful and persistent consideration of prime numbers as universal “arithmetic quanta” has not necessitated an equally powerful need for parallel research into a deeper and possibly more insightful explanation of primeness, that is, a better understanding of “why” a number is prime. In this paper, prime and coprime numbers are represented and generated by algebraic expressions. Specifically, given the first n primes, p₁, p₂,…, p_n, sufficient conditions are given for expressing primes greater than p_n, and coprimes with prime factors greater than p_n, as algebraic functions of p₁, p₂,…, p_n. Thus, primality and co-primality are shown to be mathematical properties with inherently evolutionary algebraic characteristics, since larger primes and coprimes can be generated algebraically from smaller ones. The methodology described in the paper can be a useful tool in the study and analysis of the complexity, structure, interrelationships and distribution of primes and coprimes.

Published in	Mathematics and Computer Science (Volume 9, Issue 3)
DOI	10.11648/j.mcs.20240903.12
Page(s)	57-63
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2024. Published by Science Publishing Group

Keywords

Prime Number, Prime Factor, Factorization, Coprime, Algebraic Representation, Prime Generation, Coprime Generation, Optimization

1. Introduction

The Fundamental Theorem of Arithmetic (FTA), proved by Euclid (300 BCE), states that any integer greater than 1 can be expressed as a prime, or unique product of primes called prime factors

[1, 2]

. Goldbach’s conjecture, in its broadest interpretation, states that any integer greater than 1 may be expressed as a sum of at most three primes, thus representing a “summative counterpart” to the factorization result of the FTA

[3-6]

Such universally optimal representations, multiplicative or summative, do not help us gain meaningful insights into the structure of primes, since, by definition, primes are the “quanta”, i.e. indivisible building blocks, of all numbers. For that reason, the primality of a number is typically established, or refuted, by reverting to the definition of a prime: a number that is divisible only by itself and 1. No additional insight into the algebraic structure of primes is gained by applying a sieve: the set of primes, P, corresponds to the “leftover” numbers, i.e. those not eliminated by the sieve algorithm

[7]

. However, the underlying mathematical structure of primes and coprimes is intrinsic and interdependent, and thus merits a more systematic focus.

In this paper, it is shown that, under certain conditions, the primality of a number is dependent to that of smaller primes in an algebraic sense; a similar result holds for certain coprimes. Our findings demonstrate that primality, and co-primality, are properties with evolutionary characteristics, propagating from smaller to larger primes and coprimes. For example, while it is typically claimed that “3 is prime because it can only be divided by itself and 1”, this paper offers an alternative explanation: 3 is prime because it equals

2^{1} + 1

. Put differently, it can be shown that the quantity represented by

2^{b} \pm 1

is prime, if

2^{b} \pm 1 < 9

. Hence, the primality of 3, 5 and 7 is a direct algebraic consequence of the primality of 2, without the need to apply the definition of a prime number, or rely on a sieve.

A consequence of the above is that 3, 5 and 7 “inherit” their primality from that of 2. The values, and therefore the distribution, of the next 3 primes, is a direct algebraic result of the primality and value of 2, the first prime. This result may be generalized by describing the algebraic structure that represents, and can therefore generate, prime numbers greater than the n^th prime,

p_{n}

, as discussed in the next section.

Prior research has established the “quantum optimality”, multiplicative and additive, of the set P of primes, and the existence of sufficient conditions for the algebraic representation of primes using Hybrid Prime Factorization (HPF), i.e. algebraic expressions containing structured sums

[8, 9]

Specifically, this paper extends the results of the research

[9]

, by establishing common, less restrictive sufficiency conditions for the algebraic representation of primes and coprimes. Such expressions can find applications in cryptography, where prime factorization and computationally efficient generation of increasingly large primes are used for securely encrypting and decrypting digital information

[10, 11]

The methodology presented in this paper can be a useful tool for the study of the evolutionary characteristics of primality, the relational properties of primes, coprimes, and their distribution.

2. Generation of Primes and Coprimes

The Hybrid Prime Factorization (HPF) algebraic structure, defined in the next section, is used to generate larger primes and coprimes. It consists of a coprime sum or difference, subject to several conditions.

2.1. The HPF Algebraic Structure

“HPF” refers to an algebraic expression of the form

HPF = p_{1}^{a_{1}} ∙ p_{2}^{a_{2}} ∙ \dots ∙ p_{n}^{a_{n}} \pm p_{1}^{b_{1}} ∙ p_{2}^{b_{2}} ∙ \dots ∙ p_{n}^{b_{n}}

(1)

where

p_{1}, p_{2} \dots, p_{n}

denote the first n primes and the integer exponents

a_{i}, b_{i}

satisfy the conditions:

a_{i}, b_{i} \geq 0

(2)

a_{i} ∙ b_{i} = 0

(3)

a_{i} + b_{i} \geq 1

(4)

\sum_{i = 1}^{n} a_{i} \geq 1

(5)

\sum_{i = 1}^{n} b_{i} \geq 1

(6)

HPF > 1

(7)

for

i = 1, 2, 3, \dots, n

Inequalities (2)-(4) ensure that the two multiplicative terms in (1) are coprime, i.e. no

p_{i}

can be a factor in both terms, and (5)-(6) prevent either term in (1) to be 1. Condition (7) eliminates any trivial, non-prime solutions, i.e. where

HPF = 1

, such as:

2^{4} - 3 ∙ 5

5^{2} - 2^{3} ∙ 3

2^{2} {∙ 3}^{2} - 5 ∙ 7

Given the HPF structure (1)-(7), the prime generation result reported in research

[9],

can be summarized by stating that if

HPF < p_{n + 1}^{2}

(8)

then the HPF represents a prime

> p_{n}

Example 1. Let

p_{1} = 2

p_{2} = 3

p_{3} = 5

p_{4} = 7

. Each of the HPF expressions below, satisfies (2)-(8) for

n = 3

, and therefore it represents a prime

> 5

3 ∙ 5 - 2 = 13

(9)

3 ∙ 5 + 2 = 17

(10)

2^{2} ∙ 3 - 5 = 7

(11)

2^{2} ∙ 3 + 5 = 17

(12)

2^{2} ∙ 3^{2} - 5^{2} = 11 .

(13)

If the sufficiency conditions (2)-(8) are not satisfied, HPF may or may not be a prime, as shown by the expressions below:

2^{2} ∙ 3^{2} + 5^{2} = 61

isprime;(8)notsatisfied(14)

2^{1} ∙ 3^{3} - 5 = 49

isnotprime;(8)notsatisfied(15)

2^{2} + 5^{2} = 29

isprime;(4)notsatisfied(16)

2^{6} - 5 = 59

isprime;(4)and(8)notsatisfied.(17)

The result described in the above example can be generalized, based on the observation that when the HPF satisfies (2)-(7) but not (8), it will either be a prime

\geq 7

, or a composite number, coprime to {

2, 3, 5},

with at most

k

prime factor terms, where

k

is the smallest integer such that

HPF < 7^{k + 1}

. Hence, the prime generation result reported in research

[9],

corresponds to the special case

k = 1

, for which the HPF value is predictably prime. The following proposition formalizes this generalized result.

Proposition 1. The HPF expression, given by (1), subject to (2)-(4) and (7), is:

(i) co-prime to

p_{1}, p_{2} \dots, p_{n}

;

(ii)

HPF \geq p_{n + 1}

;

(iii) the number of terms in the prime factorization of the HPF is at most

k

, where

k \geq 1

is such that

k \leq \frac{\log (HPF)}{\log (p_{n + 1})} < k + 1

(18)

and log(·) denotes the natural logarithm function.

Proof. The HPF, given by (1), cannot have any of

p_{1}, p_{2} \dots, p_{n}

as prime factor(s), since this would lead to a contradiction, given that the two product terms in (1) are coprime, by virtue of conditions (2)-(4) and (7). Hence, HPF > 1 is coprime to

p_{1}, p_{2} \dots, p_{n}

, which proves the first part of the proposition. From this, it follows that the minimum value of the HPF is

p_{n + 1}

, i.e. its smallest prime factor. Therefore

HPF \geq p_{n + 1}

.(19)

To prove the last part of the proposition, let

k \geq 1

such that

p_{n + 1}^{k} \leq HPF < p_{n + 1}^{k + 1}

.(20)

Since every prime factor of HPF is

\geq p_{n + 1}

, it follows that the HPF cannot have more than k terms in its prime factorization, since this would violate the right side of (20). By taking the natural logarithms of all sides of (20), expression (18) follows, and the last part of the proposition is proved.

From Proposition 1, it follows that for the special case

k = 1

, the HPF, given by (1), is a prime number in the semi-open interval [

p_{n + 1}, p_{n + 1}^{2})

. For higher values of k, the HPF is either a prime or coprime in the semi-open interval [

p_{n + 1}^{k}, p_{n + 1}^{k + 1})

, with a maximum “prime factor cardinality” of k, i.e. having at most k terms in its prime factorization (including any repeating primes).

The following examples show how Proposition 1 can be used to represent, and thus generate, primes and coprimes.

Example 2. Let

n = 3

and consider the HPF expression (15) of the previous example. In this case,

k = 2

, since

HPF = 2^{1} ∙ 3^{3} - 5 = 49 = p_{4}^{2}

(21)

and HPF is coprime to

{2, 3, 5}

, with a maximum prime factor cardinality of 2 and no prime factor smaller than 7.

Example 3. Consider the HPF expression (

n = 3

), given by

HPF = 2^{10} ∙ 3^{5} ∙ 5^{5} + 1 = 777, 600, 001

(22)

for which, the corresponding value of k, from (18), is

k = ⌊\frac{\log (HPF)}{\log (p_{4})}⌋ = ⌊\frac{\log (777, 600, 001)}{\log (7)}⌋ = 10

(23)

where

⌊∙⌋

denotes the integer part operator. The above equation implies that (22) has a maximum prime factor cardinality of 10, with no prime factor < 7. This is confirmed by the prime factorization of the HPF, given by

HPF = 777, 600, 001 = 31 ∙ 61 ∙ 411, 211

.(24)

The value of the HPF expression (1) may be minimized with respect to the exponents

a_{i}, b_{i}

, subject to the conditions of Proposition 1, to maximize the likelihood of the HPF representing a relatively smaller prime

> p_{n}

, or a (composite) coprime

> p_{n}

with relatively small prime factors and cardinality.

In general, (1) may be viewed as an algebraic generator of primes and coprimes. Its prime and coprime generating performance is analyzed in Section 3.

2.2. Evolutional Characteristics of Primality

The algebraic system described by (1)-(4) and (7) lends itself to a hierarchical evolutionary structure in the generation of primes from smaller ones. The relaxation of conditions (5)-(6) implies that such hierarchical generation can be traced to the smallest possible prime. To show this, consider

a

, where

a = 1 + 1

. Since

1 < a < 4

, with 4 being the smallest possible non-prime (composite) number, it follows that 2 and 3 are prime. The primality of 3 may also be established from the primality of

HPF = 2^{2} - 1

, since it represents a number

> 2

and

< 4

The primality of

HPF = 2^{2} + 1

and

HPF = 2^{3} - 1

also follows directly from that of 2, i.e. without relying on the primality of

p_{2} = 3

. Since

HPF = 2^{b} \pm 1

, for

b > 1

, satisfies (1)-(4) and (7), and

p_{2} \geq 3

, it follows that a lower bound of

p_{2}^{2}

is 9, i.e.

3^{2} \leq p_{2}^{2}

. From Proposition 1, every value of this HPF within the interval

[1, 9)

is, a priori, prime. Hence, the expressions

2^{2} + 1

and

2^{3} - 1

represent primes.

For

n = 1

, since 7 cannot be generated by an expression of the form

2^{b} + 1

, it follows that some primes may be represented by an HPF sum or a difference, not both. For

n = 2

, the number 7 can be represented by the HPF sum:

2^{2} + 3^{1}

Violation of condition (20), for

k = 1

, i.e. if

HPF \geq 3^{2}

, neither guarantees nor precludes the primality of

HPF = 2^{b} \pm 1 .

For example:

2^{4} + 1

and

2^{5} - 1

are both prime, but

2^{3} + 1

and

2^{4} - 1

are not.

3. Prime Generator Performance

In this section, the performance of the system (1), (2)-(4) and (7), viewed as a algebraic prime number generator, is evaluated theoretically and by using Monte Carlo simulation.

3.1. Definitions and Measures of Performance

From Proposition 1, the expression (1), subject to (2)-(4), (7), either generates a prime

> p_{n}

, or a coprime to

p_{1}, p_{2} \dots, p_{n}

, with at most k terms in its prime factorization, where

k = ⌊\frac{\log (HPF)}{\log (p_{n + 1})}⌋

.(25)

As discussed in the previous section, the special case,

k = 1

, implies that

HPF < p_{n + 1}^{2}

(26)

and thus, the HPF, given by (1), is a prime number in the semi-open interval [

p_{n + 1}, p_{n + 1}^{2})

. To facilitate the analysis of the “prime generating” performance of (1), its “prime generating power”,

P (n, k)

, is defined as a measure of how likely it is for (1) to generate a prime.

Definition 1. The “prime generating power”,

P (n, k)

, of an HPF, given by (1), subject to (2)-(4) and (7), is defined by

P (n, k) = \frac{Number of HPF primes in [p_{n + 1}^{k}, p_{n + 1}^{k + 1})}{Number of HPF outcomes in [p_{n + 1}^{k}, p_{n + 1}^{k + 1})}

.(27)

From the above definition, it follows that

P (n, k) \leq 1

. The quantity

P (n, k)

expresses the likelihood that (1) generates a prime number within a given value range. Next, it is shown that

P (n, k)

starts at 100% for

k = 1

and decreases as the value of

k

increases.

Corollary 1. For any

n \geq 1 : P (n, 1) = 1,

and

P (n, k) < 1

for

k \geq 2

Proof. If

k = 1

, from Proposition 1 and (20), it follows that (26) is true. Since the smallest non-prime having all its prime factors greater than

p_{n}

is equal to

p_{n + 1}^{2}

, the HPF expression, given by (1), will always generate a prime number in

[p_{n + 1}, p_{n + 1}^{2})

. Therefore, the numerator and denominator in (27) are equal, and thus

P (n, 1) = 1

. For higher values of

k

, the HPF can take non-prime values, and therefore

P (n, k) < 1

Proposition 1 implies that, within the value range

[p_{n + 1}, p_{n + 1}^{2})

, expression (1), subject to (2)-(4), (7) generates a prime number with certainty, i.e.

P (n, 1) = 100 %

. In the general case, i.e. for HPF values

\geq p_{n + 1}^{2}

, this percentage is

< 1

, i.e. the value of

P (n, k)

decreases as

k

increases, as described in Proposition 1. The variation of

P (n, k)

with respect to changes in the values of n and k is analyzed in the next section.

It is infeasible to exhaustively determine all possible HPF values in a given interval, since it cannot be precluded that, for some higher exponent values, the difference in (1) would not generate a relatively small prime. Consider, for example, the following HPF, where

n = 6

, given by

HPF = 5^{1} ∙ 13^{3} - 2^{4} ∙ 3^{2} ∙ 7^{1} ∙ 11^{1}

HPF = 10985 - 11088 = 103

(28)

represents a prime, since

HPF < p_{7}^{2}

, where

p_{7} = 17

. The two coprime terms in (28) are, approximately, 100 times greater than the value of the HPF. Hence, it is possible to generate primes in

[p_{n + 1}, p_{n + 1}^{2})

by subtracting coprime terms that are several orders of magnitude greater.

Under the assumption that (1) can generate every prime and coprime, it follows that evaluating its actual performance, given by

P (n, k)

, is equivalent to assessing its predicted performance,

\hat{P} (n, k)

, defined below.

Definition 2. The “predicted prime generating power”,

\hat{P} (n, k)

, of an HPF, given by (1), subject to (2)-(4) and (7), is defined by

\hat{P} (n, k) = \frac{A (n, k)}{A (n, k) + B (n, k)}

(29)

where

A (n, k)

is the number of primes in

[p_{n + 1}^{k}, p_{n + 1}^{k + 1})

, and

B (n, k)

is the number of composites in

[p_{n + 1}^{k}, p_{n + 1}^{k + 1})

, coprime to

p_{1}, p_{2} \dots, p_{n}

As previously mentioned,

\hat{P} (n, k)

is useful for two reasons:

(i) the computational complexity of computing all the solutions of (1), subject to (2)-(4) and (7), for

n \geq 10

easily exceeds the computational capabilities of a typical computer system, since the two terms comprising the difference in the HPF expression, given by (1), can reach extremely large values, even before generating an HPF prime within the desired range.

(ii) it is not known if every such prime and coprime can be represented by at least one solution in the form of (1).

In the next section, the theoretically predicted

\hat{P} (n, k)

and the actual

P (n, k)

, obtained by Monte Carlo simulation, are computed and compared.

3.2. Predicted vs. Simulated Performance

Since

B (n, k) = 0

for

k = 1

, it follows that

\hat{P} (n, 1) = 100 %

, for any HPF value in

[p_{n + 1}, p_{n + 1}^{2})

. Therefore, a single value is assigned to

\hat{P} (n, k)

within each interval

[p_{n + 1}^{k}, p_{n + 1}^{k + 1})

, starting with

\hat{P} (n, 1) = 1

for

k = 1

. For a range of

n, k

values, the number of primes and coprimes within each interval

[p_{n + 1}^{k}, p_{n + 1}^{k + 1})

is computed, and the corresponding value of

\hat{P} (n, k)

for that interval is evaluated.

To avoid the time-consuming component of performing prime factorization for each HPF value, the computation of

A (n, k)

B (n, k)

and

\hat{P} (n, k),

utilizes the list of the first 1M primes from

[12]

. The results are summarized in the following table.

Table 1. Predicted performance,

\hat{P} (n, k)

, for

n = 3, 4, 5

and

k = 1, \dots, 5

k	n = 3	n = 4	n = 5	Average
1	100%	100%	100%	100%
2	63.6%	67.9%	67.5%	66.4%
3	50.3%	52.6%	49.2%	50.7%
4	39.7%	41.2%	39.0%	40.0%
5	33.0%	34.1%	32.1%	33.1%

From Table 1, the values of

\hat{P} (n, k)

do not vary significantly for

n = 3, 4, 5

. This observation has an interesting practical implication when searching for primes in higher order intervals, i.e.

[p_{n + 1}^{k}, p_{n + 1}^{k + 1})

for

k > 1

: it implies that the likelihood that HPF is prime does not change significantly as

n

increases. The last column of Table 1 shows the average values for each

k

The above values of

\hat{P} (n, k)

are compared to

P (n, k)

, obtained by Monte Carlo simulation. To avoid runtime overflow errors, all exponent parameters in (1) are capped. The Monte Carlo simulation results are summarized in Table 2.

Table 2. Simulated performance,

P (n, k)

, for

n = 3, 4, 5

, and

k = 1, \dots, 5

k	n = 3	n = 4	n = 5	Average
1	100.0%	100.0%	100.0%	100.0%
2	66.7%	65.7%	65.6%	66.0%
3	52.4%	47.3%	50.9%	50.2%
4	38.3%	42.7%	37.6%	39.5%
5	29.4%	33.1%	32.9%	31.8%

From Tables 1 and 2, it follows that:

(i) The average prime-generation performance of the HPF Prime and Coprime Generator (HPF PCG for short) is 50% or higher within the HPF range

[p_{n + 1}, p_{n + 1}^{4})

, i.e. for

k \leq 3

(ii) When the HPF PCG generates a coprime number q, the value of

k

from (18) can be used to determine the maximum number of terms in the prime factorization of q. This can be used to eliminate a significant number of prime factor combinations that do not generate a product with the same last digit as q, making the prime factorization of HPF PCG coprimes more computationally efficient. This point is illustrated in Example 4.

Download: Download full-size image

Figure 1. Comparison of average predicted vs. simulated HPF prime-generation performance, for

k = 1, \dots, 5

The results in Tables 1 and 2 are shown graphically in Figure 1. The average values of predicted performance,

\hat{P} (n, k)

, and simulated performance,

P (n, k)

, are not significantly different for

k = 1, \dots, 5

Example 4. For

n = 4

, the HPF given by

HPF = 2^{1} ∙ 5^{4} + 3^{2} ∙ 7^{1} = 1250 + 63 = 1313

HPF = 13 ∙ 101

(30)

generates a coprime number. Applying (18), it follows that

k = 2

. Therefore, the prime factorization of 1313 has at most 2 terms, i.e. a maximum prime factor cardinality of 2, and since HPF is coprime, it follows that HPF has exactly 2 prime factors.

Let p and q be primes, such that

p ∙ q = 1313

.(31)

Since p, q can only end in 1, 3, 7 or 9, for their product to end in 3, there can only be four last-digit combinations: (1,3), (3,1), (7,9), (9,7). Also, since

\min (p, q) \geq 11

, it follows that

\max (p, q) \leq 119

. From Proposition 1, it follows that HPF is coprime to the first 4 primes. Thus, it is only necessary to test if HPF is divisible by an odd number w, where

w \in [11, 119]

, and

w mod 10 = 1

w mod 10 = 7

, i.e. a total of 44 possible numbers. This subset of possible factors may be further reduced, from 44 to 26, by excluding multiples of 3 or 7, e.g. 21, 27, 33, 39, 49 etc., generating an additional reduction of 41%. The remaining values are coprime with respect to the first 4 primes, and since

w < 11^{2}

, they are prime. The unique prime factorization solution is easily determined to be

p = 13

and

q = 101

. This process significantly reduces the potential number of prime factors of an HPF-generated coprime, thus increasing computational efficiency. In general, the factorization of any HPF-generated coprime results in the determination of at least two primes greater than

p_{n}

As discussed in the previous example, the increased computational efficiency in searching for prime factors of HPF-generated coprimes is a result of the a priori knowledge of their maximum prime factor cardinality, established by Proposition 1 (part 3). In general, the computational savings in the prime factorization of an HPF coprime in [

p_{n + 1}^{k}, p_{n + 1}^{k + 1})

, generated by (1), subject to (2)-(4) and (7), are twofold:

(i) none of the n primes

p_{1}, p_{2} \dots, p_{n}

should be considered, since they are not prime factors of any HPF coprime, and

(ii) since the prime factor cardinality of the HPF coprime is at most equal to k, where k is given by (18), the subset of admissible prime factors, for each cardinality scenario, is reduced by considering only those candidate primes whose product ends in the same digit as the HPF coprime. Moreover, for each cardinality scenario, upper and lower bounds for the prime factors of the HPF can be derived, as discussed below.

Consider the case where the total prime factor cardinality of the HPF coprime equals m, where

m \in [2, k

]. It then follows that the upper and lower bounds for each prime factor

q_{j} > p_{n}

, of the HPF, are given by

HPF = \prod_{j = 1}^{m} q_{j}

(32)

p_{n + 1} \leq \min_{j} (q_{j}) \leq ⌊\sqrt[m]{HPF}⌋

(33)

\max_{j} (q_{j}) \leq ⌊\frac{HPF}{p_{n + 1}^{m - 1}}⌋

.(34)

Given that total prime factor cardinality includes any repeating prime factors, as explained in Section 2.1, (32) does not imply that the

q_{j}

j = 1, \dots, m

, are different. For example, if

HPF = 13^{4}

, then

m = 4

and

q_{j} = 13

, for

j = 1, \dots, 4 .

Some of the computational efficiencies, described above, materialize even when the lower bound,

p_{n} + 2

, is used, instead of

p_{n + 1}

. Given that

p_{n} < p_{n} + 2 \leq p_{n + 1}

, it follows that no HPF prime factor is less than

p_{n} + 2

. Since there are at most k* prime factors, where

k^{*}

is given by

k^{*} = ⌊\frac{\log (HPF)}{\log (p_{n} + 2)}⌋

(35)

the next step is to proceed by considering feasible factors for each cardinality value, up to

k^{*}

. Any odds not coprime to

p_{1}, p_{2} \dots, p_{n}

, cannot be factors of the HPF coprime, since this would imply that the HPF is not coprime to

p_{1}, p_{2} \dots, p_{n}

. If the total prime factor cardinality of the HPF coprime is m, where

m \in [2, k^{*}

], the modified upper and lower bounds for each prime factor

q_{j}

, are given by:

p_{n} + 2 \leq \min_{j} (q_{j}) \leq ⌊\sqrt[m]{HPF}⌋

(36)

\max_{j} (q_{j}) \leq ⌊\frac{HPF}{{(p_{n} + 2)}^{m - 1}}⌋

.(37)

As expected, the modified bounds, given by (36)-(37) are weaker than those in (33)-(34), respectively.

Example 5. Consider the factorization of the coprime HPF (

n = 4

), generated by

HPF = 2^{4} ∙ 3^{3} ∙ 7^{2} - 5^{3} = 2899 = 13 ∙ 223

.(38)

Since no prime factor of 2899 is less than 7+2 = 9, it follows that

k^{*} = ⌊\frac{\log (2899)}{\log (9)}⌋ = 3 .

(39)

and the total prime factor cardinality of 2899 is at most 3.

Consider the first case, where the prime factor cardinality, m, is

m = 2

, i.e. 2899 is assumed to be represented by

2899 = q_{1} ∙ q_{2}

(40)

where

q_{1}, q_{2}

are prime. It follows, from (36)-(37), that

9 \leq \min (q_{1}, q_{2}) \leq 53

(41)

\max (q_{1}, q_{2}) \leq 321 .

(42)

From the subset of odd numbers satisfying (41)-(42), only those with compatible last digits need to be considered, i.e. whose product ends in 9. There are 4 possible combinations:

q_{1}

ends in 1 then

q_{2}

should end in 9

q_{1}

ends in 9 then

q_{2}

should end in 1

q_{1}

ends in 3 then

q_{2}

should end in 3

q_{1}

ends in 7 then

q_{2}

should end in 7.

Note that #1 and #2 are symmetric, and therefore only one of those should be considered, something that further increases the computational efficiency of the prime factor search. This search yields two factors of 2899, coprime to

2, 3, 5, 7

: 13 and 223.

It remains to be established that these factors are prime. Since

13 < 81

, it follows that 13 is smaller than the smallest HPF coprime, therefore 13 is prime. Since the smallest prime factor of 223 cannot exceed

⌊\sqrt[2]{223}⌋ = 14

, only 11 and 13 need to be considered. Since neither 11 nor 13 are factors, 223 is a prime factor. Given that prime factors are unique, the case m = 3 need not be considered.

4. Conclusions

Primes greater than

p_{n}

, for

n \geq 2

, and coprimes with prime factors

> p_{n}

, can be generated algebraically using the HPF expression given by (1), subject to (2)-(4) and (7). The sufficiency condition (18) gives the maximum total prime factor cardinality of the HPF. For the special case where the cardinality bound,

k

, equals 1, the HPF is a priori prime, i.e. its primality can be established without computing its numerical value.

In cases where the HPF generates a coprime, the lower and upper bounds on its prime factors, and the upper bound on the total cardinality of its prime factorization (including any prime factors with multiplicity >1) result in additional computational efficiencies in the prime factor search. In addition, the prime factorization of any HPF coprime yields at least two primes greater than

p_{n}

The methodology described in this paper may be used to algebraically represent, generate, efficiently compute, factor and analyze larger primes and coprimes. In the case of prime factorization of HPF-generated coprimes, computational efficiencies are realized even when weaker non-prime bounds are used.

The approach described in the paper unifies the structural characteristics of primes and coprimes, using a common algebraic representation. Such an approach can be a useful tool for studying their distribution and interrelationships.

Abbreviations

FTA	Fundamental Theorem of Arithmetic
HPF	Hybrid Prime Factorization
PCG	Prime and Coprime Generator

Author Contributions

Ioannis Papadakis is the sole author. The author read and approved the final manuscript.

Conflicts of Interest

The author declares no conflicts of interest.

References

[1]	Euclid, Elements, proposition 7.32 (p. 219) and 9.20 (p. 271) from the Greek text of J. L. Heiberg (1883-1885), based on Euclidis Elementa, edited and translated in English by Richard Fitzpatrick [Online]. Available: https://farside.ph.utexas.edu/Books/Euclid/Elements.pdf
[2]	S. Hawking, God Created the Integers: The mathematical breakthroughs that changed history; Propositions 7.32 (p. 92) and 9.20 (p. 101); Running Press: Philadelphia, PA, USA, 2005.
[3]	G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, New York NY, USA: Oxford University Press, 2008 (6th edition), p. 23.
[4]	C. K. Caldwell, The Prime Pages: Goldbach's conjecture. [Online]. Available: https://t5k.org/glossary/page.php?sort=GoldbachConjecture
[5]	C. K. Caldwell, The Prime Pages: Prime Conjectures and Open Questions. [Online]. Available: https://t5k.org/notes/conjectures/
[6]	T. Oliveira e Silva, S. Herzog and S. Pardi, “Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4∙10¹⁸”, Mathematics of Computation, 83 (2014), 2033-2060, November 2013. Available: https://www.ams.org/journals/mcom/2014-83-288/S0025-5718-2013-02787-1/S0025-5718-2013-02787-1.pdf
[7]	J. Derbyshire, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics; Plume: Washington, DC, USA, 2004; pp. 99–101.
[8]	I. N. M. Papadakis, On the Universal Encoding Optimality of Primes. Mathematics 2021, 9 (24), 3155. https://doi.org/10.3390/math9243155
[9]	I. N. M. Papadakis, Algebraic Representation of Primes by Hybrid Factorization. Math. Comput. Sci. 2024, 9(1), 12-25. https://doi.org/10.11648/j.mcs.20240901.12
[10]	R. L. Rivest, A. Shamir, L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Commun. ACM 1978, 21, 120–126. Available: http://people.csail.mit.edu/rivest/Rsapaper.pdf
[11]	D.-T. Dam, T.-H. Tran, V.-P. Hoang, C.-K. Pham, T.-T. Hoang, A Survey of Post-Quantum Cryptography: Start of a New Race. Cryptography 2023, 7, 40. Available: https://doi.org/10.3390/cryptography7030040
[12]	C. K. Caldwell, The Prime Pages: The first fifty million primes. Available: https://t5k.org/lists/small/millions/

Cite This Article

Plain Text BibTeX RIS

APA Style

Papadakis, I. (2024). Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Mathematics and Computer Science, 9(3), 57-63. https://doi.org/10.11648/j.mcs.20240903.12

Copy | Download

ACS Style

Papadakis, I. Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Math. Comput. Sci. 2024, 9(3), 57-63. doi: 10.11648/j.mcs.20240903.12

Copy | Download

AMA Style

Papadakis I. Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Math Comput Sci. 2024;9(3):57-63. doi: 10.11648/j.mcs.20240903.12

Copy | Download

@article{10.11648/j.mcs.20240903.12,
  author = {Ioannis Papadakis},
  title = {Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums
},
  journal = {Mathematics and Computer Science},
  volume = {9},
  number = {3},
  pages = {57-63},
  doi = {10.11648/j.mcs.20240903.12},
  url = {https://doi.org/10.11648/j.mcs.20240903.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20240903.12},
  abstract = {The algebraic structure and distribution of prime numbers remain two of the most fundamental problems in mathematics. The Fundamental Theorem of Arithmetic, proved by Euclid, and Goldbach’s conjecture, while universal in scope with respect to how numbers can be represented multiplicatively or additively, do not provide insights into the structure of primes. Similarly, the definition of a prime −as a number divisible only by 1 and itself− or a sieve algorithm, commonly used to generate primes by successively eliminating multiples, offer no insight into the structure of primes. The powerful and persistent consideration of prime numbers as universal “arithmetic quanta” has not necessitated an equally powerful need for parallel research into a deeper and possibly more insightful explanation of primeness, that is, a better understanding of “why” a number is prime. In this paper, prime and coprime numbers are represented and generated by algebraic expressions. Specifically, given the first n primes, p1, p2,…, pn, sufficient conditions are given for expressing primes greater than pn, and coprimes with prime factors greater than pn, as algebraic functions of p1, p2,…, pn. Thus, primality and co-primality are shown to be mathematical properties with inherently evolutionary algebraic characteristics, since larger primes and coprimes can be generated algebraically from smaller ones. The methodology described in the paper can be a useful tool in the study and analysis of the complexity, structure, interrelationships and distribution of primes and coprimes.
},
 year = {2024}
}

Copy | Download

TY  - JOUR
T1  - Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums

AU  - Ioannis Papadakis
Y1  - 2024/08/15
PY  - 2024
N1  - https://doi.org/10.11648/j.mcs.20240903.12
DO  - 10.11648/j.mcs.20240903.12
T2  - Mathematics and Computer Science
JF  - Mathematics and Computer Science
JO  - Mathematics and Computer Science
SP  - 57
EP  - 63
PB  - Science Publishing Group
SN  - 2575-6028
UR  - https://doi.org/10.11648/j.mcs.20240903.12
AB  - The algebraic structure and distribution of prime numbers remain two of the most fundamental problems in mathematics. The Fundamental Theorem of Arithmetic, proved by Euclid, and Goldbach’s conjecture, while universal in scope with respect to how numbers can be represented multiplicatively or additively, do not provide insights into the structure of primes. Similarly, the definition of a prime −as a number divisible only by 1 and itself− or a sieve algorithm, commonly used to generate primes by successively eliminating multiples, offer no insight into the structure of primes. The powerful and persistent consideration of prime numbers as universal “arithmetic quanta” has not necessitated an equally powerful need for parallel research into a deeper and possibly more insightful explanation of primeness, that is, a better understanding of “why” a number is prime. In this paper, prime and coprime numbers are represented and generated by algebraic expressions. Specifically, given the first n primes, p1, p2,…, pn, sufficient conditions are given for expressing primes greater than pn, and coprimes with prime factors greater than pn, as algebraic functions of p1, p2,…, pn. Thus, primality and co-primality are shown to be mathematical properties with inherently evolutionary algebraic characteristics, since larger primes and coprimes can be generated algebraically from smaller ones. The methodology described in the paper can be a useful tool in the study and analysis of the complexity, structure, interrelationships and distribution of primes and coprimes.

VL  - 9
IS  - 3
ER  -

Copy | Download

Author Information

Ioannis Papadakis

Independent Researcher, Charlotte, USA

Contact Email

http://orcid.org/0000-0001-9245-0751

Download PDF

Figure 1

Figure 1. Comparison of average predicted vs. simulated HPF prime-generation performance, for $k = 1, \dots, 5$ .

Plain Text BibTeX RIS

APA Style

Papadakis, I. (2024). Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Mathematics and Computer Science, 9(3), 57-63. https://doi.org/10.11648/j.mcs.20240903.12

Copy | Download

ACS Style

Papadakis, I. Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Math. Comput. Sci. 2024, 9(3), 57-63. doi: 10.11648/j.mcs.20240903.12

Copy | Download

AMA Style

Papadakis I. Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums. Math Comput Sci. 2024;9(3):57-63. doi: 10.11648/j.mcs.20240903.12

Copy | Download

@article{10.11648/j.mcs.20240903.12,
  author = {Ioannis Papadakis},
  title = {Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums
},
  journal = {Mathematics and Computer Science},
  volume = {9},
  number = {3},
  pages = {57-63},
  doi = {10.11648/j.mcs.20240903.12},
  url = {https://doi.org/10.11648/j.mcs.20240903.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20240903.12},
  abstract = {The algebraic structure and distribution of prime numbers remain two of the most fundamental problems in mathematics. The Fundamental Theorem of Arithmetic, proved by Euclid, and Goldbach’s conjecture, while universal in scope with respect to how numbers can be represented multiplicatively or additively, do not provide insights into the structure of primes. Similarly, the definition of a prime −as a number divisible only by 1 and itself− or a sieve algorithm, commonly used to generate primes by successively eliminating multiples, offer no insight into the structure of primes. The powerful and persistent consideration of prime numbers as universal “arithmetic quanta” has not necessitated an equally powerful need for parallel research into a deeper and possibly more insightful explanation of primeness, that is, a better understanding of “why” a number is prime. In this paper, prime and coprime numbers are represented and generated by algebraic expressions. Specifically, given the first n primes, p1, p2,…, pn, sufficient conditions are given for expressing primes greater than pn, and coprimes with prime factors greater than pn, as algebraic functions of p1, p2,…, pn. Thus, primality and co-primality are shown to be mathematical properties with inherently evolutionary algebraic characteristics, since larger primes and coprimes can be generated algebraically from smaller ones. The methodology described in the paper can be a useful tool in the study and analysis of the complexity, structure, interrelationships and distribution of primes and coprimes.
},
 year = {2024}
}

Copy | Download

TY  - JOUR
T1  - Representation and Generation of Prime and Coprime Numbers by Using Structured Algebraic Sums

AU  - Ioannis Papadakis
Y1  - 2024/08/15
PY  - 2024
N1  - https://doi.org/10.11648/j.mcs.20240903.12
DO  - 10.11648/j.mcs.20240903.12
T2  - Mathematics and Computer Science
JF  - Mathematics and Computer Science
JO  - Mathematics and Computer Science
SP  - 57
EP  - 63
PB  - Science Publishing Group
SN  - 2575-6028
UR  - https://doi.org/10.11648/j.mcs.20240903.12
AB  - The algebraic structure and distribution of prime numbers remain two of the most fundamental problems in mathematics. The Fundamental Theorem of Arithmetic, proved by Euclid, and Goldbach’s conjecture, while universal in scope with respect to how numbers can be represented multiplicatively or additively, do not provide insights into the structure of primes. Similarly, the definition of a prime −as a number divisible only by 1 and itself− or a sieve algorithm, commonly used to generate primes by successively eliminating multiples, offer no insight into the structure of primes. The powerful and persistent consideration of prime numbers as universal “arithmetic quanta” has not necessitated an equally powerful need for parallel research into a deeper and possibly more insightful explanation of primeness, that is, a better understanding of “why” a number is prime. In this paper, prime and coprime numbers are represented and generated by algebraic expressions. Specifically, given the first n primes, p1, p2,…, pn, sufficient conditions are given for expressing primes greater than pn, and coprimes with prime factors greater than pn, as algebraic functions of p1, p2,…, pn. Thus, primality and co-primality are shown to be mathematical properties with inherently evolutionary algebraic characteristics, since larger primes and coprimes can be generated algebraically from smaller ones. The methodology described in the paper can be a useful tool in the study and analysis of the complexity, structure, interrelationships and distribution of primes and coprimes.

VL  - 9
IS  - 3
ER  -

Copy | Download