# Thread: Number of divisors problem

1. ## Number of divisors problem

I'm trying to solve the problem of how many solutions (x,y) there are to:
$\displaystyle 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 $\displaystyle n^2$ minus the # of duplicate solutions, which in total equals $\displaystyle \tau(n^2) - (\tau(n^2)-1)/2$ (where $\displaystyle \tau$ is the divisor function).

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

Thanks a lot!

2. Originally Posted by Arzx
I'm trying to solve the problem of how many solutions (x,y) there are to:
$\displaystyle 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 $\displaystyle n^2$ minus the # of duplicate solutions, which in total equals $\displaystyle \tau(n^2) - (\tau(n^2)-1)/2$ (where $\displaystyle \tau$ is the divisor function).

My question is, what is the reasoning for $\displaystyle (\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

3. 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 $\displaystyle n^2$.

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

4. 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 $\displaystyle n^2$.

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

5. 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 $\displaystyle n^2$.

The way I got to this was that 1/x + 1/y = 1/n => n(x+y) = xy => (x-n)(y-n) = $\displaystyle n^2$. So the solutions are all the divisors of $\displaystyle 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 \displaystyle{n=6\,,\,\frac{1}{x}+\frac{1}{y}=\fra c{1}{6}\Longleftrightarrow (x-6)(y-6)=36}$ . We have here

the solutions $\displaystyle (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 $\displaystyle (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

6. 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 \displaystyle{n=6\,,\,\frac{1}{x}+\frac{1}{y}=\fra c{1}{6}\Longleftrightarrow (x-6)(y-6)=36}$ . We have here

the solutions $\displaystyle (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 $\displaystyle (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. :/

7. If I've understood your formula correctly, I don't think $\displaystyle (\tau(n^2)-1)/2$ is the number of duplicate solutions.

From your analysis, you'll notice that to get $\displaystyle x$ and $\displaystyle y$, you have to get two factors of $\displaystyle n^2$. We will call these factor pairs $\displaystyle a$ and $\displaystyle b$, which come from the divisors of $\displaystyle 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 $\displaystyle a=b$. So, if we add one to the number of divisors of $\displaystyle n^2$ and divide it by two, you'll get the number of solutions of $\displaystyle (x,y)$ that satisfy your conditions.

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

You'll notice that this is essentially the same as your formula $\displaystyle \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