Gnouma Jérôme Kadouno
Independent Researcher, Conakry, Guinea.
DOI: 10.4236/apm.2026.167024   PDF    HTML   XML   33 Downloads   225 Views   Citations

Abstract

The original online version of this article (Kadouno, G.J. (2025) Analysis of Multiplication Tables by Sum, Difference and Product: A New Approach to Primality. Advances in Pure Mathematics, 15, 505-517. https://doi.org/10.4236/apm.2025.158025) unfortunately contains mis-takes in the primality test (Sections 6-9). The author wishes to correct the scope of the primality claim, replace one numerical example, and restate the logarithmic version as a sieve with a proven performance guarantee. State-ments introduced in this erratum are labelled with the prefix E (Proposition E1, Theorem E1, ...) to distinguish them from those of the original article, to which we refer by their original numbers.

Keywords

Erratum

Share and Cite:

1. The First Test Condition Is Trivial

For every $n\ge 2$ and every $k\ge 1$, the tabular product satisfies ${\Pi }_{\text{T}}\left(k,n\right)=n^{k}k!$, hence $n|{\Pi }_{\text{T}}\left(k,n\right)$ . The condition

${\Pi }_{\text{T}}\left(k,n\right)\equiv 0\left(\mathrm{mod}n\right)$

therefore holds for all $n$ and carries no information. The decision rests entirely on the second condition, $\gcd \left(n,k!\right)=1$, equivalently $\gcd \left(n,k\#\right)=1$ . Theorems 3 and 4 should be restated with the first condition removed.

2. The Logarithmic Depth Does Not Yield a Primality Test

Proposition E1 (Validity threshold) Let $n\ge 2$ , let $K\ge 1$ be an integer and $K\#={\displaystyle {\prod }_{p\le K}p}$ the primorial (the product of the primes $\le K$ ). The implication

$\gcd \left(n,K\#\right)=1\Rightarrow n\text{prime}$

holds whenever $K\ge \sqrt{n}$ .

Proof. Sufficiency. If $K\ge \sqrt{n}$ and $n$ is composite, its least prime factor $p$ satisfies $p\le \sqrt{n}\le K$ ; thus $p|K\#$ and $p|n$, so $\gcd \left(n,K\#\right)\ge p>1$ .

Contrapositively, $\gcd =1$ forces $n$ prime.

Sharpness. The critical case is the square of a prime. For $n=p^2$ the least prime factor is $p=\sqrt{n}$ . If $K<\sqrt{n}$, no prime $\le K$ divides $n$, so $\gcd \left(n,K\#\right)=1$ while $n$ is composite: the implication fails.

The adaptive depth is $k\left(n\right)=\lfloor C\left(n\right){\log }_{2}n\rfloor$ with $C\left(n\right)=3+\lfloor \frac{1}{3}{\log }_{10}n\rfloor$ . Since $C\left(n\right)$ is itself unbounded, growing like $\frac{1}{3}{\log }_{10}n$, one has $k\left(n\right)=\Theta \left({\left(\log n\right)}^2\right)$, which is still far below $\sqrt{n}$ for large; the logarithmic version is therefore necessarily a sieve, not a test. Two explicit instances, both within the range the article claimed reliable:

l $n={101}^2=10201$ : $C\left(n\right)=4$, $k\left(n\right)=\lfloor 4{\log }_{2}10201\rfloor =53$ . As $101>53$, $\gcd \left(10201,53\#\right)=1$, so the procedure returns prime for a perfect square.

l $n=1000003\times 1000033=1000036000099$ : $C\left(n\right)=7$, $k\left(n\right)=279$ . Both prime factors exceed 279, so $\gcd \left(n,279\#\right)=1$ and the procedure returns prime for a composite.

3. Correction of Example 5 (Section 9.2.3)

Example 5 (Section 9.2.3 of the original article) presents $n=999999000001$ as composite, equal to $\left({10}^6+1\right)\left({10}^6-1\right)$ with factor $101\times 9901001$ . However

$\left({10}^6+1\right)\left({10}^6-1\right)={10}^{12}-1=999999999999,$

which factors as $3^3\cdot 7\cdot 11\cdot 13\cdot 37\cdot 101\cdot 9901$, while $101\times 9901001=1000001101$ ; neither equals 999999000001, which is in fact prime. [1] The example should be replaced by a composite with a small prime factor, for instance $n={10}^{12}-1$ above, whose factor 3 is detected at once.

4. Corrected Statement of the Criterion

Theorem E1 (Primality criterion by coprimality; replaces Theorems 3-4) For

$n\ge 2$ , let $k=\lfloor \sqrt{n}\rfloor$ . Then

$n\text{prime}\iff \gcd \left(n,k\#\right)=1.$

Proof. By the argument of Proposition E1, with $K=\lfloor \sqrt{n}\rfloor$ : the least prime factor $p$ of a composite $n$ satisfies $p\le \sqrt{n}$, hence $p\le \lfloor \sqrt{n}\rfloor =k$ since $p$ is an integer. (Here the depth is the fixed value $k=\lfloor \sqrt{n}\rfloor$, in contrast with the adaptive depth $k\left(n\right)$ of Section 5.)

Remark E1 (Status of the criterion) Under the bound $k=\lfloor \sqrt{n}\rfloor$ the criterion is decision-equivalent to trial division up to $\sqrt{n}$ : it decides the same thing on every input, namely the existence of a prime factor $\le \sqrt{n}$ . It differs as a procedure—a reformulation of primality as coprimality, $n$ prime $\iff$ $n$ coprime to the product of the primes $\le \sqrt{n}$ : by the prime number theorem [1] [2] , $\log \left(k\#\right)=\vartheta \left(k\right)~k$ , so $k\#$ has on the order of $\sqrt{n}$ bits. The contribution of this work is the proposed tabular framework and its associated reformulation.

5. Revised Section 8: From Test to Sieve

Definition E1 (Logarithmic primorial sieve) For $n\ge 10$ , let $C\left(n\right)=3+\lfloor \frac{1}{3}{\log }_{10}n\rfloor$ , depth $k\left(n\right)=\lfloor C\left(n\right){\log }_{2}n\rfloor$ and $k\left(n\right)\#={\displaystyle {\prod }_{p\le k\left(n\right)}p}$ . The sieve returns composite (certain) when $\gcd \left(n,k\left(n\right)\#\right)>1$ ; otherwise, when $\gcd \left(n,k\left(n\right)\#\right)=1$, it reports no prime factor $\le k\left(n\right)$ —inconclusive as to primality. In particular $\gcd \left(n,k\left(n\right)\#\right)=1$ does not imply that $n$ is prime. The restriction $n\ge 10$ is necessary: for $n\le 9$ the adaptive depth satisfies $k\left(n\right)\ge n$, so the candidate $n$ itself lies among the primes $\le k\left(n\right)$ ; a prime $n$ then divides $k\left(n\right)\#$ and is wrongly reported composite (this affects precisely the primes $2,3,5,7$ ). These small cases are settled directly by the exact bound $k=\lfloor \sqrt{n}\rfloor$ of Theorem E1, for which $k<n$, so no prime can be its own factor.

Theorem E2 (Performance, via Mertens) By Mertens’ third theorem [3] , the density of integers with no prime factor $\le y$ is

${\displaystyle \prod }_{p\le y}\left(1-\frac{1}{p}\right)=\frac{{\text{e}}^{-\gamma }}{\ln y}\left(1+o\left(1\right)\right),$

with $\gamma \approx 0.5772$ . Here $C=C\left(n\right)=3+\lfloor \frac{1}{3}{\log }_{10}n\rfloor ~\ln n/\left(3\ln 10\right)$, so

$y=k\left(n\right)\sim C\left(n\right)\frac{\ln n}{\ln 2}~\frac{{\left(\ln n\right)}^2}{3\ln 2\ln 10},\ln k\left(n\right)~2\ln \ln n.$

The surviving fraction is therefore

$S\left(n\right)\approx \frac{{\text{e}}^{-\gamma }}{\ln k\left(n\right)}~\frac{{\text{e}}^{-\gamma }}{2\ln \ln n}\to 0\text{as}n\to \infty .$

Hence the eliminated fraction of composites tends to 1, while the residual $S\left(n\right)$ stays strictly positive for every finite $n$ and decays like $1/\ln \ln n$ . These two facts are inseparable: they make the procedure an asymptotically near-perfect filter and, at the same time, forbid it the status of a complete test. Numerical validation (uniform sampling per band) confirms the analysis:

At the smallest band the depth already exceeds $\sqrt{n}$ ( $k\left({10}^3\right)=39>31.6\approx \sqrt{{10}^3}$ ), so there the sieve is locally complete and eliminates every composite; the asymptotic estimate ${\text{e}}^{-\gamma }/\ln k\left(n\right)$, valid for large $n$, correspondingly overestimates the survival rate in this regime.

Blind set. The composites missed at depth $k\left(n\right)$ form

$B\left(n\right)=\left\{m\text{composite}:\text{all}\text{prime}\text{factors}\text{of}m\text{are}>k\left(n\right)\right\},$

dominated by the semiprimes $m=pq$ with $k\left(n\right)<p\le q$ and containing the squares $p^2$ with $p>k\left(n\right)$ . The sieve is blind precisely on $B\left(n\right)$, and its cryptographically relevant core—the balanced semiprimes $pq$ with both factors large—is exactly where factoring itself is hard; the perfect squares and the strongly unbalanced semiprimes it also misses are, by contrast, easy to factor.

Complete two-stage test. Hence the correct, efficient architecture: the logarithmic primorial sieve as a first stage (eliminating ≈94% of composites at negligible cost), followed by a completion test on the survivors—deterministic Miller-Rabin [4] below known bounds, or BPSW [5] . The sieve plays the legitimate role of a front-end filter; completeness comes from the modular stage. The depth $k\left(n\right)$ is tunable: a larger constant lowers the survivor count as ${\text{e}}^{-\gamma }/\ln k\left(n\right)$, at the cost of a primorial of size ${\text{e}}^{\vartheta \left(k\right)}$ .

6. Results That Remain Valid

1) The tabular framework. The identities ${\Sigma }_{\text{T}}\left(k,n\right)=nk\left(k+1\right)/2$, ${\Delta }_{\text{T}}\left(a,b,n\right)=\left(b-a\right)n$ and ${\Pi }_{\text{T}}\left(k,n\right)=n^{k}k!$ are exact and retain their unifying and pedagogical value.

2) Carmichael numbers. The rejection result (Theorem 5 of the original article) uses the bound $k=\lfloor \sqrt{n}\rfloor +1$, i.e. the regime $k\ge \sqrt{n}$, and remains valid: a Carmichael number $n$ is squarefree with at least three prime factors, so its least prime factor satisfies $p<n^{1/3}<\sqrt{n}$ and is detected. This property must be attached to the $\sqrt{n}$ bound, not to the logarithmic depth, which rejects only those Carmichael numbers having a prime factor $\le k\left(n\right)$ .

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Hardy, G.H. and Wright, E.M. (2008) An Introduction to the Theory of Numbers. 6th Edition, Oxford University Press, Oxford.
[2]	Tenenbaum, G. (1995) Introduction to Analytic and Probabilistic Number Theory. Cambridge University Press, Cambridge.
[3]	Mertens, F. (1874) Ein Beitrag zur analytischen Zahlentheorie. Journal fur die Reine und Angewandte Mathematik, 78, 46-62.
[4]	Rabin, M.O. (1980) Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12, 128-138.[CrossRef]
[5]	Baillie, R. and Wagstaff, S.S. (1980) Lucas Pseudoprimes. Mathematics of Computation, 35, 1391-1417.[CrossRef]