IMO 1964 · Problem 1
(a) Find all positive integers \(n\) for which \(2^n - 1\) is divisible by 7.
(b) Prove that there is no positive integer \(n\) for which \(2^n + 1\) is divisible by 7.
Official text of the problem. Official problem paper (PDF)
Answer
(a) All positive multiples of \(3\): \(n=3,6,9,\ldots\).
(b) No such positive integer exists.
Solution
For any positive integer \(n\), the division algorithm gives \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] Since \(2^3=8\equiv 1\pmod 7\), we have \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] Thus \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) The number \(2^n-1\) is divisible by \(7\) exactly when \(2^n\equiv1\pmod7\). By the three cases above, this holds exactly when \(r=0\), or equivalently when \(3\mid n\). Hence the required integers are precisely the positive multiples of \(3\).
(b) If \(2^n+1\) were divisible by \(7\), then \(2^n\equiv-1\equiv6\pmod7\). But the only possible residues of \(2^n\) modulo \(7\) are \(1,2,4\). Therefore no such positive integer exists.
The solution was checked against John Scholes' IMO solution archive (Kalva).
IMO 1964 · Aufgabe 1
(a) Bestimme alle positiven ganzen Zahlen \(n\), für die \(2^n - 1\) durch 7 teilbar ist.
(b) Beweise, dass es keine positive ganze Zahl \(n\) gibt, für die \(2^n + 1\) durch 7 teilbar ist.
Aufgabentext aus dem offiziellen englischen Text übersetzt. Offizielles Aufgabenblatt (PDF)
Antwort
(a) Alle positiven Vielfachen von \(3\): \(n=3,6,9,\ldots\).
(b) Eine solche positive ganze Zahl existiert nicht.
Lösung
Für jede positive ganze Zahl \(n\) liefert die Division mit Rest \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] Wegen \(2^3=8\equiv 1\pmod 7\) gilt \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] Somit gilt \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) Die Zahl \(2^n-1\) ist genau dann durch \(7\) teilbar, wenn \(2^n\equiv1\pmod7\) gilt. Nach den drei obigen Fällen gilt dies genau dann, wenn \(r=0\) ist, also genau dann, wenn \(3\mid n\) gilt. Die gesuchten ganzen Zahlen sind daher genau die positiven Vielfachen von \(3\).
(b) Wäre \(2^n+1\) durch \(7\) teilbar, so wäre \(2^n\equiv-1\equiv6\pmod7\). Die einzigen möglichen Reste von \(2^n\) modulo \(7\) sind jedoch \(1,2,4\). Daher existiert keine solche positive ganze Zahl.
Die Lösung wurde mit dem IMO-Lösungsarchiv von John Scholes (Kalva) abgeglichen.
IMO 1964 · Soru 1
(a) \(2^n - 1\) sayısının 7 ile bölünebildiği tüm pozitif \(n\) tam sayılarını bulunuz.
(b) \(2^n + 1\) sayısının 7 ile bölünebildiği hiçbir pozitif \(n\) tam sayısının bulunmadığını kanıtlayınız.
Soru metni resmi İngilizce metinden çevrilmiştir. Resmi soru kâğıdı (PDF)
Cevap
(a) \(3\)'ün tüm pozitif katları: \(n=3,6,9,\ldots\).
(b) Böyle bir pozitif tam sayı yoktur.
Çözüm
Her pozitif \(n\) tam sayısı için bölme algoritması gereği \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] \(2^3=8\equiv 1\pmod 7\) olduğundan \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] Dolayısıyla \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) \(2^n-1\) sayısının \(7\) ile bölünebilmesi için gerek ve yeter koşul \(2^n\equiv1\pmod7\) olmasıdır. Yukarıdaki üç duruma göre bu, ancak ve ancak \(r=0\) olduğunda, yani \(3\mid n\) olduğunda sağlanır. O hâlde aranan tam sayılar tam olarak \(3\)'ün pozitif katlarıdır.
(b) \(2^n+1\) sayısı \(7\) ile bölünebilseydi \(2^n\equiv-1\equiv6\pmod7\) olurdu. Oysa \(2^n\) sayısının \(7\) modülündeki olası kalanları yalnızca \(1,2,4\)'tür. Bu nedenle böyle bir pozitif tam sayı yoktur.
Çözüm, John Scholes'un IMO çözüm arşiviyle (Kalva) karşılaştırılarak kontrol edildi.
IMO 1964 · Problema 1
(a) Hallar todos los enteros positivos \(n\) para los cuales \(2^n - 1\) es divisible por 7.
(b) Demostrar que no existe ningún entero positivo \(n\) para el cual \(2^n + 1\) sea divisible por 7.
Enunciado traducido del texto oficial en inglés. Enunciado oficial (PDF)
Respuesta
(a) Todos los múltiplos positivos de \(3\): \(n=3,6,9,\ldots\).
(b) No existe tal entero positivo.
Solución
Para cualquier entero positivo \(n\), el algoritmo de la división da \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] Como \(2^3=8\equiv 1\pmod 7\), tenemos \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] Por tanto, \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) El número \(2^n-1\) es divisible por \(7\) si y solo si \(2^n\equiv1\pmod7\). Por los tres casos anteriores, esto ocurre si y solo si \(r=0\), o, equivalentemente, si \(3\mid n\). Así pues, los enteros buscados son precisamente los múltiplos positivos de \(3\).
(b) Si \(2^n+1\) fuera divisible por \(7\), entonces \(2^n\equiv-1\equiv6\pmod7\). Pero los únicos residuos posibles de \(2^n\) módulo \(7\) son \(1,2,4\). Por lo tanto, no existe tal entero positivo.
La solución se comprobó con el archivo de soluciones de la IMO de John Scholes (Kalva).
IMO 1964 · 问题 1
(a) 求所有使得 \(2^n - 1\) 能被 7 整除的正整数 \(n\)。
(b) 证明：不存在使得 \(2^n + 1\) 能被 7 整除的正整数 \(n\)。
题目译自官方英文原文。 官方试卷 (PDF)
答案
(a) 所有 \(3\) 的正整数倍：\(n=3,6,9,\ldots\)。
(b) 不存在这样的正整数。
解答
对于任意正整数 \(n\)，由带余除法可得 \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] 由于 \(2^3=8\equiv 1\pmod 7\)，有 \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] 因此 \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) 数 \(2^n-1\) 能被 \(7\) 整除，当且仅当 \(2^n\equiv1\pmod7\)。由上述三种情形可知，这当且仅当 \(r=0\) 时成立，等价地，当且仅当 \(3\mid n\) 时成立。因此，所求整数恰为 \(3\) 的所有正整数倍。
(b) 若 \(2^n+1\) 能被 \(7\) 整除，则 \(2^n\equiv-1\equiv6\pmod7\)。然而，\(2^n\) 模 \(7\) 的余数只可能为 \(1,2,4\)。因此，不存在这样的正整数。
解答已与 John Scholes 的 IMO 解答档案（Kalva）核对。
IMO 1964 · Задача 1
(a) Найдите все положительные целые числа \(n\), для которых \(2^n - 1\) делится на 7.
(b) Докажите, что не существует положительного целого числа \(n\), для которого \(2^n + 1\) делится на 7.
Условие переведено с официального английского текста. Официальный текст задач (PDF)
Ответ
(a) Все положительные числа, кратные \(3\): \(n=3,6,9,\ldots\).
(b) Такого положительного целого числа не существует.
Решение
Для любого положительного целого числа \(n\) по теореме о делении с остатком имеем \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] Поскольку \(2^3=8\equiv 1\pmod 7\), получаем \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] Таким образом, \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) Число \(2^n-1\) делится на \(7\) тогда и только тогда, когда \(2^n\equiv1\pmod7\). Согласно трём рассмотренным выше случаям, это выполняется тогда и только тогда, когда \(r=0\), или, что равносильно, когда \(3\mid n\). Следовательно, искомые числа — в точности все положительные числа, кратные \(3\).
(b) Если бы \(2^n+1\) делилось на \(7\), то \(2^n\equiv-1\equiv6\pmod7\). Но единственные возможные остатки числа \(2^n\) по модулю \(7\) — это \(1,2,4\). Поэтому такого положительного целого числа не существует.
Решение проверено по архиву решений IMO Джона Скоулза (Kalva).
IMO 1964 · المسألة 1
(a) أوجد جميع الأعداد الصحيحة الموجبة \(n\) التي يكون فيها \(2^n - 1\) قابلاً للقسمة على 7.
(b) أثبت أنه لا يوجد عدد صحيح موجب \(n\) يكون فيه \(2^n + 1\) قابلاً للقسمة على 7.
نص المسألة مترجم عن النص الإنجليزي الرسمي. ورقة المسائل الرسمية (PDF)
الإجابة
(a) جميع المضاعفات الموجبة للعدد \(3\): \(n=3,6,9,\ldots\).
(b) لا يوجد مثل هذا العدد الصحيح الموجب.
الحل
لكل عدد صحيح موجب \(n\)، تعطينا خوارزمية القسمة \[ n=3q+r,\qquad q\geq 0,\quad r\in\{0,1,2\}. \] بما أن \(2^3=8\equiv 1\pmod 7\)، فإن \[ 2^n=8^q2^r\equiv 2^r\pmod 7. \] ومن ثم \[ 2^n\equiv \begin{cases} 1\pmod 7,&r=0,\\ 2\pmod 7,&r=1,\\ 4\pmod 7,&r=2. \end{cases} \]
(a) يكون العدد \(2^n-1\) قابلاً للقسمة على \(7\) إذا وفقط إذا كان \(2^n\equiv1\pmod7\). وبحسب الحالات الثلاث أعلاه، يتحقق ذلك إذا وفقط إذا كان \(r=0\)، أو، على نحو مكافئ، إذا كان \(3\mid n\). إذن الأعداد الصحيحة المطلوبة هي بالضبط المضاعفات الموجبة للعدد \(3\).
(b) لو كان \(2^n+1\) قابلاً للقسمة على \(7\)، لكان \(2^n\equiv-1\equiv6\pmod7\). لكن البواقي الممكنة الوحيدة للعدد \(2^n\) بترديد \(7\) هي \(1,2,4\). لذلك لا يوجد مثل هذا العدد الصحيح الموجب.
تمت مراجعة الحل بمقارنته بأرشيف حلول IMO لجون سكولز (Kalva).