Арифметика остатков - незаслуженно обиженная царица ТЧ?

[Ktina]

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

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

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

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

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

[nnosipov]

Ktina в сообщении #557054 писал(а):

Решая различные (чуть было не написала "попарно различные") олимпиадные задачи ...

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

[Ktina]

nnosipov в сообщении #557059 писал(а):

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

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

[nnosipov]

Ktina в сообщении #557065 писал(а):

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

В электронном есть. В колхозной библиотеке это "Stepanov S.A. Sravnenija (Znanie, 1975)(ru)(L)(T)(32s).djvu" Выслал на mail.ru

[Ktina]

nnosipov в сообщении #557068 писал(а):

Ktina в сообщении #557065 писал(а):

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

В электронном есть. В колхозной библиотеке это "Stepanov S.A. Sravnenija (Znanie, 1975)(ru)(L)(T)(32s).djvu"

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

[nnosipov]

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

[Ktina]

nnosipov в сообщении #557071 писал(а):

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

(Оффтоп)

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

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

[Sonic86]

Ktina в сообщении #557054 писал(а):

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

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

[nnosipov]

(Оффтоп)

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$ (последнее утверждение можно доказать совсем элементарно).

[Doil-byle]

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

[nnosipov]

Doil-byle в сообщении #557998 писал(а):

А разве использовать элементарные свойства сравнений на школьных олимпиадах запрещено?

Конечно, нет. Другое дело, что почти всегда без этого можно обойтись.

[vicvolf]

Doil-byle в сообщении #557998 писал(а):

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

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

[vicvolf]

vicvolf в сообщении #558102 писал(а):

Doil-byle в сообщении #557998 писал(а):

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

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

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

[Doil-byle]

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

[vicvolf]

Doil-byle в сообщении #558474 писал(а):

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

Это плохо, так как получаются разные начальные условия для участников олимпиады. Надо включать, хотя бы факультативно, во всех школах.

Цитата:

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

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