number of coprime divisors of n with their difference divisible by 3

Question

For an integer n, how many pairs (a, b) [suppose a is smaller than b] of coprime divisors of n exist such that (b-a) is divisible by 3 ?

Advanced version of this question: Let F(n) denote the number of co-prime divisors of n with difference divisible by 3 (as above). What is the sum_i=1..n F(i) ?

Some observations:

• Number of co-prime divisors of n = [∏(2p_i+1)-1]/2 where p_i are powers of primes in prime factorisation of n
• You can drop 3^p from prime factorisation of n, since no required coprime pair will contain factor 3
• Since all primes (except 3) can be written in the form 3k+1 or 3k-1 (even 6k+/-1, if we drop 2, but this is not important for us) then our pairs are either of form 3k+1 vs 3k+1 or of form 3k-1 vs 3k-1

Some recursive formulas I've got to:

• Let F(n) denote the number of coprime divisor pairs of n with difference divisible by 3.
• Let T(n) denote the number of coprime divisor pairs of n (overall)

Then, if m and 3k+1 or 3k-1 are co-prime (suppose divisors of n), we have

1. F(m*(3k+1)^p) = F(m)*(2*p+1) + p [same recursive formula as the one for counting all co-prime divisors of n]
2. F[m*(3k-1)^(2a+b)] = [#pairs from F(m) multiplied by (3k-1)^2] + [#pairs divisors of m with difference non-divisible by 3, with one side multiplied by 3k-1] = [ F(m)*(1+2a) + a ] + [ (T(m)-F(m)) * 2 * (a+b) ]

Can not get yet any further than that.. Any advise appreciated.

Thanks, Dmitry

Answer 1

Consider the prime power decomposition of $n$. Let $P=\Pi(2a_i+1)$ where the $a_i$ are the powers of primes that are 1 modulo 3 and let $Q=\Pi(2b_i+1)$ where the $b_i$ are the powers of primes that are 2 modulo 3. Let $S$ be 1 or -1, depending on whether $\Sigma{b_i}$ is even or odd.

The number of ordered pairs $(x,y)$ such that $x$ and $y$ are coprime divisors of $n$ is $PQ$. Let $C$ be the number of these such that $x-y$ is congruent to 1 mod 3 and $N$ the number of these such that $x-y$ is congruent to 2 mod 3.

The answer to the problem set is then $\frac{C+1}{2}$, where $$C+N=PQ, C-N=SP. $$.

N.B. The crucial argument is to let $(x,y)$ be an ordered pair for $n$ and consider the effect of considering ordered pairs for $p^an$ where $p$ is a prime coprime to $n$.

There are $2a+1$ pairs derived from $(x,y)$ $$(x,y),(px,y),(x,py),(p^2,y), ...$$

Now consider the effect on $C$ and $N$ for

$p$ congruent to 1,

$p$ congruent to 2, $a$ even

$p$ congruent to 2, $a$ odd.