Пары натуральных чисел

Задача.

(IMO, 1994) 
Determine all ordered pairs (m,n) of positive integers such that (n3 + 1)/(mn − 1) is an integer. 

Найдите все упорядоченные пары натуральных чисел (m,n), для которых 

(n3 + 1)/(mn − 1)  является целым числом.


Решение.

1) Очевидно, что выражение mn делится нацело на m и n, а значит пары чисел (mn − 1, m) и (mn − 1, n) являются взаимно простыми: НОД (mn − 1, m) = 1, НОД (mn − 1, n) = 1.

Если (n3 + 1)/(mn − 1) - целое число, то (n3 + 1 + mn − 1)/(mn − 1) = n * (n² + m)/(mn − 1) также является целым числом. Поскольку пара (mn − 1, n)  - взаимно простые, то (n² + m)/(mn − 1) должно быть целым числом. 

Следовательно, (n² + m + m * (mn - 1))/(mn − 1) = n * (m² + n)/(mn − 1) также является целым числом. Аналогично, пара (mn − 1, n) - взаимно простые, значит (m² + n)/(mn − 1) должно быть целым числом. Целым числом будет и значение выражения  (m² + n + m² * (mn − 1))/(mn − 1) = (m³ + 1)/(mn − 1).

Имеется симметрия переменных m и n: (n3 + 1)/(mn − 1) является целым тогда и только тогда, когда (m³ + 1)/(mn − 1) - целое число. Т.е. если пара (m;n) является решением задачи, то пара (n;m) также будет  решением. 

2) Рассмотрим случай m = 1. 2/(n − 1) - целое. Это возможно только при n = 2 или n = 3. В силу симметричности m и n, получим пары решений: (1;2), (1;3), (2;1), (3;1).

3) Рассмотрим случай m = 2. Тогда 9/(2n − 1) - целые, а это возможно только при 2n - 1 = 9 или 2n - 1= 3 (заметим, что если n - натуральное, то 2n − 1 > 0). Т.е. при n = 5 или n = 2. В силу симметричности m и n, получим пары решений: (2;2), (2;5), (5;2).

4) Рассмотрим случай m = 3. Тогда 28/(3n − 1) - целые, а это возможно только при 3n - 1 = 28 или 3n - 1 = 14 или 3n - 1 = 7 или 3n - 1= 4 или 3n - 1= 2 (заметим, что если n - натуральное, то 3n − 1 > 0). Целых решений этих линейных уравнений немного: n = 5 или n = 1. В силу симметричности m и n, получим только две новые пары решений: (3;5), (5;3).

5) Пусть m > 3 (*).  Учитывая симметричность переменных, для определенности предположим, что m ≤ n (**). Заметим, что тогда для всех натуральных n: mn − 1 > 0. А значит, если (m² + n)/(mn − 1)  является целым числом, то m² + n ≥ mn − 1 или n * (m - 1) ≤ m² + n.

n ≤ (m² + n)/(m - 1) или n ≤ m + 1 + 2/(m - 1). 

Следовательно, учитывая (*), (**): m ≤ n ≤ m + 1 (при m > 3 выражение 2/(m - 1) < 1).

Т.е. остается проверить только два случая:

а) n = m 

Имеем: (m² + n)/(mn − 1) = (m² + m)/(m² − 1) = m/(m - 1) должно быть целым. Но это выполняется только при m = 2, что противоречит (*).

б) n = m + 1

Имеем: (m² + n)/(mn − 1) = (m² + m + 1)/(m² + m - 1)  =  1 - 2/(m² + m - 1) должно быть целым, но это невозможно при m > 3.

При 3 < m ≤ n и 3 < n ≤ m решений нет. 

Ответ: (1;2), (1;3), (2;1), (3;1), (2;2), (2;5), (5;2), (3;5), (5;3).

Ресурсы:

http://mathus.ru/math/imon.pdf

https://cambomaths.files.wordpress.com/2010/03/cambomaths-wordpress-com-determine-all-ordered-pairs.pdf