Date: Sun, 6 Dec 2009 16:22:25 -0800 From: Andrew Weimholt <andrew.weimholt(AT)gmail.com> Subject: [seqfan] Alternate definition of A089233 The definition of A089233 is a(n) = Number of coprime pairs of divisors > 1 of n It is also the number of divisors of n^2 which do not divide n and which are less than n. Here is my attempt at a proof. Comments and/or corrections will be welcomed. ------------------------------------------------------------------------------------------------------------ The following is a proof that the two sequence definitions below are equivalent (1) a(n) = Number of coprime pairs of divisors > 1 of n. (i.e. number of (x,y), such that 1<x<y, x|n, y|n, GCD(x,y)==1) (2) a(n) = Number of divisors of n^2 which do not divide n and are less than n. (i.e. number of d, such that d|n^2, d<n, and NOT( d|n )) We will first prove a few lemmas, and then in the final theorem, we will show that there exists a bijective mapping from the d in definition (1) to the (x,y) in definition (2), which proves the two sequences are identical. ------------------------------------------------------------------------------------------------------------ Lemma 1: If d is a divisor of n^2 which does not divide n and which is less than n, then d/GCD(n,d) > 1 and n/GCD(n,d) > 1 Proof: d/GCD(n,d) = 1 implies d=CGD(n,d), which implies d|n, but by definition d does not divide n, therefore d/GCD(n,d) > 1 n/GCD(n,d) = 1 implies n=GCD(n,d), which implies n|d, which implies d>=n, but by definition d<n, therefore n/GCD(n,d) > 1 ------------------------------------------------------------------------------------------------------------ Lemma 2: If d is a divisor of n^2 which does not divide n and which is less than n, then d/GCD(n,d) and n/GCD(n,d) both divide n Proof: n / (n/GCD(n,d)) = GCD(n,d), which is an integer, therefore n/GCD(n,d) divides n. n / (d/GCD(n,d)) = n*GCD(n,d) / d Assume n*GCD(n,d) / d is not an integer. Then there exists some prime p and positive integer k, such that p^k divides d but does not divide n*GCD(n,d). Since d | n^2, p^k must divide n^2 and p must divide n. Let p^a be the highest power of p that divides n. Then p^(2a) is the highest power of p that divides n^2, and a < k <= 2a. Since k > a, p^a | GCD(n,d), therefore p^(2a) | n*GCD(n,d), but since 2a >= k, p^k must also divide n*GCD(n,d), which contradicts our assumption. Therefore n*GCD(n,d) / d is an integer and d/GCD(n,d) divides n. ------------------------------------------------------------------------------------------------------------ Lemma 3: If d is a divisor of n^2 which does not divide n and which is less than n, then d/GCD(n,d) is coprime to n/GCD(n,d) Proof: Assume there is some prime p which divides both d/GCD(n,d) and n/GCD(n,d). Then p divides both d and n, and therefore divides GCD(n,d). Let p^k be the highest power of p which divides both n and d. Then p^k is also the highest power of p which divides GCD(n,d). If p divides d/GCD(n,d), then p divides d/p^k, which implies p^(k+1) divides d. If p divides n/GCD(n,d), then p divides n/p^k, which implies p^(k+1) divides n. But p^k is the highest power of p which divides both d and n, (a contradiction) Therefore d/GCD(n,d) and n/GCD(n,d) are coprime. ------------------------------------------------------------------------------------------------------------ Theorem 1: There exists a bijective mapping from the set D of integers {d such that d | n^2, d<n, and NOT( d | n ) } to the set S of ordered pairs { (x,y) such that 1<x<y, x|n, y|n, and GCD(x,y) = 1. } Proof: In part 1 of the proof, we will show that each d in D maps to an (x,y) in S. In part 2, we will show that the mapping in part 1 is injective. In part 3, we will show that the mapping in part 1 is surjective. Part 1: given d, we choose x = d / GCD(n,d) y = n / GCD(n,d) By lemma 1, x>1 and by our definition of D, d<n, which implies n/GCD(n,d) > d/GCD(n,d) therefore 1<x<y By lemma 2, x|n and y|n. By lemma 3, GCD(x,y) = 1 Therefore (x,y) is in S. Part 2: Let d_1 and d_2 be members of D such that d_1 =/= d_2, and let (x_1,y_1) and (x_2,y_2) be their respective mappings on S. Then (x_1,y_1) = ( d_1/GCD(n,d_1) , n/GCD(n,d_1) ) and (x_2,y_2) = ( d_2/GCD(n,d_2) , n/GCD(n,d_2) ) Assume that the ordered pairs are equal. Then (1) n / GCD(n,d_1) = n / CGD(n,d_2) And (2) d_1 / GCD(n,d_1) = d_2 / GCD(n,d_2) But (1) implies GCD(n,d_1) = GCD(n,d_2), which by (2) implies d_1 = d_2 (a contradiction) Therefore, the ordered pairs are not equal, and the mapping is injective. Part 3: given (x,y) in S, we want to find a d in D, such that d maps to (x,y) using the mapping in part 1. We will prove that d = n*x/y implies x = d / GCD(n,d), and y = n / GCD(n,d) y*d = n*x since by definition of S, GCD(x,y)=1, x|d, therefore there exists some positive integer k, such that d = k*x and n = k*y Then GCD(n,d) = GCD(k*x, k*y) which equals k, since x and y are coprime. Therefore d = GCD(n,d) * x and n = GCD(n,d) * y Rearranging, we get x = d/GCD(n/d) y = n/GCD(n/d) Therefore the mapping in part 1 is surjective Since the mapping is both injective and surjective, it is bijective. ------------------------------------------------------------------------------------------------------------