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 upper-left corner to the lower-right one. By convention, entries in the lower-triangular portion of arithmetic tables for commutative operators are excluded from consideration as distinct entries since they already appear in the upper region. Excluding the upper-triangular 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 lowest-terms 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 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 follow 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 9, 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 prime-numbered 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 9 and Lemma 11, this minimum value of R is greater than or equal to the lower limit for R for non-square 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 - a2/(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 12 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 9 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 16, {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)/N2is 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 non-monotonic 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 relatively-prime 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.
In the remainder of this paper, we define a proper divisor k of a
composite natural number n as one that is neither 1 nor n:
Entries described in the preceding two sections are shown below for the
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 prime-numbered 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 lowest-terms quotients of the natural numbers 1,...,N,
with
F(N) - F(N-1) = 2φ(N),since each lowest-terms 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)/N2The 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 non-monotonic 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 N-1 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 18 with n = 2
fN(1) = fN(2) = π(N) + 1,where π is the prime counting function. In general, the central divisors counted in fN(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 f500(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 fN(a) is
fN(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 (20) of Lemma 14, 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 14.
The second interval can be written
We consider only prime values of n in this interval to establish a lower bound for fN(a). Additional central divisors may exist for composite n. Since
Including both intervals, a lower bound for fN(a) thus is
A list of lower bound values for N = 500 is tabulated here.
Upper Bounds
Tight upper bounds for fN(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 fN(p) for prime p. The values of fN(1) and fN(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 19 with
p ≤ n ≤ min{2p,N}, p ≤ N (5)
For p < N/2, we have 2p + 1 ≤ N and by Lemma 21, {n,p} are central divisors for odd values of n in the range
Applying Lemma 19 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 22, {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 fN(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 19 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 UfN(a) of fN(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 fN(N) = 1. From right to left, the consecutive points of the polygonal upper bound are:
Range of a UfN(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
UfN(N) = 1For example, at N = 500 the points are:UfN(⌈ (N - 1)/2 ⌉) = ⌊ (N + 3)/2 ⌋
UfN(2 ⌊ (N + 3)/2 ⌋ - 4 ⌊ N/6 ⌋ - 2 ⌊ [(N mod 6) + 3]/4 ⌋ - 3) = ⌊ (N + 3)/2 ⌋
UfN(1) = 2 + 2 ⌊ N/6 ⌋ + ⌊ [(N mod 6) + 3]/4 ⌋
Uf500(500) = 1Uf500(250) = 251
Uf500(165) = 251
Uf500(1) = 169
so that the product an is within range. For example, the central divisors comprising gN(1) are {1,1} and {1,p} for all primes p in the range 2,...,N2, by Lemma 2. It follows that
a ≤ n ≤ N2/a, (8)
gN(1) = π(N2) + 1A histogram of g500(a) is shown below, along with upper and lower bounds defined in the following sections:
Tail Values
When
the exact value of gN(a) is
(9)
gN(a) = 2(N - a) + 1Proof. We have
Rewriting (9),
(10)
so all values of n satisfying (8) are within the range (20) of Lemma 14, and thus correspond to central divisors. The number of values of n in (8) is
From (9),
⌊ N2/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
⌊ N2/a ⌋ = 2N - aFrom (11), we have
Working downwards from a = N, gN 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 ⌊ N2/a ⌋ for N in the table above, we have
A list of values of g500(a), Lg500(a) and Ug500(a) is tabulated here.
Range of a UgN(a) ⌊ N2/a ⌋ - a + 1 ⌊ (N2/a + 3)/2 ⌋ ⌊ (a + 3)/2 ⌋ + 2 ⌊ N2/(6a) ⌋ + ⌊ [(⌊ N2/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 prime-numbered 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 14, 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 hN(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 hN(C) is simply π(C).
Upper Bound
Since a prime-numbered column of the MMT is completely filled with central divisors down to the main diagonal, an upper bound for hN(b) is
UhN(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)2If c = b, then ab = bd by (13), so d = a. But then the assumption c ≤ d is equivalent to(c2 - a2)(c2 - b2) = 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.
max{c,d} > max{a,b}or
min{c,d} < min{a,b}Proof. Let N = ab, so that b = N/a and d = N/c. The first condition above is equivalent to
Conversely, the second condition above is equivalent to
Proof. Without loss of generality, assume p ≥ q so that
p2 > p and p2 > pq,p2 is greater than both reference factors, and therefore {q,p2} are not central divisors by Lemma 4. The remaining factor pair
Then
(w - 1)(x - 1) < yz < (w + 1)(x + 1) (15)
Proof by contradiction. Assume (16) does not hold:
(y - x)(z - w) ≤ 0 (16)
(y - x)(z - w) > 0Then
y > x and z > wor
y < x and z < wIn the first case, we have
y ≥ x + 1 and z ≥ w + 1contradicting (15). In the second case, we haveyz ≥ (x + 1)(w + 1),
y ≤ x - 1 and z ≤ w - 1again contradicting (15), QED.yz ≤ (x - 1)(w - 1)
n ≤ 2p + 1,then {n,p} are central divisors.
Proof. When n = 1, {n,p} are central divisors by
Lemma 2, so we can henceforth assume
Otherwise, let k be any proper divisor of composite 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 4.
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 5. 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 4, QED.
Proof. If a,b,c,d are natural numbers such that ab = cd, then by Euclid's Four Number Theorem [8], there are natural numbers r,s,t,u such that
a = rsLet n,a,b be natural numbers such that n | ab. Then we can write
b = tu
c = rt
d = su
ab = knfor some natural number k. Let c = k and d = n in the preceding result. Then there exists natural numbers r,s,t,u such that
If ab is composite, these limits are closer together than for any other factor pair of ab.
(a - 1)(b - 1) < m < (a + 1)(b + 1) (17)
Proof. If ab is a prime p, then its central divisors are {1,p} by
Lemma 2,
To prove the second part when ab is composite, let {c,d} be another factor pair
of
|d - c| > |b - a|and similarly,d + c > b + a
(c + 1)(d + 1) > (a + 1)(b + 1)
-(c + d) < -(a + b)Therefore, the limits in (17) are farther apart for {c,d} than for {a,b}.(c - 1)(d - 1) < (a - 1)(b - 1)
For {m,ab} to be central divisors, we must show that
for all divisors k of the product mab. By Lemma 8, each such divisor can be written as
(m - ab)2 ≤ (k - mab/k)2 (18)
(j - 1)(ab/j - 1) < m < (j + 1)(ab/j + 1)Applying Lemma 6 with(j - 1)(ab/j - 1) < i(m/i) < (j + 1)(ab/j + 1)
(i - ab/j)(m/i - j) ≤ 0,which reduces to (18), 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 9 with
Proof. Clearly,
We have
From (19), we also have
(19)
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 {a,b} are central divisors. The condition is symmetric in a and b; (20) is equivalent to
(20)
Proof. Assume {a,b} are not the central divisors of ab. Then there exist other natural numbers c and d such that
(21)
b - a > d - c ≥ 0Now 4ab = 4cd, so adding that quantity to both sides, we have(b - a)2 > (d - c)2
(b + a)2 > (d + c)2Using (21),
b + a > d + c (22) d + c ≤ b + a - 1 (23)
By (23),
a contradiction. Therefore, {a,b} are Central Divisors when inequality (20) holds, QED.
Note that the converse does not hold; for example, if a = 1 and b = 5, then {a,b} are Central Divisors but neither (20) nor (21) hold.
Proof. Let m ∈ {-1,0,1,2,3}. Then
so the inequality in Lemma 14 is satisfied for a = n and
then {n,pq} are central divisors if and only if n is not divisible by q - 1. In particular, when
p(q - 2) ≤ n ≤ (p - 1)(q - 1), (24)
p ≤ n ≤ 2(p - 1)and {n,3p} are central divisors if and only if n is odd.
Proof. A valid range for n exists only when q ≤ p + 1, and we also have
A: n is not divisible by q - 1so that Lemma 16 is simply A ⇔ B, subject to (24). We will first prove the converseB: {n,pq} are central divisors,
Assume q - 1 | n (A is false). Then by (24),
n/(q - 1) ≤ p - 1 < pso {p(q - 1),qn/(q - 1)} are closer together than {n,pq}, and therefore {n,pq} are not central divisors (B is false).[p(q - 1) - nq/(q - 1)]2 < (pq - n)2,
Next, we'll prove some special cases that serve to limit the range of the variables. Note that Lemma 16 is proven when either both A and B are true, or both A and B are false, subject to inequality (24).
{1,p3(p - 2)} are not central divisors by Lemma 2 since npq is composite.Therefore, B is also true.{p,p2(p - 2)} are not central divisors since they are farther apart than {n,pq} for
p > 3. Ifp = 3, these pairs are the same.{p - 2,p3} are not central divisors since they are farther apart than {n,pq}
In the latter case, p - 1 divides n so A is false. Then
n > p > q ≥ 3
p(q - 2) < n < (p - 1)(q - 1)It follows that n > q, so {n,pq} are central divisors by Lemma 13, and B is true.
{1,npq} are not central divisors by Lemma 2 since npq is composite.Therefore, {kp,qn/k} are the central divisors of npq and so must be closer together than {n,pq}. Then{p,nq} are not central divisors since they are farther apart than {n,pq}.
{q,np} are not central divisors since they are farther apart than {n,pq}.
{k,pqn/k} are not central divisors since they are farther apart than {n,pq}.
The remaining factor pairs of npq are of the form {kp,qn/k} or {kq,pn/k} for
k ≤ Grouping the smaller (or larger) factors together increases the distance between the corresponding products, so {kq,pn/k} are not central divisors since they are farther apart than {kp,qn/k}.
n/p < k < qBut by (24), n/p ≥ q - 2, so k > q - 2 and k ≤ q - 1. The only possibility is
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.(n2k2 - c2)(k2 - 1) < 0
(nk - c/k)2 < (n - c)2
⌊ (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. 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 20 with
Proof. If n is prime, then {n,p} are central divisors by
Lemma 3. Otherwise, n is composite and of the form
Proof. By Lemma 2, {1,p2n+1} cannot be
central divisors since the latter factor is composite. The remaining factor
pairs of p2n+1 are {pk,p2n+1-k} for
2n + 1 - k > n + 1so p2n+1-k is greater than both reference factors for all given values of k, and therefore {pk,p2n+1-k} are not central divisors by Lemma 4, QED.p2n+1-k > pn+1 > pn,
Proof. Let N = ab. Since {a,b} are the central divisors of N, then a minimizes
(a - N/a)2/d2 = (a/d - (N/a)/d)2is also minimized for all such d. Therefore, {a/d,b/d} are central divisors of N/d2.
Proof. In the first case, we have
(n - a)(n - b) < 0so {n2,ab} are closer together than {na,nb}. In the second case, we have(n2 - a2)(n2 - b2) < 0
(n2 - ab)2 < (na - nb)2,
na < bso {n2a,b} are closer together than {na,nb}. In the last case, we can exchange a and b in the preceding results to establish that {n2b,a} are closer together than {na,nb}, QED.(n4 - n2)a2 < (n2 - 1)b2
(n2a - b)2 < (na - nb)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 (22) of Lemma 14,
q - 1 ≤ n ≤ q + 1and
{qp,np + m} are central divisors for all primes p.
q - 2n ≤ m ≤ 3q - 2n + 2, (25)
For example, when q = 5,
{5p,4p - 3}, {5p,4p - 2}, ..., {5p,4p + 9},are each central divisors for all primes p.
{5p,5p - 5}, {5p,5p - 4}, ..., {5p,5p + 7},
{5p,6p - 7}, {5p,6p - 6}, ..., {5p,6p + 5}
The ranges for np + m are disjoint when p > 2q + 4, in which case there are
Proof. Multiplying the first inequality by p - 2 and adding the second inequality plus 2n, we have for all primes p:
(p - 2)(q - 1) + (q - 2n) + 2n ≤ (p - 2)n + m + 2n ≤ (p - 2)(q + 1) + (3q - 2n + 2) + 2nSince {q,p} are central divisors by Lemma 3, the conditions of Lemma 9 are satisifed and(p - 1)(q - 1) < np + m < (p + 1)(q + 1)
To find the condition for which the ranges of central divisors are disjoint, we substitute each value of n in (25):
If n = q - 1:The first two ranges are disjoint whenq - 2(q - 1) ≤ m ≤ 3q - 2(q - 1) + 2If n = q:(q - 1)p - q + 2 ≤ np + m ≤ (q - 1)p + q + 4
q - 2q ≤ m ≤ 3q - 2q + 2If n = q + 1:qp - q ≤ np + m ≤ qp + q + 2
q - 2(q + 1) ≤ m ≤ 3q - 2(q + 1) + 2(q + 1)p - q - 2 ≤ np + m ≤ (q + 1)p + q
(q - 1)p + q + 4 < qp - qSimilarly, the last two ranges are disjoint whenp > 2q + 4
qp + q + 2 < (q + 1)p - q - 2p > 2q + 4
p > (a - 1)(b - 1),then {p,ab} are central divisors.
Proof. We have
(a - 2)(b - 2) ≥ 0so {ab,p} are central divisors by Lemma 7, QED.2p > 2(a - 1)(b - 1) ≥ ab - 2
ab ≤ 2p + 1,
RC = constantproduce a rainbow effect:
This image is included simply for its visual impact.
[2] P. Erdős, An asymptotic inequality in the theory of numbers (in Russian), Vestnik Leningrad. Univ., v. 15 (1960) p. 13, 41-49; 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. 367-433, cited in Koukoulopoulos and Thiel, op. cit., p. 448.
[4] Weisstein, Eric W. "Relatively Prime." From MathWorld--A 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., Addison-Wesley, 1988, p. 12.
[8] Erdos & Suranyi, Topics in the Theory of Numbers, Springer, 2003, p. 5.
[9] 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 © 1993-1998, 2020, 2023 by Balmoral Software. All rights
reserved.
