# Number of divisors problem

• Dec 6th 2010, 07:03 PM
Arzx
Number of divisors problem
I'm trying to solve the problem of how many solutions (x,y) there are to:
$1/x + 1/y = 1/n$
for a fixed positive integer n and positive integers x and y.

I've been told that this equates to finding the # of divisors of $n^2$ minus the # of duplicate solutions, which in total equals $\tau(n^2) - (\tau(n^2)-1)/2$ (where $\tau$ is the divisor function).

My question is, what is the reasoning for $(\tau(n^2)-1)/2$ being the number of duplicate solutions? Where does this come from?

Thanks a lot!
• Dec 6th 2010, 07:32 PM
tonio
Quote:

Originally Posted by Arzx
I'm trying to solve the problem of how many solutions (x,y) there are to:
$1/x + 1/y = 1/n$
for a fixed positive integer n and positive integers x and y.

I've been told that this equates to finding the # of divisors of $n^2$ minus the # of duplicate solutions, which in total equals $\tau(n^2) - (\tau(n^2)-1)/2$ (where $\tau$ is the divisor function).

My question is, what is the reasoning for $(\tau(n^2)-1)/2$ being the number of duplicate solutions? Where does this come from?

Thanks a lot!

I have another question: what do you mean by "duplicate solutions"? Solutions to what and what does "duplicate" mean in this case?

tonio
• Dec 6th 2010, 08:17 PM
Arzx
Quote:

Originally Posted by tonio
I have another question: what do you mean by "duplicate solutions"? Solutions to what and what does "duplicate" mean in this case?

tonio

My understanding is that the solutions are the values of x and y that make 1/x + 1/y = 1/n true, and the "duplicates" are values that appear more than once if you just consider all the divisors of $n^2$.

The way I got to this was that 1/x + 1/y = 1/n => n(x+y) = xy => (x-n)(y-n) = $n^2$. So the solutions are all the divisors of $n^2$, -- is that right? would you approach this in a different way?
• Dec 6th 2010, 09:33 PM
chiph588@
Quote:

Originally Posted by Arzx
My understanding is that the solutions are the values of x and y that make 1/x + 1/y = 1/n true, and the "duplicates" are values that appear more than once if you just consider all the divisors of $n^2$.

The way I got to this was that 1/x + 1/y = 1/n => n(x+y) = xy => (x-n)(y-n) = $n^2$. So the solutions are all the divisors of $n^2$, -- is that right? would you approach this in a different way?

Perhaps the solutions $(x,y)$ and $(y,x)$ are considered duplicates.
• Dec 7th 2010, 06:02 AM
tonio
Quote:

Originally Posted by Arzx
My understanding is that the solutions are the values of x and y that make 1/x + 1/y = 1/n true, and the "duplicates" are values that appear more than once if you just consider all the divisors of $n^2$.

The way I got to this was that 1/x + 1/y = 1/n => n(x+y) = xy => (x-n)(y-n) = $n^2$. So the solutions are all the divisors of $n^2$, -- is that right? would you approach this in a different way?

I think that's a very nice and promising way to approach it. About "duplicate" I think Chip's idea may be right. For example,

for $\displaystyle{n=6\,,\,\frac{1}{x}+\frac{1}{y}=\fra c{1}{6}\Longleftrightarrow (x-6)(y-6)=36}$ . We have here

the solutions $(9,18), (18,9)$ , and these are, perhaps, called "duplicate". I'd rather call the solutions "different up to order of x,y" ,

but as long as the idea is clear...

In the above example, we've the solutions $(42,7), (24,8), (18,9),(15,10),(12,12,)$ , 5 different

(up to order) solutions, but I am not able to apply the "duplicate" thingy a priori, i.e. before I know

the solutions...

Tonio
• Dec 7th 2010, 06:28 AM
Arzx
Quote:

Originally Posted by tonio
I think that's a very nice and promising way to approach it. About "duplicate" I think Chip's idea may be right. For example,

for $\displaystyle{n=6\,,\,\frac{1}{x}+\frac{1}{y}=\fra c{1}{6}\Longleftrightarrow (x-6)(y-6)=36}$ . We have here

the solutions $(9,18), (18,9)$ , and these are, perhaps, called "duplicate". I'd rather call the solutions "different up to order of x,y" ,

but as long as the idea is clear...

In the above example, we've the solutions $(42,7), (24,8), (18,9),(15,10),(12,12,)$ , 5 different

(up to order) solutions, but I am not able to apply the "duplicate" thingy a priori, i.e. before I know

the solutions...

Tonio

The solutions in your example before removing the "duplicates" - there are 9 of them, which does match the number of divisors of 36. So that makes sense.

If you were asked the question "For n a fixed pos. integer, how many solutions (x,y) are there to the equation 1/x + 1/y = 1/n?", would you think you were meant to consider every solution or just the solutions up to order? Because if it is up to order, I really don't know how derive that number of "duplicate" solutions in the general case. :/
• Dec 7th 2010, 07:07 AM
Bingk
If I've understood your formula correctly, I don't think $(\tau(n^2)-1)/2$ is the number of duplicate solutions.

From your analysis, you'll notice that to get $x$ and $y$, you have to get two factors of $n^2$. We will call these factor pairs $a$ and $b$, which come from the divisors of $n^2$.

Now, you should note that from the list of divisors, we can pair them up to get the desired product, except for one case, which is when $a=b$. So, if we add one to the number of divisors of $n^2$ and divide it by two, you'll get the number of solutions of $(x,y)$ that satisfy your conditions.

In other words, the solution is $(\tau(n^2)+1)/2$

You'll notice that this is essentially the same as your formula $\tau(n^2) - (\tau(n^2)-1)/2$

The corresponding interpretation of your formula is that you started with the number of divisors, then you removed the corresponding partner from the paired factors