Которой задачей была бы эта если бы она пришла на IMO 1,2,3?

[rightways]

Натуральное число $n>1$ таково, что $a^n-a$ делится на $n$ для любого натурального $a\ge2014.$ Докажите, что $НОД(a^n-a,n)>1$ для всех целых $a$

[nnosipov]

Какая IMO? Это вообще не задача. Предлагается воспользоваться элементарными свойствами сравнений по модулю, причём в довольно вычурной обстановке. Искусственно и бессодержательно.

Единственное, что здесь можно прокомментировать: каковы те натуральные $n>1$, для которых имеет место сравнение $a^n \equiv a \pmod{n}$ для любого $a \in \mathbb{Z}$?. Ответ известен: это простые числа и числа Кармайкла (абсолютно псевдопростые числа).

[nnosipov]

А что здесь можно неправильно понять? Дано: $n>1$ таково, что $a^n \equiv a \pmod{n}$ для всех $a \geqslant 2014$. В частности, это верно для $a \in \{2014,2015,\dots,2014+(n-1)\}$. Последнее множество составляет полную систему вычетов по модулю $n$. Отсюда следует, что сравнение $a^n \equiv a \pmod{n}$ верно для любого целого $a$. Значит, $\gcd{(a^n-a,n)}=n$ для любого целого $a$.

К модераторам: отправить в ПР/Р, олимпиадный раздел явно не походит.

Upd: ТС удалил своё сообщение, на которое я отвечал.

[rightways]

спасибо! я просто думал, что эта задача трудная

-- 02.02.2014, 14:49 --

я изменил задачу

-- 02.02.2014, 14:56 --

Натуральное число $n>1$ таково, что $a^n-a$ делится на $n$ для всех целых $a$ для которых $2014^2 \ge a\ge2014.$ Докажите, что $НОД(a^n-a,n)>1$ для всех натуральных $a<2014$

[Cash]

Это уже более похоже на задачу, но трудной она не стала.
Для любого $a \leqslant 2013$ элементарно выписываются сравнения
$2014(a^n-a) \equiv 0 \pmod{n}$
$2015(a^n-a) \equiv 0 \pmod{n}$
откуда и следует требуемое

[rightways]

cash, ya ne ponel rewenie, mojete po podrobnee opulikovat rewenye, u menya chuchut soobrazitelnosti ne hvataet

[Deggial]

rightways, замечание за транслит

[Cash]

Тут все прозрачно. Если Вы не можете понять, то интересно Ваше решение.

-- Ср фев 05, 2014 10:25:51 --

(Оффтоп)

Возникает сильное подозрение, что это задача с какой-то текущей местечковой олимпиады

И еще, когда писал решение, был уверен что в условии было $2014^2 \geqslant a \geqslant2014$
Раз неравенства стали нестрогие, то в моем решении верно только одно сравнение, но и его достаточно.

[rightways]

Мое решение длинное, оно основана на такой лемме:


Если НОД$(a^{n-1}-1,n)=1 $ , то $ (a^{n-1})^p-1 $ не делится на $n$ ни при каком простом $p$

-- 05.02.2014, 16:38 --

задача не была на никакой олимпиаде, там стоит число 2014 чисто из за того, чтоб красиво смотрелось

[Cash]

Ок, поверим
Смотрите:
Числа $2015$ и $2015a$ принадлежат интервалу $(2014;2014^2)$, а значит для них можно записать
$2015^n \equiv 2015 \pmod{n}$
$(2015a)^n \equiv 2015a \pmod{n}$
Откуда следует, что $2015a^n \equiv 2015a \pmod{n}$
Если $\gcd(a^n-a, n)=1$, то $n$ является делителем $2015$ и смотрите пост от nnosipov