by Michael Thomas De Vlieger, 12 August 2014, St. Louis, Missouri, revised 9 January 2015 to add contact info (see bottom of page). Click here for the main menu.
The antidivisor k < n has three possible arithmetic relationships to n. From OEIS A066272 it is clear that an antidivisor k cannot divide n; an antidivisor k cannot be a divisor of n by definition. This page aims to prove the following:
1. Antidivisors k must be coprime to prime n. (link)
2. Odd antidivisors k must be coprime to n. (link)
2.1 All antidivisors k that are not coprime to n must be neutral to n. (link)
3. Even antidivisors k > 2 must be neutral to composite n, meaning k neither divides n nor is coprime to n. Alternatively, 1 < gcd(k, n) < k. (link)
3.1 Odd n > 1 have the antidivisor 2, which is the only prime even antidivisor, by definition coprime to odd n. (link)
3.2 All even antidivisors k are composite, except k = 2. (link)
3.3 If n has no coprime k then all the k of n and n itself must be composite and even. (link)
3.4 Numbers n > 1 that do not have prime antidivisors must be even. (link)
4. The even antidivisors k of even composite n must be semidivisors of n, meaning the antidivisor k is the product of at least two primes p that also divide n; one of these primes p = 2. (link)
4.1 Integer powers of 2, i.e., n = 2^e cannot have even antidivisors k. (link)
4.2 Even k of an even n that is not a power e > 1 of 2 must be in the form f(2^(e + 1)), with f a factor of the odd result d of dividing n by the largest prime power 2^e that divides n. (link)
4.3 If n is even and has no prime antidivisors k, then n must also have no coprime antidivisors. (link)
5. The even antidivisors k > 3 of odd composite n must be semitotatives of n, meaning k is the product of at least one prime p that divides n, and one prime q that is coprime to n. The prime q = 2. (link)
5.1 Integer prime powers, i.e.,
n = p^e must have (e – 1) even antidivisors k, all of which are semitotatives of n. (link)
6. If n has no prime antidivisors k, then n has no coprime antidivisors k, and vice versa. (link)
Let d, e, f, i, k, m, n, p, q be positive integers. Let the prime p divide n, and the prime q be coprime to n.
Definitions. (Please refer to OEIS A066272 for the definition and background regarding the antidivisor.)
Arithmetic relationship: a comparison of the prime divisors of m and n. There are three principal arithmetic relationships: m coprime to n (i.e., gcd(m, n) = 1), m is neutral to n (1 < gcd(m, n) < m), and m divides n (gcd(m, n) = m). Looking at prime divisors common to m and n sets up three different arithmetic relationships: m coprime to n, m is semicoprime to n, and m is regular to n, with the divisor m of n being a special case of regular. The neutral relationships include semicoprime and nondivisor regular (See below, or proofs regarding neutral numbers).
Neutral: a number m is said to be "neutral" to n if it neither divides n nor is coprime to n. There are two kinds of neutral number: nondivisor regular m and semicoprime m.
Regular: a number m is said to be "regular" to n if all the prime factors p of m also divide n. The divisor is a special case of a regular m such that m also divides n in addition to all of its prime factors p.
Semicoprime: a number m is said to be "semicoprime" to n if m is the product of at least one prime divisor p of n and one prime q that is coprime to n.
Semidivisor: a nondivisor regular number m < n; m is composite and neutral to composite n, and n must not be a perfect prime power p^e.
Semitotative: a semicoprime m < n; m is composite and neutral to composite n ≥ 8.
Theorem 1: Antidivisors k must be coprime to prime n, since all k < n are coprime to n [1].
Theorem 2: Odd antidivisors k must be coprime to n. This is because:
Equation 1: Odd antidivisors k:
k (x + ½) ± ½ = n
k (ODD/2) = n ± ½
k (ODD) = (2 n + 1)/2 and (2 n − 1)/2
k = (2 n + 1)/ ODD and (2 n − 1)/ ODD
Each of (2 n + 1), (2 n − 1), and the ODD rhs denominator lack the factor 2, and because the ODD rhs denominator must divide the rhs numerator in order to obtain an integer, odd k must be coprime to n. Also observe that 2 n ± 1 = ±1 (mod n) and is thus coprime to n. A divisor d > 1 of a number coprime to n must also be coprime to n and cannot divide n. Thus any odd antidivisor k must be coprime to n.
Examples: For n = 12, set of antidivisors is {5, 8}: k = 5 is odd and coprime to n = 12. For n = 9455, the set of odd antidivisors is {3, 9, 11, 33, 99, 191, 573, 1719, 2101, 6303} and the set of coprime antidivisors is {2, 3, 9, 11, 33, 99, 191, 573, 1719, 2101, 6303}.
Corollary 2.1: All antidivisors k that are not coprime to n must be neutral to n.
By definition, an antidivisor k cannot divide n. If k is not coprime to n, then k must be neutral to n, i.e., 1 < gcd(k, n) < k. Neutral k implies that we have a composite n > 4.
Theorem 3: Even antidivisors k > 2 must be neutral to composite n, meaning k neither divides n nor is coprime to n. Alternatively, 1 < gcd(k, n) < k. This is because:
Equation 2: Even antidivisors k:
k (x + ½) = n
k (ODD/2) = n
k = 2 n / ODD
The ODD rhs denominator must divide n in order to obtain an integer result. The factor 2 will divide k, making an even antidivisor k. This implies gcd(k, n) = ODD. The ODD number cannot be less than 3, since ODD = 1 would make k = 2n, and not a qualifying antidivisor k < n. Since 1 < gcd(k, n) < ODD with ODD ≥ 3, k must be neutral to n, meaning k neither divides n, nor is coprime to n and is an element counted in OEIS A045763(n).
Examples: For n = 60, the set of antidivisors is {7, 8, 11, 17, 24, 40}: the even antidivisors are {8, 24, 40} and the antidivisors that are neutral to 60 are {8, 24, 40}.
For n = 3969, the set of even antidivisors is {2, 6, 14, 18, 42, 54, 98, 126, 162, 294, 378, 882, 1134, 2646}, the antidivisors that are neutral to 3969 are {6, 14, 18, 42, 54, 98, 126, 162, 294, 378, 882, 1134, 2646}.
Corollary 3.1: All odd n > 1 have the antidivisor k = 2.
See the definition of antidivisor at OEIS A066272. Additionally, we can find a solution to the ODD rhs denominator in Equation 2 that generates k = 2. If n = ODD, then k = 2.
Equation 3: Antidivisor k = 2 for all odd n > 1:
k = 2 n / n, with n ≡ 1 (mod 2)
k = 2
Note that for n = 1, k = 2 exceeds n and is not an antidivisor k < n by definition.
Examples: See chart “Spiel” at OEIS A066272a.
Corollary 3.2: All even antidivisors k are composite, except k = 2. All neutral antidivisors are composite, since prime numbers k must either divide n or be coprime to n. All k = 2 n / ODD must have 2 as a factor in addition to the integer n / ODD.
Example: For n = 6, k = 4, since 2 (6) / 3 = 2 × 2 = 4.
Corollary 3.3: If n has no coprime k then all the k of n and n itself must be composite and even.
Theorem 1 shows that odd antidivisors k must be coprime to n, while Corollary 3.1 shows that all odd n > 1 have the antidivisor k = 2, which is prime and coprime to odd n. If we have even n, then even k shares the prime factor 2, thus k is even and neutral to n.
Corollary 3.4: Numbers n >1 that do not have prime antidivisors k must be even.
Firstly, n ≤ 2 have no antidivisors, thus no prime antidivisors. If n > 2 has no prime antidivisors, then by Corollary 3.1, n cannot be odd (all odd n must have the antidivisor k = 2; 2 is prime). Thus all n >1 that do not have prime antidivisors must be even
Theorem 4: The even antidivisors k of even composite n must be semidivisors of n, meaning k is the product of at least two primes p that also divide n; one of these primes p = 2.
If the ODD rhs denominator in Equation 2 divides n and n is even, then k is limited to the primes p that divide n and cannot be divisible by any other prime q that is coprime to n. Thus k is a regular, neutral nondivisor of n, and is counted in OEIS A243822(n). The prime divisors p of k must also divide n. Since both k and n are even and the ODD denominator must divide n (otherwise we would not have an integer k), k must be a product of primes p that also divide n. The number k = 2 cannot be an antidivisor of even n, because 2 is a divisor of n and divisors cannot be antidivisors by definition. Theorem 2 established that antidivisors must be neutral to n, therefore neither divisors of n nor coprime to n. Thus even k must be a semidivisor of even n as defined above and at OEIS A243822.
Note that n = 2 does not have antidivisors, but if it did, any antidivisor of prime 2 would need to be coprime to 2 and not divide 2.
Examples: For n = 120, the set of antidivisors is {16, 48, 80}; all of these k do not divide 120, yet they are products of a subset of the set of prime divisors of 120.
For n = 1000, the set of even antidivisors is {16, 80, 400}; all of these k do not divide 1000, yet they are products of a subset of the set of prime divisors of 1000.
Corollary 4.1: n = 2^e cannot have even antidivisors.
The ODD rhs denominator in Equation 2 is coprime to 2*2^e by definition. No integer k can be found. Additionally, prime powers cannot have semidivisors. All powers of 2 with multiplicities i ≤ e must divide 2^e, and are thus divisors of 2^e, which by definition are not antidivisors.
Examples: The antidivisors {3, 7, 9, 19, 27, 57, 73, 171} of n = 256 are all odd.
For n = 2^20 = 1,048,576, the set of antidivisors {3, 7, 9, 43, 49, 127, 129, 337, 387, 889, 2359, 5419, 6223, 16257, 16513, 42799, 48771, 233017, 299593, 699051} contains only odd terms.
Corollary 4.2: Even k of even n that is not a power of 2 must be in the form f(2^(e + 1)), with f a factor of the odd result d of dividing n by the largest prime power 2^e that divides n.
An even n that is not a power of 2 is the product of 2^e and some odd prime or composite factor n. In effect, we can eliminate 2^e from n to leave an odd number d. Let's return to Equation 2. If n is even, we can rewrite 2n as d(2^(e + 1)).
Equation 4: Even antidivisors k:
k (x + ½) = n
k = 2 n / ODD
k = d(2^e + 1) / ODD
In order to furnish an integer k, the ODD denominator must divide d. Thus, all even k must be of the form f(2^(e + 1)).
Examples: The even antidivisors of n = 60 are {8, 24, 40}. The largest odd factor of 60 is d = 15, with factors f = {1, 3, 5, 15}. The even antidivisors of 60 are {2^3 * 1, 2^3 * 3, 2^3 * 5}.
Corollary 4.3: If n is even and has no prime antidivisors k, then n must also have no coprime antidivisors.
Theorem 4 shows that the even antidivisors k of even composite n must be semidivisors of n. Semidivisors k are neutral to n, (1 < gcd(k, n) < k), meaning k neither divides n nor is coprime to n. Such antidivisors k must have the factor 2 | n and some odd divisor of n, thus k must be composite.
Theorem 5: The even antidivisors k > 3 of odd composite n must be semitotatives of n, meaning k is the product of at least one prime p that divides n, and one prime q that is coprime to n. The prime q = 2.
An even k is divisible by 2 which is by definition coprime to an odd n. Thus k is divisible by a prime q coprime to n. The ODD rhs denominator of Equation 2 must divide n in order to produce an integer k. Recall that the ODD divisor must be 3 or greater, since a divisor of 1 would make k exceed n. Thus the ODD divisor must be some product of odd primes p that each divide n. Thus k is the product of 2, which is coprime to odd n, and one or more odd prime divisors p that divide n. Such a k must be neutral to n, that is, k neither divides n nor is coprime to n, since gcd(k, n) = ODD, and ODD is a product of odd primes and cannot equal 1. The case where k = 2 is described by Corollary 3.1; k = 2 is coprime to odd n. Thus k > 3 is a product of q = 2 coprime to odd n, and at least one prime p that divides odd n, and is counted in OEIS A243823(n).
Example: For n = 135, the set of antidivisors is {2, 6, 10, 18, 30, 54, 90}; all but the first term are semitotatives of 135, i.e., they are products of 2 and a subset of the set of prime divisors {3, 5} of 135.
Corollary 5.1: n = p^e must have (e – 1) even antidivisors k, all of which are semitotatives of n.
Powers of odd primes must also be odd. Since n is odd, an even antidivisor k must have 2 as a factor. This factor 2 is coprime to odd n, while the ODD rhs denominator of Equation 2 must divide odd k. The factors of a prime power p^e are {1, p, p^2, p^3, … p^(e – 1), p^e}; each of these factors are solutions to the ODD denominator except p^e itself. Dividing 2 p^e by each of these, we obtain the antidivisors {2, 2p, 2p^2, 2p^3, …, 2p^(e – 1), 2p^e}.
Example: For n = 729, the set of even antidivisors is {2, 6, 18, 54, 162, 486}; all of these k do not divide 729, yet they are products of 2 and each proper divisor of 729.
Thus we have proved that odd antidivisors n must be coprime to n, even antidivisors k of even n must be semidivisors of n, and even antidivisors k of odd composite n must be semitotatives of n, except k = 2 is coprime to odd n.
Theorem 6: If n has no prime antidivisors k, then n has no coprime antidivisors k, and vice versa.
Firstly, n ≤ 2 have no antidivisors, thus no prime or coprime antidivisors. Secondly, we are talking about even n > 1, since by Corollary 3.1, odd n must have the prime antidivisor 2, which is also coprime to odd n. Corollary 3.3 shows that n without coprime antidivisors k must be even, with all even k. Theorem 3 states that even antidivisors k > 2 must be neutral to composite n, meaning k neither divides n nor is coprime to n. Corollary 4.1 suggests we are not talking about integer powers of 2 since n = 2^e cannot have even antidivisors k. Thus the numbers n that do not have prime antidivisors k also do not have prime antidivisors k, and vice versa. Additionally, n and all antidivisors k are even but not perfect powers of 2. Thus, by Corollary 4.2, the antidivisors k are of the form f(2^(e + 1)), with f a factor of the odd result d of dividing n by the largest prime power 2^e that divides n.
This theorem implies that OEIS A241557, Numbers m that do not have prime anti-divisors k, is also the sequence of Numbers m that do not have coprime anti-divisors k. Further, all n > 1 and all of the antidivisors k are even. The k are of the form f(2^(e + 1)).
Additional thoughts on antidivisors still in progress:
Conjecture: The antidivisor k = 2/3 * n is the largest antidivisor of n ≡ 0 (mod 3).
References.
[1] Dudley 1969, Section 9, “Euler’s Theorem and Function”, page 64, specifically, “Every positive integer less than [prime] p is relatively prime to it, so φ(p) = p − 1…”
To discuss this page or report errors mail mike at numberbases dotcom. (Sorry, poor man's captcha).