Элементарная задача по теории чисел

[Sonic86]

Пусть f(x) - многочлен степени большей, либо равной 1, принимающий только простые значения на множестве простых чисел. Доказать, что такого многочлена не существует.
Обязательная просьба: использовать в доказательстве математику не сильнее 11 класса, так как эта задача - со школьной олимпиады.

[TOTAL]

$$f(x)=x$$

[ИСН]

Убивал бы во-первых об стену тех, кто ставит такие ограничения. Я знаю класс сложности "циркулем и линейкой", знаю класс "NP", ну и ещё несколько - а теперь оказывается, есть ещё какой-то "11 класс".
Во-вторых, такой многочлен существует: f(x)=x.

Добавлено спустя 35 секунд:

Опередили. Great minds think alike.

[TOTAL]

ИСН писал(а):

Опередили. Great minds think alike.

Не совсем одинаково. Бить об стену я не догадался.

[Руст]

Более общее утверждение здесь уже обсуждали. Только для доказательства так или иначе приходится использовать бесконечность простых чисел в арифметических прогрессиях.

[arqady]

ИСН писал(а):

Убивал бы во-первых об стену тех, кто ставит такие ограничения.

Не согласен с Вами! В конце концов, вся математика - это прихоть человечества. Пусть каждый развлекается как хочет и как может. А мы ( те же человеки ) оценим, если сможем. В этом процесе, имхо, весь кайф.

[Sonic86]

Пусть $n$ - натуральное число, $p$ - простое, $q$ - произвольный делитель $(n+1)^p-n^p$. Доказать, что $q-1$ делится на $p$.
Желательно доказать только с помощью математики 11 класса.

[Sonic86]

Я видимо неправильно выразился. То что $f(x)=x$ я уже понял. А насчет замечания Руста - я в шоке: задачу дали на олимпиаде в 11 классе! А про прогрессии я тоже знаю. В общем - спасибо.

[maxal]

Sonic86, не плодите похожите темы. Пишите в одной!

[RIP]

Sonic86 писал(а):

Пусть $n$ - натуральное число, $p$ - простое, $q$ - произвольный делитель $(n+1)^p-n^p$. Доказать, что $q-1$ делится на $p$.

Приводимое решение можно, конечно, переделать под школьное, но мне лень. Очевидно, можно считать, что $q$ простое. Понятно, что $q\nmid n$. Пусть $an\equiv1\pmod q$, тогда $(a+1)^p\equiv1\pmod q$. В частности, $a+1$ не делится на $q$. Если $d$ - показатель числа $a+1$ по модулю $q$ (т.е. наименьшее натуральное $d$ с условием $(a+1)^d\equiv1\pmod q$), то $d|p$, т.е. $d=1$ либо $d=p$. Первый случай исключается, т.к. $a$ не делится на $q$, поэтому $d=p$. Поскольку по малой теореме Ферма, $d|q-1$, то всё доказано.

Добавлено спустя 2 минуты 33 секунды:

Sonic86 писал(а):

То что $f(x)=x$ я уже понял.

Если к первой задаче добавить условие $f(x)\ne x$, то получится очень хорошая задачка, которую непонятно как решать школьными методами.

[Sonic86]

RIP! Спасибо! Я Вас люблю! И Руста тоже.
Кстати, можно обобщить это утверждение: разность любых $p$-ых степеней, взаимно простых с делителями уменьшаемого и вычистаемого, разлагается на простые множители вида $kp+1$. И тогда подставляя вместо этих чисел многочлены, удовлетворяющие условию взаимной простоты мы получаем много утверждений подобного вида!
Странно, как это я сам не допер!

[Коровьев]

Sonic86 писал(а):

Пусть $n$ - натуральное число, $p$ - простое, $q$ - произвольный делитель $(n+1)^p-n^p$. Доказать, что $q-1$ делится на $p$.
Желательно доказать только с помощью математики 11 класса.

Сие невозможно. Ибо существующие доказательства в теории чисел требуют понятия первообразного корня и теорем, связанных с ним.

[RIP]

Коровьев писал(а):

Sonic86 писал(а):

Пусть $n$ - натуральное число, $p$ - простое, $q$ - произвольный делитель $(n+1)^p-n^p$. Доказать, что $q-1$ делится на $p$.
Желательно доказать только с помощью математики 11 класса.

Сие невозможно. Ибо существующие доказательства в теории чисел требуют понятия первообразного корня и теорем, связанных с ним.

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

[Коровьев]

RIP писал(а):

Коровьев писал(а):

Sonic86 писал(а):

Пусть $n$ - натуральное число, $p$ - простое, $q$ - произвольный делитель $(n+1)^p-n^p$. Доказать, что $q-1$ делится на $p$.
Желательно доказать только с помощью математики 11 класса.

Сие невозможно. Ибо существующие доказательства в теории чисел требуют понятия первообразного корня и теорем, связанных с ним.

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

Ну, тогда и основная задачка темы доступна школьником. Нужно только знать формулировку теоремы Дирихле о простых числах в арифметической прогрессии.
МТФ и опирается как раз на существование первообразных корней по простому модулю.
Впрочем, можно попробовать доказать МТФ и школьными методами. Вряд ли Ферма использовал современные понятия в теории чисел.

[bot]

Коровьев писал(а):

Впрочем, можно попробовать доказать МТФ и школьными методами.

Можно - принцип Дирихле.
Когда-то в школе сам доказывал.