Results 1 to 7 of 7

Math Help - Number of divisors problem

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    10

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Arzx View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by tonio View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by Arzx View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Arzx View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Dec 2010
    Posts
    10
    Quote Originally Posted by tonio View Post
    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. :/
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Aug 2009
    Posts
    170
    Thanks
    8
    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
    Last edited by Bingk; December 7th 2010 at 06:10 AM. Reason: Added interpretation
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of positive divisors of n
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 17th 2011, 11:04 AM
  2. Number of Positive Divisors
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 6th 2011, 03:35 AM
  3. divisors of a number
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: April 8th 2010, 08:34 AM
  4. Number of odd divisors
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 17th 2008, 07:00 AM
  5. number of divisors
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 15th 2008, 08:34 PM

Search Tags


/mathhelpforum @mathhelpforum