Задача.
(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 * (n2 +
m)/(mn − 1) также является целым числом. Поскольку пара (mn − 1,
n) - взаимно простые, то (n2 + m)/(mn − 1)
должно быть целым числом.
Следовательно, (n2 + m + m * (mn -
1))/(mn − 1) = n * (m2 + n)/(mn − 1) также
является целым числом. Аналогично, пара (mn − 1, n) - взаимно
простые, значит (m2 + n)/(mn − 1) должно
быть целым числом. Целым числом будет и значение выражения (m2
+ n + m2 * (mn − 1))/(mn − 1) = (m3 +
1)/(mn − 1).
Имеется симметрия переменных m и n: (n3 + 1)/(mn − 1) является
целым тогда и только тогда, когда (m3 +
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. А значит,
если (m2 + n)/(mn − 1) является целым
числом, то m2 + n ≥ mn − 1
или n * (m - 1) ≤ m2 +
n.
n ≤ (m2 +
n)/(m - 1) или n ≤ m + 1
+ 2/(m - 1).
Следовательно, учитывая (*), (**): m ≤ n ≤ m +
1 (при m > 3 выражение 2/(m - 1) < 1).
Т.е. остается проверить только два случая:
а) n = m
Имеем: (m2 + n)/(mn − 1) = (m2 +
m)/(m2 − 1) = m/(m - 1) должно быть целым. Но это
выполняется только при m = 2, что противоречит (*).
б) n = m + 1
Имеем: (m2 + n)/(mn − 1) = (m2 +
m + 1)/(m2 + m - 1) = 1 - 2/(m2 + 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).
Ресурсы:
