Number of divisors problem

**Arzx** · December 6th 2010, 06:03 PM

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!

**tonio** · December 6th 2010, 06:32 PM

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

**Arzx** · December 6th 2010, 07:17 PM

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?

**chiph588@** · December 6th 2010, 08:33 PM

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.

**tonio** · December 7th 2010, 05:02 AM

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

**Arzx** · December 7th 2010, 05:28 AM

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. :/

**Bingk** · December 7th 2010, 06:07 AM

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

Thread: Number of divisors problem

LinkBack

Thread Tools

Display

Number of divisors problem

Similar Math Help Forum Discussions

Number of positive divisors of n

Number of Positive Divisors

divisors of a number

Number of odd divisors

number of divisors

Search Tags