P(x,A): Number of positive divisors of A not greater than x
d(x): number of positive divisors of A
If x and y are positive integers and co-prime to each other, then
d(x)*d(y) + 1 = Σ P(z, x){z: z>0 and z|y} + ΣP(w, y) {w:w>0 and w|x} <—- Result
Proof:
Identity(1):
If x, A > 0 and x is a divisor of A, then P(x, A)+P(A/x, A) = d(A) + 1
Identity(2):
If x, A > 0 and x is not a divisor of A, then P(x, A)+P(A/x, A) = d(A)
P(x, x*y) = d(x) + number of divisors of x*y but not divisors of x and less than x
Consider a divisor z (not 1) of y. All the multiples of z less than x are divisors of x*y but not x.
Number of multiples of z less than x
= Number of divisors of x less than x/z
= Number of divisors of x not greater than x/z
= P(x/z, x)
As y is co-prime to x
P(x, x*y) = d(x) + Σ P(x/z, x) {z: z > 1 and z|y}
P(x, x*y) = Σ P(x/z, x) {z: z>0 and z|y}
From Identities (1) and (2)
P(x, x*y) = 1 + Σ (d(x)-P(z, x)) {z: z>0 and z|y}
P(x, x*y) = d(x)*d(y) +1 – Σ P(z, x) {z: z>0 and z|y}
Similarly
P(y, x*y) = d(x)*d(y) + 1 – Σ P(w, y) {w: w>0 and w|x}
Add these both equations
P(x, x*y) + P(y, x*y) = 2*d(x)*d(y) + 2 – Σ P(z, x) {z: z>0 and z|y} – Σ P(w, y) {w: w>0 and w|x}
From Identity (1)
d(x*y) + 1 = 2*d(x)*d(y) + 2 – Σ P(z, x) {z: z>0 and z|y} – Σ P(w, y) {w: w>0 and w|x}
If x and y are co-prime to each other, then d(x*y) = d(x)*d(y)
d(x)*d(y)+1 = 2*d(x)*d(y)+2- Σ P(z, x) {z: z>0 and z|y} – Σ P(w, y) {w: w>0 and w|x}
Σ P(z, x) {z: z>0 and z|y} + Σ P(w, y) {w: w>0 and w|x} = d(x)*d(y) + 1
