2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 16:41 
Аватара пользователя


01/12/11

8634
Решая различные (чуть было не написала "попарно различные") олимпиадные задачи по арифметике и теории чисел, я пришла к выводу, что многие из тех задач, "официальное" решение которых подразумевает использование громоздких формул и долгих вычислений, можно решить буквально вмиг, если воспользоваться арифметикой остатков.

Вот простейший пример:
Рассмотрим три последовательных натуральных числа. Доказать, что куб наибольшего из них не может быть суммой кубов двух других.
В "официальном" решении используется формула суммы кубов (или куба суммы, я уже не помню). А ведь по остаткам на 4 всего за полминуты можно решить (и не только для натуральных, а вообще для целых).

И таких примеров - тьма!

Вот и возник у меня вопрос: а пытались ли математики применить этот самый арифмост (сиречь, арифметику остатков) для решения открытых проблем? А вдруг некоторые из этих проблем перестанут быть открытыми, если на них взглянуть под несколько иным углом?

Вот, горю желанием узнать, что думают по данному поводу уважаемые форумчане.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 16:51 
Заслуженный участник


20/12/10
8858
Ktina в сообщении #557054 писал(а):
Решая различные (чуть было не написала "попарно различные") олимпиадные задачи ...
:D

Есть хорошая книжка Степанова "Сравнения", в ней обсуждаются и недетские задачи в том числе.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 16:58 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #557059 писал(а):
Есть хорошая книжка Степанова "Сравнения", в ней обсуждаются и недетские задачи в том числе.

А книжка эта в электронном виде или в бумажном?

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 17:06 
Заслуженный участник


20/12/10
8858
Ktina в сообщении #557065 писал(а):
А книжка эта в электронном виде или в бумажном?
В электронном есть. В колхозной библиотеке это "Stepanov S.A. Sravnenija (Znanie, 1975)(ru)(L)(T)(32s).djvu" Выслал на mail.ru

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 17:07 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #557068 писал(а):
Ktina в сообщении #557065 писал(а):
А книжка эта в электронном виде или в бумажном?
В электронном есть. В колхозной библиотеке это "Stepanov S.A. Sravnenija (Znanie, 1975)(ru)(L)(T)(32s).djvu"

Спасибо, сейчас поищу.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 17:13 
Заслуженный участник


20/12/10
8858
Ktina, вот типичный пример задачки, где сравнения быстро приводят к цели: http://www.artofproblemsolving.com/Foru ... 6&t=473492
Задачка детская, но всё же.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 17:20 
Аватара пользователя


01/12/11

8634
nnosipov в сообщении #557071 писал(а):
Ktina, вот типичный пример задачки, где сравнения быстро приводят к цели: http://www.artofproblemsolving.com/Foru ... 6&t=473492
Задачка детская, но всё же.

(Оффтоп)

Приятно было обнаружить там Ваш ник.

А почему "unsolved", если уже "solved"?

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 18:56 
Заслуженный участник


08/04/08
8557
Ktina в сообщении #557054 писал(а):
Вот и возник у меня вопрос: а пытались ли математики применить этот самый арифмост (сиречь, арифметику остатков) для решения открытых проблем? А вдруг некоторые из этих проблем перестанут быть открытыми, если на них взглянуть под несколько иным углом?
Попытка - не пытка :-) В конце концов локальные дзета-функции строятся из числа решений сравнений по модулю и использовались для доказательства ВТФ. Но тут от уровня фантазии зависит, просто в лоб не проходит. Формализовать уровень фантазии я не смогу.
Вот в Проскурякове я видел хороший пример, когда локальные свойства на глобальные не переносятся: уравнение $(x^2-2)(x^2-3)(x^2-6)=0$ не имеет решений в $\mathbb{Z}$, но имеет решения в каждом $\mathbb{Z}_p$.
Есть в Боревиче-Шафаревиче о том, когда квадратичная форма принимает в полях нулевое значение - достаточно сложная.
В общем, ничего это не значит...

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение06.04.2012, 19:12 
Заслуженный участник


20/12/10
8858

(Оффтоп)

Ktina в сообщении #557073 писал(а):
А почему "unsolved", если уже "solved"?
Помещать в "Proposed & Own Problems" вроде тоже не годится. Вот нет у них раздела "New Problems", поэтому обычно отправляю в "unsolved". По-моему, больше шансов, что посмотрят.


