Balmoral Software
This table can be modified in such a way as to include only distinct numbers, shown in darker text above. Duplicate products are excluded from the modified table; for example, the entry of 20 in row 2 and column 10 is not shown since it appears in row 4 and column 5 of a smaller table, closer to the diagonal.
A consistent selection criterion can be established for all arithmetic operators that identifies distinct entries in the associated tables. This criterion consists of picking an entry occurring in the smallest square table, which in most cases is equivalent to selecting entries with row and column indices that are closer together than any others producing the same table entry. For commutative operators, the arithmetic table is symmetric with respect to the main diagonal extending from the upperleft corner to the lowerright one. By convention, entries in the lowertriangular portion of arithmetic tables for commutative operators are excluded from consideration as distinct entries since they already appear in the upper region. Excluding the uppertriangular region instead would produce the same patterns, but with rows and columns transposed.
The selection criterion described above can be applied to table entries in any order, producing the same result.
Let R and C denote the row and column indices in an N x N arithmetic table,
Multiplication: A distinct product in the table selected to minimize the associated row and column indices has R and C closer together than any other factor pair having a product equal to RC. Equivalently, R and C are central divisors, as defined below.
Division: A quotient in lowest terms satisfies the selection criterion, since any other fraction with the same value has both numerator and denominator that are larger multiples of those in the lowestterms formulation, and therefore farther apart. The row and column indices of a distinct table entry have no common factors; that is, their greatest common divisor (gcd) is 1.
Addition: As with the preceding operations, a distinct sum in the
addition table selected to minimize the associated row and column indices has R
and C closer together than any other factor pair having the same sum
Subtraction: A distinct entry in the subtraction table is selected to minimize both of the associated row and column indices since the difference between the indices is fixed. This occurs when the row or column index is at its minimum value of 1. As a result, distinct entries occur in the first row and first column of the table.
Summary:
Operation  Selection criterion for distinct entries 

Multiplication  {R,C} are central divisors 
Division  gcd(R,C) = 1 
Addition  C  R is 0 or 1 
Subtraction  min{R,C} = 1 
We'll explore these patterns in the sections below.
As the factor x increases towards its limit , its paired factor N/x decreases towards the same limit. Therefore, the central divisors of N have the property that they are closer together than any other factor pair of N. For example, {18,20} are the central divisors of their product 360. But {6,74} are not the central divisors of 444 since 12 x 37 = 444 and {12,37} are closer together.
The factors a and N/a above are referred to as the lesser central divisor (LCD) and greater central divisor (GCD) of N. Capital letters are always used in this paper for these acronyms, to avoid confusion with greatest common divisor (gcd). By convention, the row index is the LCD and the column index the GCD of any product present in the MMT. LCDs and GCDs are listed as OEIS sequences A033676 and A033677, respectively. The frequency distributions of LCDs and GCDs are discussed in a subsequent section.
A factor pair {a,b} is a set independent of the size order of its elements, but we usually apply the convention of listing the smaller factor first when the relative factor sizes are known.
Obviously, {a,b} are always central divisors when a = b. Another result is that
{1,p} are central divisors if and only if
(a  1)(b  1) + 1 = (1  1/a)ab  a + 2,then by Lemma 4, any column index with a as its LCD will have an unbroken segment of dark pixels starting at the line
R = (1  1/a)C  a + 2and extending vertically down to the main diagonal R = C. For a ≥ 2, the slopes of these lines are 1/2, 2/3, 3/4, 4/5 and so on, as shown by the yellow annotations in the preceding and following diagrams. In the case of a primenumbered column, we have
When C is a square, a reaches its maximum value of and the top of the vertical segment of dark pixels occurs at row
By Lemma 4 and Lemma 9, this minimum value of R is greater than or equal to the lower limit for R for nonsquare values of C, so there is always a solid band of entries in the MMT between the main diagonal and a narrow parabola above it.
Analogously for a row R with central divisors {a,b}, a ≤ b,
(a + 1)(b + 1)  1 = (1 + 1/a)ab + a,and any row index R with a as its LCD will have an unbroken segment of dark pixels extending horizontally from the main diagonal and ending at the line
C = (1 + 1/a)R + a,which can be written
R = [1  1/(a + 1)]C  a^{2}/(a + 1)These lines have the same slopes and nearly the same intercepts as those for the column segments:


