Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Math Puzzle

  1. Aug 17, 2013 #1
    Find all ordered pairs (m,n) such that mn-1 divides n^3+1.

    Hint #1:
    Write the expression as a+bn for some coefficients a and b.

    Hint #2:
    Show that if (m,n) is a solution, then (n,m) is also a solution.

    Good luck!
  2. jcsd
  3. Aug 22, 2013 #2


    User Avatar
    Homework Helper
    Gold Member

    I'm awful at math(s) but I'll give this one a shot since no one else has, as of yet. Maybe I'll learn something new along the way.

    Do you mean, "divides evenly," as in no remainder? I mean in normal arithmetic, any number can divide any other number (as long as the divisor [denominator] is not zero); there just might be a remainder is all.

    From here on, I'll just assume you mean "divides evenly."

    Also, is there any restriction on the cardinality of m and n? I mean, are they restricted to be real numbers? rational numbers? integers? natural numbers?

    I'll just assume complex numbers to be more general, but I believe this solution is the same for any cardinality above the integers.

    Reply to Hint #1:
    Write what expression? You mean the (n3 + 1)/(mn - 1) expression? I'm not sure I follow your hint here.

    Reply to Hint #2:
    I'm afraid I don't really follow this hint either.

    Here's my attempted solution (for rational, real or complex m and n).

    Since we want the expressions to divide evenly, it means we place restrictions on n and m, to produce a natural number k, (k: k = 1, 2, 3, ...) such that

    .....k = (n3 + 1)/(mn - 1).

    We also note that we can't have a zero in the denominator, so there is a further restriction that m1/n. That gives us,

    .....k = (n3 + 1)/(mn - 1); (m: m1/n).

    Solving for m,

    .....m = (n3 + 1 + k)/(kn); (m: m1/n). [Edit: and it almost goes without saying that n ≠ 0]

    A little substitution shows, 1/n ≠ (n3 + 1 + k)/(kn) → n ≠ -1.

    So the final ordered pairs are:

    .....( (n3 + 1 + k)/(kn), n ),

    such that,
    n is any rational, real or complex number, with the restriction that n ≠ -1, [also n ≠ 0].
    k is any natural number. (i.e., k = 1, 2, 3, ...).

    [Edit: n ≠ 0 too. So n ≠ -1, n ≠ 0.]
    Last edited: Aug 22, 2013
  4. Aug 22, 2013 #3


    User Avatar
    Homework Helper
    Gold Member

    Here's a half-baked answer if we restrict m and n to the domain of integers:

    We know that n ≠ 0, n ≠ -1 from the last post, but I'll include those in the domain of my answer anyway. Just note that there are no valid, ordered pairs at those locations where n = 0 or -1.

    Valid, ordered pairs for n ≥ -1:
    (2, 1), (2, 2), (3, 1), (5, 2), (5, 3)

    Valid, ordered pairs for n < -1:
    (1 - n, n)

    Notice that there's an infinite, yet countable number of ordered pairs for n < -1. Examples include (3, -2), (4, -3), (5, -4), (6, -5), ...

    I have a proof to show that those ordered pairs exist and are valid, but I haven't yet proved that they are the only ones. (I'm suspecting they might be though).
    Last edited: Aug 22, 2013
  5. Aug 22, 2013 #4


    User Avatar
    2017 Award

    Staff: Mentor

    Those puzzles usually imply that m and n are natural numbers (or at least integers).

    Small pairs: (1,2), (2,1), (1,3), (3,1), (2,2), (2,5), (5,2), (3,5), (5,3). If there are more, they have to have n>32 or m>32.

    It is clear that n^3 +1 = (n+1)(n^2-n+1) and nm-1 is not a divisor of one of those factors (apart from n=2), but how can we show that it cannot be a divisor of the product as a whole, if nm-1 is not a prime number?
  6. Oct 3, 2013 #5
    I searched all possible positive-integer solutions up to n = 2000, and these {n,m} pairs are the only ones that I found:

    I did it first with Mathematica, going up to 100, then with C++, going up to 2000. With C++, I had to be careful to use "long long" 64-bit integers. However, with a 2-GHz Intel Core 2 Duo, it took 1m 8s of CPU time. Search time goes as O(n^3).

    I conjecture that these are the only solutions.

    But among these solutions, if {n,m} is a solution, then {m,n} is also a solution.
    Last edited: Oct 3, 2013
  7. Oct 3, 2013 #6
    I did a run up to n = 10,000. It took 2 hr 15 min of CPU time. No additional solutions.

    However, I've been totally stumped by
    n*m-1 evenly dividing n^3+1
    n*m-1 evenly dividing m^3+1.

    I've also had no progress in proving that the solutions I'd found are the only solutions.
  8. Oct 11, 2013 #7
    Trying eddybob123's first hint, let
    (n3+1) - (n*m-1) * (a*n+b) = 0
    where 0 <= b < n and a,b are nonnegative integers. Expanding gives (b+1) + n*(some integer) = 0, implying that b = n-1.

    This inspires a form for that ratio, so let's try
    (n3+1) - (n*m-1) * (n*k-1) = 0
    for positive-integer k. For nonzero n, it becomes
    n2 - n*m*k + m + k = 0
    So if {n,m} is a solution, then {n,k} is also a solution.

    It's hard for me to proceed further, however. Here are the {n,m,k} values that I'd found:
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook