2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение01.02.2014, 23:55 
Натуральное число $n>1$ таково, что $a^n-a$ делится на $n$ для любого натурального $a\ge2014.$ Докажите, что $НОД(a^n-a,n)>1$ для всех целых $a$

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение02.02.2014, 08:26 
Какая IMO? Это вообще не задача. Предлагается воспользоваться элементарными свойствами сравнений по модулю, причём в довольно вычурной обстановке. Искусственно и бессодержательно.

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

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение02.02.2014, 11:29 
А что здесь можно неправильно понять? Дано: $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: ТС удалил своё сообщение, на которое я отвечал.

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение02.02.2014, 11:37 
спасибо! :facepalm: я просто думал, что эта задача трудная

-- 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$

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение03.02.2014, 08:39 
Это уже более похоже на задачу, но трудной она не стала.
Для любого $a \leqslant 2013$ элементарно выписываются сравнения
$2014(a^n-a) \equiv 0 \pmod{n}$
$2015(a^n-a) \equiv 0 \pmod{n}$
откуда и следует требуемое

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение04.02.2014, 18:28 
cash, ya ne ponel rewenie, mojete po podrobnee opulikovat rewenye, u menya chuchut soobrazitelnosti ne hvataet

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение04.02.2014, 18:43 
Аватара пользователя
 !  rightways, замечание за транслит

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение05.02.2014, 09:23 
Тут все прозрачно. Если Вы не можете понять, то интересно Ваше решение.

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

(Оффтоп)

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

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

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение05.02.2014, 13:15 
Мое решение длинное, оно основана на такой лемме:


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

-- 05.02.2014, 16:38 --

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

 
 
 
 Re: Которой задачей была бы эта если бы она пришла на IMO 1,2,3?
Сообщение05.02.2014, 15:02 
Ок, поверим :-)
Смотрите:
Числа $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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group