Next, we consider columns that are multiples of 3. To exclude the shadow line already considered in the first example, we'll examine columns that are odd multiples of 3
Applying Lemma 10 with a = R, b = C and k = 3, all MMT entries are blank in the top third of the table where
R ≤ C/3  1A shadow line is apparent at R = (2/3)C  1 due to significantly more numerous central divisors in the third of the table closest to the diagonal than in the middle third. For the subset of column indices that are triples of a prime, all entries below the shadow line are central divisors, and exactly half of the entries above the line:
Proof. Let C = 3p for a prime p and consider the lowest third of the MMT:
2C/3  1 ≤ R ≤ CSince {3,p} are central divisors by Lemma 3 and the above inequality is contained within2p  1 ≤ R ≤ 3p
2p  1 ≤ R ≤ 4p + 3,then the conditions of Lemma 4 are met with a = 3, b = p and m = R, and so {R,3p} are central divisors.
In the adjacent middle third of the table, we have
C/3 ≤ R ≤ 2C/3  2By Lemma 12, {R,3p} are central divisors if and only if R is odd, QED.p ≤ R ≤ 2p  2
Additional shadow lines can be identified in a similar manner for other divisors of C, but they become increasingly faint since more columns are excluded in order to mask the shadow lines from previous selections.
The entries identified in both sections above account for more than 90% of the entries in the MMT and its most significant patterns:
Let F(N) denote the number of entries in the N x N MMT (tabulated as OEIS sequence A027424). Then
H(N) = F(N)/N^{2}is the fraction of table entries that are distinct. The first few values of F(N) and H(N) are:
The mathematician Paul Erdős proved in 1955 [1,2] that
F(1) = 1 H(1) = 1 F(2) = 3 H(2) = 3/4 F(3) = 6 H(3) = 2/3 F(4) = 9 H(4) = 9/16
The convergence is relatively slow, as can be seen in the chart below. Due to the influence of primes, H has a locally nonmonotonic behavior:
A result by Ford [3] shows that H(N) is bounded by
for N ≥ 3, where δ = 1  (1 + log log 2)/log 2 = 0.08607. These bounds are shown in the preceding diagram with
Only quotients created from relativelyprime numerator and denominator are shown in the MDT, equivalent to them having a greatest common divisor (gcd) of 1. As a result, there is an obvious symmetry in the table with respect to the main diagonal. Extending the MDT to larger sizes produces a repetitious complexity. Again representing table entries by dark pixels, the
This is a plan view of Euclid's orchard.
Entries described in the preceding two sections are shown below for the
600 x 600
The points (R,C) form ascending diagonals of included entries over the entire
MDT. As p increases from 2 to N, then
If R  C = 1, then the entry R/C = R/(R ± 1) is in lowest terms since the numerator and denominator are consecutive integers and therefore coprime. As a result, all entries on the two diagonals adjacent to the main diagonal are included.
If R  C is a prime p, then p < N and the table entry is
which cannot be a quotient of integers since . Therefore, R/C is in lowest terms. However, if
so the table entry is not in lowest terms. Therefore, the entries on primenumbered descending diagonals are included, except at intervals of p.
The entries described in the preceding two sections are shown below for the
The behavior of descending diagonals accounts for the fuzziness adjacent to the main diagonal, where first every table entry is present
Entries classified in all of the previous sections are shown here for the
Let F(N) denote the number of distinct entries in the N x N MDT. Equivalently,
F(N) is the number of lowestterms quotients of the natural numbers 1,...,N,
with
F(N)  F(N1) = 2φ(N),since each lowestterms fraction appears in the MDT along with its reciprocal. The solution to this difference equation is
As before, the fraction of distinct table entries is
(1)
H(N) = F(N)/N^{2}The first few values of F(N) and H(N) are:
From [6], we have φ(1) = 1 and
F(1) = 1 H(1) = 1 F(2) = 3 H(2) = 3/4 F(3) = 7 H(3) = 7/9 F(4) = 11 H(4) = 11/16
so from (1) and (2),
(2)
The convergence of H(N) to its limit is considerably faster for the MDT than in the MMT. Due to relatively larger values of φ(N) for prime N, H(N) has a locally nonmonotonic behavior:
Numerical values of H(N) may be computed for small N using an application of a gcd algorithm for φ(i) [7]:
If storage is available for all primes p ≤ N, computation of φ for larger N is much faster using Euler's product formula:
where the product is taken over all primes p dividing N. This formula can be implemented iteratively with the following steps:
(3)
input: N
φ ← N
for all primes p ≤ N do
if p  N, then φ ← (φ/p)(p  1)
output: φ
A modified subtraction table where the row is subtracted from the column has distinct entries in the first row and first column only:
In both cases, the modified N x N table has F(N) = 2N  1 entries, and the fraction of distinct entries converges to zero:
Since the modified addition and subtraction tables are not affected by primes, the H(N) function is smooth:
These shadow lines occur because in (3), the relative value φ(N)/N is frequently dominated by the largest factors in the product, which are associated with powers of the smallest primes 2 or 3 in the prime factorization of N. For example, if N is even but not a multiple of 3, then φ(N)/N is less than or equal to (and often near) the value
These proportions remain consistent for larger values of N.
Near N/3 line: 102 11% Near N/2 line: 188 21% Near 2N/3 line: 96 11% Near N1 line: 182 20% Remainder: 332 37%
{2,p} are central divisors for all primes p, 2 ≤ p ≤ N, by Lemma 3Therefore,
{2,4} are central divisors by inspection
{2,c} are not central divisors for all composite c, 6 ≤ c ≤ N by Lemma 14 with n = 2
f_{N}(1) = f_{N}(2) = π(N) + 1,where π is the prime counting function. In general, the central divisors counted in f_{N}(a) are {a,n}, where
The left inequality ensures that a is the lesser of the central divisors {a,n}, and the right inequality that both divisors are within the range found in the MMT. A histogram of f_{500}(a) is shown below, along with upper and lower bounds defined in the following sections:
a ≤ n ≤ N (4)
This frequency distribution has the same general shape for all values of N.
Tail Values
When
the exact value of f_{N}(a) is
f_{N}(a) = N  a + 1This corresponds to the solid band of entries in the MMT adjacent to the main diagonal.
Proof. We have
so all values of n satisfying (4) are within the range (17) of Lemma 15, and thus correspond to central divisors, QED.
Now assume
so that the range of n covers two intervals:
The first interval can be written
and contains values of n, all of which are central divisors by Lemma 15.
The second interval can be written
We consider only prime values of n in this interval to establish a lower bound for f_{N}(a). Additional central divisors may exist for composite n. Since
Including both intervals, a lower bound for f_{N}(a) thus is
A list of lower bound values for N = 500 is tabulated here.
Upper Bounds
Tight upper bounds for f_{N}(a) can be piecewise defined based on known characteristics of sequences of central divisors having the same LCD. Not surprisingly, these upper bounds are established by local maxima occurring at prime LCD values. In fact, most of the upper bounds described here are exact values of f_{N}(p) for prime p. The values of f_{N}(1) and f_{N}(2) were determined above, so we henceforth assume p ≥ 3.
If a is a prime and n complies with the limits in
Lemma 7, then {a,n} are central divisors. However, if a
is composite and n is subject to the same limits, there often can exist rational
numbers r such that
Consider the factor pair {p,n} for a prime p ≥ 3. Since n cannot exceed N in
the MMT, then by Lemma 7, {p,n} are central divisors for
all primes
The value n = 2p + 1 is excluded so that the interval (5) will juxtapose subsequent intervals described below. Applying Lemma 16 with
p ≤ n ≤ min{2p,N}, p ≤ N (5)
For p < N/2, we have 2p + 1 ≤ N and by Lemma 19, {n,p} are central divisors for odd values of n in the range
Applying Lemma 16 with i = 2p + 1, j = min{3p,N}, k = 2,
2p + 1 ≤ odd n ≤ min{3p,N}, p < N/2 (6)
For p < N/3, we have 3p + 1 ≤ N and by Lemma 20, {n,p} are central divisors for values of n such that
3p + 1 ≤ n ≤ min{5p,N} and n mod 6 = ±1If p ≥ N/5, then min{5p,N} = N. But if p < N/5 and we continue to use N as the maximum value of n (rather than the smaller 5p), we are overcounting the values of n to provide an upper bound for f_{N}(p). This approach is used for simplicity since the exact range for n when
3p + 1 ≤ n ≤ N when n mod 6 = 1, p < N/3
and  (7) 
3p + 1 ≤ n ≤ N when n mod 6 = 5, p < N/3Applying Lemma 16 twice with i = 3p + 1, j = N, k = 6,
⌊ (N  1)/6 ⌋  ⌈ p/2 ⌉ + ⌊ (N  5)/6 ⌋  ⌈ (3p  4)/6 ⌉ + 2The results (5), (6) and (7) cover adjacent intervals for n over its full range of possible values, and can be summarized as follows:= 2⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋  p
Summing the number of values in each range, we have the following piecewise definition for an upper bound Uf_{N}(a) of f_{N}(a) for all a:
Range of p Range(s) of n Quantity of n values p ≥ N/2 p ≤ n ≤ N (5) N  p + 1 N/3 ≤ p < N/2 p ≤ n ≤ 2p (5) p + 1 2p + 1 ≤ odd n ≤ N (6) ⌊ (N + 1)/2 ⌋  p p < N/3 p ≤ n ≤ 2p (5) p + 1 2p + 1 ≤ odd n ≤ 3p (6) (p + 1)/2 3p + 1 ≤ n ≤ N & n mod 6 = ±1 (7) 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋  p
Since {N,N} is the only factor pair when a = N, we have f_{N}(N) = 1. From right to left, the consecutive points of the polygonal upper bound are:
Range of a Uf_{N}(a) Description a ≥ N/2 N  a + 1 Line of slope 1 N/3 ≤ a < N/2 ⌊ (N + 3)/2 ⌋ Horizontal line a < N/3 ⌊ (a + 3)/2 ⌋ + 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋ Line of slope 1/2
Uf_{N}(N) = 1For example, at N = 500 the points are:Uf_{N}(⌈ (N  1)/2 ⌉) = ⌊ (N + 3)/2 ⌋
Uf_{N}(2 ⌊ (N + 3)/2 ⌋  4 ⌊ N/6 ⌋  2 ⌊ [(N mod 6) + 3]/4 ⌋  3) = ⌊ (N + 3)/2 ⌋
Uf_{N}(1) = 2 + 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋
Uf_{500}(500) = 1Uf_{500}(250) = 251
Uf_{500}(165) = 251
Uf_{500}(1) = 169
so that the product an is within range. For example, the central divisors comprising g_{N}(1) are {1,1} and {1,p} for all primes p in the range 2,...,N^{2}, by Lemma 2. It follows that
a ≤ n ≤ N^{2}/a, (8)
g_{N}(1) = π(N^{2}) + 1A histogram of g_{500}(a) is shown below, along with upper and lower bounds defined in the following sections:
Tail Values
When
the exact value of g_{N}(a) is
(9)
g_{N}(a) = 2(N  a) + 1Proof. We have
Rewriting (9),
(10)
so all values of n satisfying (8) are within the range (17) of Lemma 15, and thus correspond to central divisors. The number of values of n in (8) is
From (9),
⌊ N^{2}/a ⌋  a + 1 (11)
Adding both sides of the previous two inequalities, we have
We can write
(12)
By (12), the fractional portion is between 0 and 1, so
⌊ N^{2}/a ⌋ = 2N  aFrom (11), we have
Working downwards from a = N, g_{N} takes on increasing odd values until the limit (9) is reached.
Lower Bound
Now assume
so that the range of n covers two intervals as in the preceding section. The results in that section apply with N replaced by
Upper Bounds
Substituting ⌊ N^{2}/a ⌋ for N in the table above, we have
A list of values of g_{500}(a), Lg_{500}(a) and Ug_{500}(a) is tabulated here.
Range of a Ug_{N}(a) ⌊ N^{2}/a ⌋  a + 1 ⌊ (N^{2}/a + 3)/2 ⌋ ⌊ (a + 3)/2 ⌋ + 2 ⌊ N^{2}/(6a) ⌋ + ⌊ [(⌊ N^{2}/a ⌋ mod 6) + 3]/4 ⌋
Although the GCD frequency distribution has a general appearance similar to the totient function, and a difference of just 1 at prime values of b, nearly all of the other values of the functions differ significantly.
Lower Bound
As can be seen in a previous diagram, central
divisors occur for composite column indices C at primenumbered rows beginning
at
(C  1)/2 ≤ prime R ≤ Cor
R > ⌈ (C  3)/2 ⌉This result is established in Lemma 7 with C ≤ 2R + 1. By Lemma 15, central divisors occur at every row above the parabola
or for every R satisfying
Additional central divisors can occur elsewhere in column C, so the preceding ranges form a lower bound for h_{N}(C) that also applies to prime columns. The number of primes up to the parabola is:
and the total number of values above the parabola is
so the lower bound is the sum
It is conjectured that a tighter lower bound for h_{N}(C) is simply π(C).
Upper Bound
Since a primenumbered column of the MMT is completely filled with central divisors down to the main diagonal, an upper bound for h_{N}(b) is
Uh_{N}(b) = b
and
ab = cd (13)
then
 a  b  =  c  d  (14)
