# Math Puzzle

1. Aug 17, 2013

### eddybob123

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. Aug 22, 2013

### collinsmark

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.

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

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
3. Aug 22, 2013

### collinsmark

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
4. Aug 22, 2013

### 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?

5. Oct 3, 2013

### lpetrich

I searched all possible positive-integer solutions up to n = 2000, and these {n,m} pairs are the only ones that I found:
{{1,2},{1,3},{2,1},{2,2},{2,5},{3,1},{3,5},{5,2},{5,3}}

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
6. Oct 3, 2013

### lpetrich

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
implying
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.

7. Oct 11, 2013

### lpetrich

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:
{1,2,3},{1,3,2},{2,1,5},{2,2,2},{2,5,1},{3,1,5},{3,5,1},{5,2,3},{5,3,2}