[seqfan] Re: Alternate definition of A089233
Max Alekseyev
maxale at gmail.com
Tue Dec 6 22:07:28 CET 2011
There is a simpler proof based on the known formula for A089233.
The number of divisors of n^2 that are less then n is (A000005(n^2)-1)/2
(since the divisors of n^2, except n, form pairs d,n^2/d in which
exactly one divisor is less than n).
On the other hand, the number of divisors of n smaller than n is
A000005(n)-1 and they all divide n^2.
Hence, the number of divisors of n^2 that do not divide n and are less
than n equals
(A000005(n^2)-1)/2 - (A000005(n)-1) = A063647(n) - A000005(n) + 1
that matches the formula for A089233.
Regards,
Max
On Mon, Dec 7, 2009 at 3:22 AM, Andrew Weimholt
<andrew.weimholt at gmail.com> wrote:
> 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
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list