-- Пт апр 06, 2012 23:30:40 --

Sonic86 в сообщении #557118 писал(а):
Вот в Проскурякове я видел хороший пример, когда локальные свойства на глобальные не переносятся: уравнение $(x^2-2)(x^2-3)(x^2-6)=0$ не имеет решений в $\mathbb{Z}$, но имеет решения в каждом $\mathbb{Z}_p$.
Вот ещё один пример: уравнение $x^2-34y^2=-1$ неразрешимо в целых числах, однако сравнение $x^2-34y^2 \equiv -1 \pmod{m}$ имеет решения при любом $m$ (последнее утверждение можно доказать совсем элементарно).

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение08.04.2012, 16:21 


05/09/11
364
Петербург
А разве использовать элементарные свойства сравнений на школьных олимпиадах запрещено? Это же вроде бы даже в егэ разрешается (в С6 может понадобиться).

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение08.04.2012, 16:24 
Заслуженный участник


20/12/10
8858
Doil-byle в сообщении #557998 писал(а):
А разве использовать элементарные свойства сравнений на школьных олимпиадах запрещено?
Конечно, нет. Другое дело, что почти всегда без этого можно обойтись.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение08.04.2012, 20:33 


23/02/12
3159
Doil-byle в сообщении #557998 писал(а):
А разве использовать элементарные свойства сравнений на школьных олимпиадах запрещено? Это же вроде бы даже в егэ разрешается (в С6 может понадобиться).

Другое дело, что их в школе не проходят, поэтому на школьных олимпиадах надо приводить доказательства. Поэтому решение такой задачи на олимпиаде представляет наибольшую сложность.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение09.04.2012, 11:54 


23/02/12
3159
vicvolf в сообщении #558102 писал(а):
Doil-byle в сообщении #557998 писал(а):
А разве использовать элементарные свойства сравнений на школьных олимпиадах запрещено? Это же вроде бы даже в егэ разрешается (в С6 может понадобиться).

Другое дело, что их в школе не проходят, поэтому на школьных олимпиадах надо приводить доказательства. Поэтому решение такой задачи на олимпиаде представляет наибольшую сложность.

Наверно предмет типа "Начала теории чисел" можно было ввести в старших классах школы, как продолжение арифметики, и дать там элементарные свойства сравнений.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение09.04.2012, 21:05 


05/09/11
364
Петербург
В хороших физ-мат школах элементарную теорию чисел (в которую входит теория сравнений) проходят на алгебре. Её изучают на мат. кружках, иногда делают специальные факультативы. А так как почти все олимпиадники учатся в хороших физ-мат школах, (в Питере, например, практически все олимпиадники сосредоточены в четырёх школах: 30, 239, ФТШ, ЮМШ) то и элементарную теорию чисел можно на олимпиадах считать частью школьной программы. На Санкт-Петербургской олимпиаде школьников не стесняются даже давать задачи, для решения которых необходимы знания по основам теории графов. Кстати, и графы я встречал в материалах по егэ - в книжке по подготовке к егэ по информатике.

 Профиль  
                  
 
 Re: Арифметика остатков - незаслуженно обиженная царица ТЧ?
Сообщение09.04.2012, 22:59 


23/02/12
3159
Doil-byle в сообщении #558474 писал(а):
В хороших физ-мат школах элементарную теорию чисел (в которую входит теория сравнений) проходят на алгебре. Её изучают на мат. кружках, иногда делают специальные факультативы. А так как почти все олимпиадники учатся в хороших физ-мат школах, (в Питере, например, практически все олимпиадники сосредоточены в четырёх школах: 30, 239, ФТШ, ЮМШ) то и элементарную теорию чисел можно на олимпиадах считать частью школьной программы.

Это плохо, так как получаются разные начальные условия для участников олимпиады. Надо включать, хотя бы факультативно, во всех школах.
Цитата:
На Санкт-Петербургской олимпиаде школьников не стесняются даже давать задачи, для решения которых необходимы знания по основам теории графов. Кстати, и графы я встречал в материалах по егэ - в книжке по подготовке к егэ по информатике.

В егэ нельзя давать материал, который не проходят во всех школах.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 15 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: seraphimt


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group