IMO 1994 · Problem 4
Determine all ordered pairs \((m, n)\) of positive integers such that \[ \frac{n^3+1}{mn-1} \] is an integer.
Official text of the problem. Official problem paper (PDF)
Answer
The ordered pairs are \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
Solution
The pair \((1,1)\) is excluded because the denominator is zero. For every other pair, write \(d=mn-1>0\).
First, the divisibility condition is symmetric in \(m,n\). Indeed, if \(d\mid n^3+1\), then the identity \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] shows that \(d\mid m^3+1\). Interchanging \(m,n\) proves the converse. Thus we may assume \(m\le n\), and include the reversed pairs afterward.
Case 1: \(m=1\). We have \(n\ge2\), and the equivalent condition \(mn-1\mid m^3+1\) becomes \[ n-1\mid2. \] Hence \(n=2\) or \(n=3\).
Case 2: \(m=2\). Now \(n\ge2\), and \[ 2n-1\mid9. \] Since \(2n-1\ge3\), it equals \(3\) or \(9\). Thus \(n=2\) or \(n=5\).
Case 3: \(m\ge3\). Let \[ q=\frac{m^3+1}{mn-1}, \] which is a positive integer. Reducing \(q(mn-1)=m^3+1\) modulo \(m\) gives \[ q\equiv-1\pmod m. \] Also, since \(n\ge m\), \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] Therefore \(1\le q\le m\), so the congruence forces \(q=m-1\). Consequently, \[ (m-1)(mn-1)=m^3+1, \] which simplifies to \[ (m-1)n=m^2+1=(m-1)(m+1)+2. \] Thus \(m-1\mid2\). Since \(m\ge3\), we obtain \(m=3\), and then \(n=5\).
We have therefore found exactly the candidates \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] with \(m\le n\). Their original quotients are, respectively, \[ 9,\quad14,\quad3,\quad14,\quad9, \] so all five work. By the proved symmetry, their reversed pairs also work. These give precisely the nine pairs stated above.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1994 · Aufgabe 4
Man bestimme alle geordneten Paare \((m, n)\) positiver ganzer Zahlen, für die \[ \frac{n^3+1}{mn-1} \] eine ganze Zahl ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
Die geordneten Paare sind \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
Lösung
Das Paar \((1,1)\) ist ausgeschlossen, da der Nenner null ist. Für jedes andere Paar setzen wir \(d=mn-1>0\).
Zunächst ist die Teilbarkeitsbedingung symmetrisch in \(m,n\). Gilt nämlich \(d\mid n^3+1\), so folgt aus der Identität \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] die Teilbarkeit \(d\mid m^3+1\). Durch Vertauschen von \(m,n\) erhält man die Umkehrung. Somit dürfen wir \(m\le n\) annehmen und anschließend die Paare mit vertauschten Komponenten hinzunehmen.
Fall 1: \(m=1\). Es gilt \(n\ge2\), und die äquivalente Bedingung \(mn-1\mid m^3+1\) wird zu \[ n-1\mid2. \] Also ist \(n=2\) oder \(n=3\).
Fall 2: \(m=2\). Nun gilt \(n\ge2\), und \[ 2n-1\mid9. \] Wegen \(2n-1\ge3\) ist dieser Ausdruck gleich \(3\) oder \(9\). Somit ist \(n=2\) oder \(n=5\).
Fall 3: \(m\ge3\). Sei \[ q=\frac{m^3+1}{mn-1}, \] also eine positive ganze Zahl. Reduktion von \(q(mn-1)=m^3+1\) modulo \(m\) ergibt \[ q\equiv-1\pmod m. \] Außerdem gilt wegen \(n\ge m\) \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] Daher ist \(1\le q\le m\), sodass aus der Kongruenz \(q=m-1\) folgt. Folglich gilt \[ (m-1)(mn-1)=m^3+1, \] was sich zu \[ (m-1)n=m^2+1=(m-1)(m+1)+2 \] vereinfacht. Also gilt \(m-1\mid2\). Wegen \(m\ge3\) erhalten wir \(m=3\) und damit \(n=5\).
Wir haben somit genau die Kandidaten \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] mit \(m\le n\) gefunden. Ihre ursprünglichen Quotienten sind der Reihe nach \[ 9,\quad14,\quad3,\quad14,\quad9, \] also erfüllen alle fünf die Bedingung. Aufgrund der bewiesenen Symmetrie erfüllen auch die Paare mit vertauschten Komponenten die Bedingung. Dies ergibt genau die neun oben angegebenen Paare.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1994 · Soru 4
\[ \frac{n^3+1}{mn-1} \] ifadesinin bir tam sayı olduğu tüm pozitif tam sayı sıralı ikililerini \((m, n)\) belirleyiniz.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
Sıralı ikililer şunlardır: \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
Çözüm
Payda sıfır olduğundan \((1,1)\) ikilisi dışarıda bırakılır. Diğer her ikili için \(d=mn-1>0\) yazalım.
Öncelikle, bölünebilme koşulu \(m,n\)'ye göre simetriktir. Gerçekten de \(d\mid n^3+1\) ise, \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] özdeşliği \(d\mid m^3+1\) olduğunu gösterir. \(m,n\)'nin yerlerini değiştirmek tersini kanıtlar. Bu nedenle \(m\le n\) olduğunu varsayabilir ve daha sonra bileşenleri yer değiştirmiş ikilileri de ekleyebiliriz.
1. Durum: \(m=1\). \(n\ge2\)'dir ve eşdeğer koşul olan \(mn-1\mid m^3+1\), \[ n-1\mid2 \] hâline gelir. Buradan \(n=2\) veya \(n=3\) olur.
2. Durum: \(m=2\). Bu kez \(n\ge2\)'dir ve \[ 2n-1\mid9. \] \(2n-1\ge3\) olduğundan, bu sayı \(3\) veya \(9\)'a eşittir. Dolayısıyla \(n=2\) veya \(n=5\) olur.
3. Durum: \(m\ge3\). \[ q=\frac{m^3+1}{mn-1} \] olsun; bu bir pozitif tam sayıdır. \(q(mn-1)=m^3+1\) eşitliğini modül \(m\)'ye göre indirgersek \[ q\equiv-1\pmod m \] elde ederiz. Ayrıca, \(n\ge m\) olduğundan, \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] Dolayısıyla \(1\le q\le m\)'dir; bu nedenle denklikten zorunlu olarak \(q=m-1\) çıkar. Buna göre, \[ (m-1)(mn-1)=m^3+1, \] olur ve bu eşitlik sadeleştirilince \[ (m-1)n=m^2+1=(m-1)(m+1)+2 \] elde edilir. Böylece \(m-1\mid2\)'dir. \(m\ge3\) olduğundan \(m=3\), ardından da \(n=5\) buluruz.
Böylece \(m\le n\) koşulunu sağlayan adayların tam olarak \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] olduğunu bulduk. Başlangıçtaki ifadenin bu ikililer için değerleri sırasıyla \[ 9,\quad14,\quad3,\quad14,\quad9, \] olduğundan beşi de koşulu sağlar. Kanıtlanan simetri gereği, bileşenleri yer değiştirmiş ikililer de koşulu sağlar. Bunlar, yukarıda belirtilen dokuz ikiliyi verir.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1994 · Problema 4
Determinar todos los pares ordenados \((m, n)\) de enteros positivos tales que \[ \frac{n^3+1}{mn-1} \] sea un entero.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
Los pares ordenados son \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
Solución
El par \((1,1)\) queda excluido porque el denominador es cero. Para cualquier otro par, escribamos \(d=mn-1>0\).
En primer lugar, la condición de divisibilidad es simétrica en \(m,n\). En efecto, si \(d\mid n^3+1\), entonces la identidad \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] muestra que \(d\mid m^3+1\). Intercambiando \(m,n\), se demuestra el recíproco. Así, podemos suponer que \(m\le n\) e incluir después los pares con las componentes intercambiadas.
Caso 1: \(m=1\). Tenemos \(n\ge2\), y la condición equivalente \(mn-1\mid m^3+1\) se convierte en \[ n-1\mid2. \] Por tanto, \(n=2\) o \(n=3\).
Caso 2: \(m=2\). Ahora \(n\ge2\), y \[ 2n-1\mid9. \] Como \(2n-1\ge3\), es igual a \(3\) o a \(9\). Así, \(n=2\) o \(n=5\).
Caso 3: \(m\ge3\). Sea \[ q=\frac{m^3+1}{mn-1}, \] que es un entero positivo. Reduciendo \(q(mn-1)=m^3+1\) módulo \(m\), obtenemos \[ q\equiv-1\pmod m. \] Además, como \(n\ge m\), \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] Por tanto, \(1\le q\le m\), por lo que la congruencia obliga a que \(q=m-1\). Por consiguiente, \[ (m-1)(mn-1)=m^3+1, \] lo que se simplifica a \[ (m-1)n=m^2+1=(m-1)(m+1)+2. \] Así, \(m-1\mid2\). Como \(m\ge3\), obtenemos \(m=3\), y entonces \(n=5\).
Hemos encontrado, por tanto, exactamente los candidatos \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] con \(m\le n\). Sus cocientes originales son, respectivamente, \[ 9,\quad14,\quad3,\quad14,\quad9, \] por lo que los cinco cumplen la condición. Por la simetría demostrada, los pares con las componentes intercambiadas también la cumplen. Estos dan precisamente los nueve pares indicados anteriormente.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1994 · 问题 4
求所有正整数有序对 \((m, n)\)，使得 \[ \frac{n^3+1}{mn-1} \] 为整数。
题目译自官方英文原文。 官方试卷 (PDF)
答案
这些有序对为 \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
解答
有序对 \((1,1)\) 应排除，因为此时分母为零。对于其余每个有序对，记 \(d=mn-1>0\)。
首先，整除条件关于 \(m,n\) 对称。事实上，若 \(d\mid n^3+1\)，则由恒等式 \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] 可知 \(d\mid m^3+1\)。交换 \(m,n\) 即可证明逆命题。因此，不妨设 \(m\le n\)，最后再加入交换顺序所得的有序对。
情形 1：\(m=1\)。 此时 \(n\ge2\)，而等价条件 \(mn-1\mid m^3+1\) 化为 \[ n-1\mid2. \] 故 \(n=2\) 或 \(n=3\)。
情形 2：\(m=2\)。 此时 \(n\ge2\)，且 \[ 2n-1\mid9. \] 由于 \(2n-1\ge3\)，它等于 \(3\) 或 \(9\)。因此 \(n=2\) 或 \(n=5\)。
情形 3：\(m\ge3\)。 设 \[ q=\frac{m^3+1}{mn-1}, \] 则它是正整数。将 \(q(mn-1)=m^3+1\) 两边模 \(m\) 化简，得 \[ q\equiv-1\pmod m. \] 又因为 \(n\ge m\)，所以 \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] 因此 \(1\le q\le m\)，由上述同余式必有 \(q=m-1\)。于是 \[ (m-1)(mn-1)=m^3+1, \] 化简得 \[ (m-1)n=m^2+1=(m-1)(m+1)+2. \] 因此 \(m-1\mid2\)。由于 \(m\ge3\)，可得 \(m=3\)，进而 \(n=5\)。
因此，在 \(m\le n\) 的条件下，我们找到的全部候选有序对恰为： \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] 将它们代入原式，所得的商依次为 \[ 9,\quad14,\quad3,\quad14,\quad9, \] 故这五个有序对均符合要求。由已证明的对称性，交换它们的顺序所得的有序对也符合要求。这些恰好给出答案中列出的九个有序对。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1994 · Задача 4
Найдите все упорядоченные пары \((m, n)\) положительных целых чисел, для которых \[ \frac{n^3+1}{mn-1} \] является целым числом.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
Искомые упорядоченные пары: \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
Решение
Пара \((1,1)\) исключается, поскольку знаменатель равен нулю. Для любой другой пары положим \(d=mn-1>0\).
Прежде всего, условие делимости симметрично относительно \(m,n\). Действительно, если \(d\mid n^3+1\), то из тождества \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] следует, что \(d\mid m^3+1\). Меняя местами \(m,n\), получаем обратное утверждение. Таким образом, можно считать, что \(m\le n\), а затем добавить пары с переставленными координатами.
Случай 1: \(m=1\). Имеем \(n\ge2\), а равносильное условие \(mn-1\mid m^3+1\) принимает вид \[ n-1\mid2. \] Следовательно, \(n=2\) или \(n=3\).
Случай 2: \(m=2\). Теперь \(n\ge2\) и \[ 2n-1\mid9. \] Поскольку \(2n-1\ge3\), это число равно \(3\) или \(9\). Таким образом, \(n=2\) или \(n=5\).
Случай 3: \(m\ge3\). Пусть \[ q=\frac{m^3+1}{mn-1}, \] причём это положительное целое число. Рассматривая равенство \(q(mn-1)=m^3+1\) по модулю \(m\), получаем \[ q\equiv-1\pmod m. \] Кроме того, поскольку \(n\ge m\), \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] Следовательно, \(1\le q\le m\), поэтому из сравнения следует \(q=m-1\). Значит, \[ (m-1)(mn-1)=m^3+1, \] что после упрощения даёт \[ (m-1)n=m^2+1=(m-1)(m+1)+2. \] Таким образом, \(m-1\mid2\). Поскольку \(m\ge3\), получаем \(m=3\), а затем \(n=5\).
Итак, мы нашли в точности следующие возможные пары: \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] при \(m\le n\). Значения исходной дроби для них соответственно равны \[ 9,\quad14,\quad3,\quad14,\quad9, \] поэтому все пять пар подходят. В силу доказанной симметрии пары с переставленными координатами также подходят. Они дают в точности девять пар, указанных выше.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1994 · المسألة 4
أوجد جميع الأزواج المرتبة \((m, n)\) من الأعداد الصحيحة الموجبة بحيث يكون \[ \frac{n^3+1}{mn-1} \] عددًا صحيحًا.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
الأزواج المرتبة هي \[ \boxed{(1,2),(1,3),(2,1),(2,2),(2,5),(3,1),(3,5),(5,2),(5,3).} \]
الحل
يُستبعد الزوج \((1,1)\) لأن المقام يساوي صفرًا. ولكل زوج آخر، نكتب \(d=mn-1>0\).
أولًا، شرط القسمة متناظر في \(m,n\). بالفعل، إذا كان \(d\mid n^3+1\)، فإن المتطابقة \[ m^3(n^3+1)-(m^3+1) =(mn-1)(m^2n^2+mn+1) \] تبين أن \(d\mid m^3+1\). وبتبادل \(m,n\) يثبت العكس. لذا يمكننا افتراض \(m\le n\)، ثم إضافة الأزواج الناتجة عن عكس الترتيب لاحقًا.
الحالة 1: \(m=1\). لدينا \(n\ge2\)، ويصبح الشرط المكافئ \(mn-1\mid m^3+1\) هو \[ n-1\mid2. \] ومن ثم \(n=2\) أو \(n=3\).
الحالة 2: \(m=2\). الآن \(n\ge2\)، و \[ 2n-1\mid9. \] وبما أن \(2n-1\ge3\)، فإنه يساوي \(3\) أو \(9\). إذن \(n=2\) أو \(n=5\).
الحالة 3: \(m\ge3\). ليكن \[ q=\frac{m^3+1}{mn-1}, \] وهو عدد صحيح موجب. بأخذ \(q(mn-1)=m^3+1\) بترديد \(m\)، نحصل على \[ q\equiv-1\pmod m. \] وأيضًا، بما أن \(n\ge m\)، فإن \[ q\le\frac{m^3+1}{m^2-1} =m+\frac1{m-1}<m+1. \] لذلك \(1\le q\le m\)، ومن ثم يقتضي التطابق أن \(q=m-1\). وبالتالي، \[ (m-1)(mn-1)=m^3+1, \] وبالتبسيط نحصل على \[ (m-1)n=m^2+1=(m-1)(m+1)+2. \] إذن \(m-1\mid2\). وبما أن \(m\ge3\)، نحصل على \(m=3\)، ثم \(n=5\).
وهكذا وجدنا أن الأزواج المرشحة هي بالضبط \[ (1,2),\quad(1,3),\quad(2,2),\quad(2,5),\quad(3,5) \] مع \(m\le n\). وقيم الكسر الأصلي الموافقة لها هي، على الترتيب، \[ 9,\quad14,\quad3,\quad14,\quad9, \] لذا فإن الأزواج الخمسة جميعها تحقق المطلوب. وبحسب التناظر الذي أثبتناه، فإن الأزواج الناتجة عن عكس ترتيبها تحقق المطلوب أيضًا. وهذه تعطي بالضبط الأزواج التسعة المذكورة أعلاه.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).