[seqfan] Alternate definition of A089233

[Andrew Weimholt]

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 are welcome.

------------------------------------------------------------------------------------------------------------

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

And since the mapping is both injective and surjective, it is bijective.
------------------------------------------------------------------------------------------------------------

Andrew