a = c and b = d.It follows that a pair of central divisors are uniquely defined by their product and their unsiqned (or squared) difference. Equivalently, if there are two divisor pairs of a natural number with the same unsigned difference, then they are the same pair.
Proof. Without loss of generality, we can take a ≤ b and c ≤ d. From (13), we have
d = ab/cSubstituting in (14) and squaring,
(a  b)^{2} = (c  ab/c)^{2}If c = b, then ab = bd by (13), so d = a. But then the assumption c ≤ d is equivalent to(c^{2}  a^{2})(c^{2}  b^{2}) = 0
c = a and/or c = b
Proof. If p = 1, {1,1} are trivially central divisors. If p is a prime, then
{1,p} is the only divisor pair of p and therefore its central divisors.
Conversely, if
2 ≤ k ≤ p/2Combining these two inequalities, we have2 ≤ p/k ≤ p/2
k  p/k ≤ p/2  2 < p  1Therefore, {1,p} cannot be central divisors since they are farther apart than {k,p/k}, QED.
Proof. The divisor pairs of pq are {1,pq} and {p,q}. The first pair cannot be central divisors by Lemma 2 since pq is composite, so {p,q} are central divisors.
(a  1)(b  1) < m < (a + 1)(b + 1)These limits are closer together for central divisors {a,b} than for any other factor pair of the product ab.
Proof. Under construction.
c > a and c > bor
d > a and d > bProof. Let N = ab, so that b = N/a. The first condition above is equivalent to
Proof. Without loss of generality, assume p ≥ q so that
p^{2} > p and p^{2} > pq,p^{2} is greater than both reference factors, and therefore {q,p^{2}} are not central divisors by Lemma 5. The remaining factor pair
n ≤ 2p + 1,then {n,p} are central divisors.
Proof. {1,p} are central divisors by Lemma 2. The
result follows from Lemma 4 with
For a proof independent of Lemma 4, note that when
Otherwise, let k be any proper divisor of n. The divisor pairs of np are {1,np}, {k,pn/k}, {pk,n/k} and the reference pair {n,p}. The first pair cannot be central divisors by Lemma 2 since np is composite.
Next, we have
k ≤ n/2 ≤ p + 1/2If k = p, then {k,pn/k} is the same as the reference pair, so we can assume
pn/k > n and pn/k > p,so pn/k is greater than both reference factors, and therefore {k,pn/k} cannot be central divisors by Lemma 5.
Now assume that n = 2p + 1. Since n is odd, k ≥ 3 and
n/p = 2 + 1/p < 3 ≤ k,or pk > n. If n = 2p, then {n,p} = {p,2p} are central divisors by Lemma 6. Otherwise, we have
n/p ≤ 2  1/p < 2 ≤ k,so again pk > n. Since
pk ≥ 2p > p,pk is greater than both reference factors, and so {pk,n/k} cannot be central divisors by Lemma 5, QED.
(p  1)(q  1) < n < (p + 1)(q + 1)then {n,pq} are central divisors.
Proof. {p,q} are central divisors by Lemma 3. The
result follows by Lemma 4 with
Proof. Clearly,
We have
From (15), we also have
(15)
If a < b/k, then {a,b} are not central divisors.Proof. Since k ≥ 2, we have
If a > b/k, then {ka,b/k} are not central divisors.
so the factor pair {a,b} is farther apart than {ka,b/k}, or conversely.
Proof. The divisor pairs of pqr are {1,pqr}, {q,pr}, {r,pq} and the reference
pair {p,qr}. The first cannot be central divisors by
Lemma 2 since pqr is composite. We have
then {n,3p} are central divisors if and only if n is odd.
p ≤ n ≤ 2(p  1), (16)
Proof. Let n be even. Then n/2 < p from (16), so
5n^{2}/4 < 5p^{2}Since {3n/2,2p} are closer together than {n,3p}, the latter cannot be central divisors.(3n/2  2p)^{2} < (n  3p)^{2}
Next, let p = 2. Then n = 2 and {n,3p} = {2,6} are not central divisors.
Now let n = p ≥ 3, so that n is odd. Then {n,3p} = {max{p,3},3p} are central divisors by Lemma 6.
Therefore, we can henceforth assume that
3 ≤ p < n ≤ 2(p  1)Next, let n ≥ 5 be prime and thus odd. Since n > 3 and n > p, {n,3p} are central divisors by Lemma 11.
Finally, let n be an odd composite. From (16), we have n < 3p and every proper divisor k of n is subject to the constraint
3 ≤ k ≤ n/3 < p,whence n/k ≥ 3. The divisor pairs of 3np are:
Case 1: {1,3np}and the reference pair {n,3p}.
Case 2: {k,3pn/k}
Case 3: {3k,pn/k}
Case 4: {3,np}
Case 5: {p,3n}
Case 6: {kp,3n/k}
Case 7: {3kp,n/k}
Case 1: {1,3np} cannot be central divisors by Lemma 2 since 3np is composite.
Case 2: Since 3p/k > n/k > 1, we have 3pn/k > n and 3pn/k > 3p, so 3pn/k is greater than both reference factors. Therefore, {k,3pn/k} cannot be central divisors by Lemma 5.
Case 3: Since k ≤ n/3 < p, we have p/k > 1 and so pn/k > n. If n/k = 3, then
{3k,pn/k} is the same as the reference pair. Otherwise,
Case 4: Since n/k ≥ 3 > 3/p, we have 3 < pn/k, and so {3,np} are not central
divisors by Lemma 10 with
Case 5: We have n > p and 3n > n, so 3n > 3p and 3n is therefore bigger than both reference factors. As a result, {p,3n} cannot be closer together than the reference pair by Lemma 5.
Case 6: If k = 3, {kp,3n/k} is the same as the reference pair. Otherwise,
Case 7: Since n < 3p < 3kp, we have 3p > n/k, and so {3kp,n/k} are not central
divisors by Lemma 10 with
Proof. Since p is prime and n < p, n and p cannot have any common factors other
than 1, so
Proof. Since c is composite, it has a factor k between 2 and inclusive. We have so
k < c/nand therefore {nk,c/k} are closer together than {n,c}, QED.(n^{2}k^{2}  c^{2})(k^{2}  1) < 0
(nk  c/k)^{2} < (n  c)^{2}
then {a,b} are central divisors. The condition is symmetric in a and b; (17) is equivalent to
(17)
Proof. Assume {a,b} are not the central divisors of ab. Then there exist other natural numbers c and d such that
(18)
b  a > d  c ≥ 0Now 4ab = 4cd, so
(b  a)^{2} > (d  c)^{2} (19)
Combining (20) and (19), we have
(b + a)^{2}  (b  a)^{2} = (d + c)^{2}  (d  c)^{2} (20)
(b + a)^{2}  (b  a)^{2} + (b  a)^{2} > (d + c)^{2}  (d  c)^{2} + (d  c)^{2}Using (18),(b + a)^{2} > (d + c)^{2}
b + a > d + c (21) d + c ≤ b + a  1 (22)
By (22),
a contradiction. Therefore, {a,b} are Central Divisors when inequality (17) holds, QED.
Cf. my StackExchange posting.
⌊ (j  m)/k ⌋  ⌈ (i  m)/k ⌉ + 1Proof. Due to the requirement that n mod k = m, the values to be counted are at intervals of k. Since
i  m ≤ k ⌊ n/k ⌋ ≤ j  mand consider only multiples of k in the interval. The smallest multiple of k that is at least as large as the lower bound is
k⌈ (i  m)/k ⌉ ≤ k ⌊ n/k ⌋ ≤ k ⌊ (j  m)/k ⌋Dividing by k,
⌈ (i  m)/k ⌉ ≤ ⌊ n/k ⌋ ≤ ⌊ (j  m)/k ⌋and the result follows.
Proof. By Lemma 2, {1,p^{2n+1}} cannot be
central divisors since the latter factor is composite. The remaining factor
pairs of p^{2n+1} are {p^{k},p^{2n+1k}} for
2n + 1  k > n + 1so p^{2n+1k} is greater than both reference factors for all given values of k, and therefore {p^{k},p} are not central divisors by Lemma 5, QED.p^{2n+1k} > p^{n+1} > p^{n},
Proof. Since m is the smallest proper divisor of n, n/m is its largest, so for all proper divisors k of n, we have
m ≤ k ≤ n/m ≤ pThe divisor pairs of np are {1,np}, {kp,n/k}, {k,pn/k} and the reference pair {n,p}. {1,np} cannot be central divisors by Lemma 2 since np is composite.
If p  n, then n/p ≤ m; otherwise, n/p < m ≤ k. In the former case, we
can exclude
Finally, since k < kp and pn/k > n/k, {k,pn/k} are farther apart than {kp,n/k} and also cannot be central divisors, QED.
Proof. If n is prime, then {n,p} are central divisors by
Lemma 3. Otherwise, n is composite and its smallest
proper divisor is at least 3 since it is odd. The result follows from
Lemma 18 with
Proof. If n is prime, then {n,p} are central divisors by
Lemma 3. Otherwise, n is composite and of the form
Proof. Let N = ab. Since {a,b} are the central divisors of N, then a minimizes
(a  N/a)^{2}/d^{2} = (a/d  (N/a)/d)^{2}is also minimized for all such d. Therefore, {a/d,b/d} are central divisors of N/d^{2}.
Proof. Let {a,N/a} be the central divisors of N, and {b,N/b} a different factor pair of the same product, . Then the geometric mean of both factor pairs is and
b < a ≤ N/a < N/bBy (21) of Lemma 15,
Proof. Let m ∈ {1,0,1,2,3}. Then
so the inequality in Lemma 15 is satisfied for a = n and
RC = constantproduce a rainbow effect:
This image is included simply for its visual impact.
p(q  2) ≤ n ≤ (p  1)(q  1),then {n,pq} are central divisors if and only if n is not divisible by q  1.
Proof under construction. A valid range for n exists only when q ≤ p + 1.
For a proof of the converse, assume q  1  n. Then
n ≤ (p  1)(q  1)so {p(q  1),qn/(q  1)} are closer together than {n,pq}, and therefore {n,pq} are not central divisors.n/(q  1) ≤ p  1 < p
[p(q  1)  nq/(q  1)]^{2} < (pq  n)^{2},
It remains to prove that if {n,pq} are not central divisors, then n is divisible
by
These limits are closer together for central divisors {a,b} than for any other factor pair of the product ab.
(a  1)(b  1) < m < (a + 1)(b + 1) (23)
Proof under construction. Cf. my StackExchange posting.
Proof of the second part: Let {a,b} be central divisors and {c,d} another
factor pair of
d  c > b  aand similarly,d + c > b + a
(c + 1)(d + 1) > (a + 1)(b + 1)
(d + c) < (b + a)Therefore, the limits in (23) for {c,d} are farther apart than for {a,b}, QED.(c  1)(d  1) < (a  1)(b  1)
Proof when a = b. {a,a} are trivially central divisors, and (23) becomes
(a  1)^{2} < m < (a + 1)^{2}Then {m,a^{2}} are central divisors by Lemma 15 with
Proof when a = 1. When b is also 1, then ab = 1 and (23) becomes
0 = (1  1)(p  1) < m < (1 + 1)(p + 1) = 2(p + 1),or
1 ≤ m ≤ 2p + 1This is established in the alternate proof of Lemma 7, QED.
Proof when a = 2. By Lemma 3, {2,b} are central divisors
when b is prime. When
The results for the first few values of b can be confirmed by inspection:
Henceforth, we can assume b is a prime p ≥ 5, and (23) becomes
b Range of m in (23) ab {m,ab} are central divisors 2 2 ≤ m ≤ 8 4 for all 7 values of m 3 3 ≤ m ≤ 11 6 for all 9 values of m 4 4 ≤ m ≤ 14 8 for all 11 values of m
p ≤ m ≤ 3p + 2If m = p, then {m,ab} = {p,2p} are central divisors by Lemma 6. Therefore,
If m is prime, then m > p ≥ 5 > 2 by (24), so {m,ab} = {m,2p} are central divisors by Lemma 11. We can henceforth assume m is composite.
p + 1 ≤ m ≤ 3p + 2 (24)
Let k be a proper divisor of m, so that 2 ≤ k ≤ m/2 and
Case 1: {k,2pm/k}and the reference pair {m,2p}.
Case 2: {2,mp}
Case 3: {2k,pm/k}
Case 4: {p,2m}
Case 5: {pk,2m/k}
Case 6: {2pk,m/k}
Case 1: Since p ≥ 5, we have from (24):
m ≤ 3p + 2 < 3p + p = 4pandk ≤ m/2 < 2p
2pm/k > m
k ≤ m/2 < mso 2pm/k is greater than both reference factors, and therefore {k,2pm/k} are not central divisors by Lemma 5.2pm/k > 2p,
Case 2: We have
mp ≥ 5m > mand
mp ≥ (p + 1)p ≥ 6p > 2p,so mp is greater than both reference factors, and therefore {2,mp} are not central divisors by Lemma 5.
Case 3: If k = m/2, then {2k,pm/k} is the same as the reference pair.
We can therefore exclude
Assume for the moment that k ≥ p. Then
3 ≤ m/k ≤ m/p ≤ 3 + 2/p < 4by (24), so m/k must be 3. It follows that
m = 3k ≤ 3p + 2so k = p, and {2k,pm/k} is again the same as the reference pair.p ≤ k ≤ p + 2/3,
Thus, we have k < p. Then
pm/k > mand
m/k > 2so pm/k is greater than both reference factors, and therefore {2k,pm/k} are not central divisors by Lemma 5.pm/k > 2p,
Case 4: We have
2m > mand
2m ≥ 2(p + 1) > 2p,so 2m is greater than both reference factors, and therefore {p,2m} are not central divisors by Lemma 5.
Case 5: If k = 2, then {pk,2m/k} is the same as the reference pair, so
we have
m/p ≤ 3 + 2/p < 4 ≤ k, or pk > mIf m ≤ 3p  1, then
m/p ≤ 3  1/p < 3 ≤ k, or pk > mSince pk ≥ 3p > 2p, we have shown that if m ≠ 3p, then pk exceeds both reference factors, and therefore {pk,2m/k} are not central divisors by Lemma 5.
When m = 3p, k is 3 or p. In the former case, {pk,2m/k} is the same as the
reference pair {3p,2p}, so we must have
(p  3)(p + 2) > 0so {pk,2m/k} = {p^{2},6} are farther apart than the reference pairp^{2}  6 > p,
Case 6: Since p > 2, we have
m ≤ 3p + 2 < 3p + p = 4p = 2p(2) ≤ 2pkand
2pk ≥ 2p(2) > 2p,so 2pk is greater than both reference factors, and therefore {2pk,m/k} are not central divisors by Lemma 5, QED.
It remains to prove Lemma 4 for 3 ≤ a ≤ b  1.
[2] P. Erdős, An asymptotic inequality in the theory of numbers (in Russian), Vestnik Leningrad. Univ., v. 15 (1960) p. 13, 4149; MR0126424 (23 #A3720), cited in Finch, S. (2018), Mathematical Constants II (Encyclopedia of Mathematics and Its Applications), p. 33. Cambridge: Cambridge University Press. doi:10.1017/9781316997741, available from OEIS
[3] K. Ford, The distribution of integers with a divisor in a given interval, Ann. of Math. 168 no. 2 (2008) pp. 367433, cited in Koukoulopoulos and Thiel, op. cit., p. 448.
[4] Weisstein, Eric W. "Relatively Prime." From MathWorldA Wolfram Web Resource. https://mathworld.wolfram.com/RelativelyPrime.html
[5] Wikipedia Coprime integers
[6] M. Abramowitz & I. A. Stegun (eds.), Handbook of Mathematical Functions, National Bureau of Standards, 1964, p. 826.
[7] R. Sedgewick, Algorithms, second ed., AddisonWesley, 1988, p. 12.
[8] Wikipedia Greatest common divisor
Thanks to Nigel Boston, Harold Diamond, Martin Huxley and Daniel Fischer for constructive feedback.
This paper is a revision and expansion of a paper first posted on this site in 1993.
Copyright © 19931998, 2020 by Balmoral Software. All rights reserved.