Find All Pairs (m,n) with mn-1 Dividing n^3+1

[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.[/color]

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

Good luck!

 

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

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

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.

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

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

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

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

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

Spoiler

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 = (n³ + 1)/(mn - 1).

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

...k = (n³ + 1)/(mn - 1); (m: m ≠ 1/n).

Solving for m,

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

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

So the final ordered pairs are:

...( (n³ + 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.]

 

[collinsmark]

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

Spoiler

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

 

[mfb]

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.[/color]

Spoiler

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?

 

[lpetrich]

Spoiler

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.

 

[lpetrich]

Spoiler

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.

 

[lpetrich]

Spoiler

Trying eddybob123's first hint, let
(n³+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
(n³+1) - (n*m-1) * (n*k-1) = 0
for positive-integer k. For nonzero n, it becomes
n² - 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}