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

[Sonic86]

Хм... А я вот только классические доказательства знаю
Еще 4 задачи:
1. Докажите, что дробь $m/n$ представима в виде $(2^{a_s}+...+2^{a_0})/(2^{b_r}+...+2^{b_0})$, где все $a_s ,...,a_0 ,b_r ,...,b_0 $ - различные натуральные числа, $\leftrightarrow m+n$ - нечетна.
2*. Найти (методами 11 класса ), все многочлены $P(n)$, для которых $2^n-1$ делится на $P(n)$
(Лично я считаю множество всех простых Мерсенна бесконечным, и отсюда прихожу к противоречию, а в итоге $P(n)=1$, а бедные дети... )
3. Дано число $N$, не делящее ся на 81, представимое в виде суммы трех квадратов, делящихся на 3. Докажите, что $N$ представимо в виде суммы трех чисел, не делящихся на 3.
4. Дано число $N$, представимое в виде суммы трех квадратов, делящихся на 3. Докажите, что $N$ представимо в виде суммы трех чисел, не делящихся на 3.

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

Простите, модератор, я не нашел свою тему "Сравнение", я ее здесь запишу.
0**. Так называемая теорема Вольстенхольма. Обозначим $C(n)=C^n _{2n}$, множество простых чисел $P$. Доказать, что для нечетных $n$ выполняется

$$C(n)=2(mod n^3) \leftrightarrow n \in P, n>3$$

При этом легко доказать, что $C(p)=2(mod p^3) \leftarrow p \in P, p>3$. Утверждение для $n=p^m$ сводится к утверждению, что для любого простого $p$ неверно $C(p)=2(mod p^4)$. Кроме того, найдено, что $C(29*937)=2(mod 29*937)$ и $C(13)=2(mod 3^2)$.
Я пользовался только обычными методами. Есть ли какой-то специальный метод для доказательства подобных сравнений? Подскажите.

Добавлено спустя 17 минут 21 секунду:

Еще 2 вопроса:
6. Известно ли асимптотическое значение среднего значения функции $E(a,b)$ по 2-у аргументу? $E(a,b)$ - число шагов алгоритма Евклида над числами $a,b, a>b$ до получения НОД$(a,b)$. Среднее значение $E(a,b)$ по $b$ будет $(E(a,1)+...E(a,a-1))/a$. Известна оценка $E(a,b)< log(a)/log(\phi)$ при $a \rightarrow \infty$, но $\phi=1,61$, а грубые численные оценки дают 1,25 для аргумента логарифма в знаменателе.
7. Можно ли оценить число разложений натурального $A$ в виде $A=(mn+1)/(m+n)$?

[worm2]

Sonic86 писал(а):

7. Можно ли оценить число разложений натурального $A$ в виде $A=(mn+1)/(m+n)$?

Сводится к факторизации некоторого другого числа.
(A+1)(A-1)=(m-A)(n-A), переобозначаем неизвестные через x = m-A, y = n-A, раскладываем на множители числа (A+1) и (A-1), комбинируя разложения, получаем всевозможные разложения (A+1)(A-1) на 2 сомножителя x и y.

[Коровьев]

bot писал(а):

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

О, я в школе много тоже чего напонадоказывал.

Жаль, что щас из-за склероза всё забыл.

А вообще-то, впервые представил элементарное доказательство проблемы Дирихле о простых числах в арифметической пргрессии датчанин Сельберг только в 1950(!) году. Полтораста лет она не давалась математикам. Правда, я с ним, доказательством, не знаком.
Конечно, элементарное - подразумевает только то, что док-во без элементов высшей математики, не более.

[RIP]

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

Конечно, элементарное - подразумевает только то, что док-во без элементов высшей математики, не более.

Нет, "элементарное" означает, что не используется теория функций комплексного переменного. А матан там используется вовсю.

P.S. Никогда не встречал, чтобы МТФ доказывали с помощью первообразного корня. Наоборот, существование первообразного корня обычно доказывают, основываясь на МТФ.

Кроме того, Сельберг дал элементарное доказательство асимптотического закона распределения простых чисел, а доказательство теоремы Дирихле, которое дал сам Дирихле, было элементарным в указанном выше смысле (правда, первоначальное доказательстово было неполным).

[Kid Kool]

Sonic86 писал(а):

1. Докажите, что дробь $m/n$ представима в виде $(2^{a_s}+...+2^{a_0})/(2^{b_r}+...+2^{b_0})$, где все $a_s ,...,a_0 ,b_r ,...,b_0 $ - различные натуральные числа, $\leftrightarrow m+n$ - нечетна.

$m/n$ должна быть несократимой.

Sonic86 писал(а):

2*. Найти (методами 11 класса Smile ), все многочлены $P(n)$, для которых $2^n-1$ делится на $P(n)$
(Лично я считаю множество всех простых Мерсенна бесконечным, и отсюда прихожу к противоречию, а в итоге $P(n)=1$, а бедные дети... Smile )

Если простое p делит P(n), то p делит P(n+p). Поэтому $2^n-1$ делится на p и $2^{n+p}-1$ делится на p. Откуда (взяв разность) $2^n(2^p-1)$ делится на p. Т.к. p нечетно, то p делит $2^p-1$, но по малой теореме Ферма p делит $2^p-2$. Откуда p=1, противоречие. Значит, P(n) простых делителей не имеет, т.е. P(n) = 1 или -1.

Sonic86 писал(а):

3. Дано число $N$, не делящее ся на 81, представимое в виде суммы трех квадратов, делящихся на 3. Докажите, что $N$ представимо в виде суммы трех чисел, не делящихся на 3.
4. Дано число $N$, представимое в виде суммы трех квадратов, делящихся на 3. Докажите, что $N$ представимо в виде суммы трех чисел, не делящихся на 3.

N = 1+1+(N-2)

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

Sonic86 писал(а):

1. Докажите, что дробь $m/n$ представима в виде $(2^{a_s}+...+2^{a_0})/(2^{b_r}+...+2^{b_0})$, где все $a_s ,...,a_0 ,b_r ,...,b_0 $ - различные натуральные числа, $\leftrightarrow m+n$ - нечетна.

В такой формулировке задача неверна, нужно потребовать, чтобы $m/n$ была несократима.
В прямую сторону очевидно. Если m+n четно, что каждое из m, n нечетно, а тогда на какое бы число d их ни домножали, всегда минимум из $a_s ,...,a_0$ будет равен минимуму из $b_r ,...,b_0$.
Обратно. Пусть m+n нечетно. Есть идея, что нужно уможать m, n на числа вида $2^k+1$. Например, если k-номер наименьшего бита, равного 1 у m и n, то после домножения m и n на $2^k+1$ у получившихся чисел номер минимального совпадающего единичного бита увеличится.

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

Sonic86 писал(а):

0**. Так называемая теорема Вольстенхольма. Обозначим $C(n)=C^n _{2n}$, множество простых чисел $P$. Доказать, что для нечетных $n$ выполняется

$$C(n)=2(mod n^3) \leftrightarrow n \in P, n>3$$

В обратную сторону. Пусть $P(x) = (x-1)...(x-(p-1))$. Нужно доказать, что $P(2p) = P(p) (mod p^3)$.

$P(x)$ = $(p-1)! + x(p-1)!\left(\sum\limits_{k=1}^{p-1}\frac{1}{k}\right) + x^2(p-1)!\left(\sum\limits_{1 \leq k<l \leq {p-1}}\frac{1}{kl}\right) + x^3Q(x)$/.

3-яя скобка делится на p, потому что равна $\frac{1}{2}\left({\left(\sum\limits_{k=1}^{p-1}\frac{1}{k}\right)}^2 - \left(\sum\limits_{k=1}^{p-1}\frac{1}{k^2}\right)\right)$, что по модулю p равно 0 (1, ..., $\frac{1}{p-1}$ - это как-то переставленные 1, ..., p-1 по модулю p).

2-ая скобка делится на $p^2$, поскольку:

$\sum\limits_{k=1}^{p-1}\frac{1}{k}$ = $\sum\limits_{k=1}^{\frac{p-1}{2}}\left(\frac{1}{k} + \frac{1}{p-k}\right)$ = $p\sum\limits_{k=1}^{\frac{p-1}{2}}\frac{1}{k(p-k)}$ = $p\sum\limits_{k=1}^{\frac{p-1}{2}}\left(-\frac{1}{k^2} + p\frac{1}{k^2(p-k)}\right)$ = $-p\sum\limits_{k=1}^{\frac{p-1}{2}}\frac{1}{k^2}$ (mod $p^2$). А $\sum\limits_{k=1}^{\frac{p-1}{2}}\frac{1}{k^2}$ = $\frac{\frac{p-1}{2}\frac{p+1}{2}p}{6}$ (mod p), что делится на p при p > 3.

Т.о., при x делящемся на p > 3 P(x) = (p-1)! mod $p^3$, откуда все следует.

[bot]

Sonic86 писал(а):

Хм... А я вот только классические доказательства знаю

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

RIP писал(а):

Никогда не встречал, чтобы МТФ доказывали с помощью первообразного корня.

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

[Sonic86]

Kid Kool писал(а): дробь $m/n$ должна быть несократимой.
Да, действительно, формулировка не очень удачная, но смысл, например, в том, что: $2/3=6/9=(2^1+2^2)/(2^0+2^3)$. А насчет умножения на $2^k+1$ у меня не очень получается.

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

Worm2, спасибо!

Добавлено спустя 45 минут 55 секунд:

Еще одна, очень злая задача
Существует ли натуральное $A$, такое, что все числа вида $n^2+A$ являются составными.

[Kid Kool]

Sonic86 писал(а):

Существует ли натуральное $A$, такое, что все числа вида $n^2+A$ являются составными.

При n=A это число равно A(A+1). Так что A равно разве что 1. Но тогда при n=2 получаем простое число 5.

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

RIP писал(а):

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

Кстати, рассматривая простые делители чисел вида $\frac{a^p-1}{a-1}$ (или используя уже доказанную выше задачу) легко доказать, что существует бесконечно много простых вида pk+1. Тогда отсюда автоматом получается, что |f(1)| = 1. Кроме того, очевидно, что |f(0)| = 1. Может, отсюда уже можно вывести доказательство?

[TOTAL]

Kid Kool писал(а):

Sonic86 писал(а):

Существует ли натуральное $A$, такое, что все числа вида $n^2+A$ являются составными.

При n=A это число равно A(A+1). Так что A равно разве что 1.

Так что A(A+1) составное, как и надо.

[Kid Kool]

TOTAL писал(а):

Так что A(A+1) составное, как и надо.

хе, а я прочитал "не являются составными"...

[Sonic86]

Я задачу про представление в виде трех квадратов решал так:
Пусть $N$ представимо в виде: $N=9x^2+9y^2+9z^2$. Так как $9=2^2+2^2+1^2$? то имеем тождество:

$$9x^2+9y^2+9z^2=(2x+2y-z)^2+(2y+2z-x)^2+(2z+2x-y)^2$$

Более того, имеем:

$$9x^2+9y^2+9z^2=(2x\varepsilon_1 +2y\varepsilon_2 +z\varepsilon_3 )^2+(2y\varepsilon_1 +2z\varepsilon_2 +x\varepsilon_3 )^2+(2z\varepsilon_1 +2x\varepsilon_2 +y\varepsilon_3 )^2$$

Здесь $\varepsilon_1 ,\varepsilon_2 ,\varepsilon_3 $ - 3 единицы, из которых две равны +1, а третья равна -1.
Пусть $N$ не делится на 81. Тогда $x,y,z$ не делятся на 3 одновременно. Тогда следует рассмотреть 3 случая: $x,y,z$ имеют 3, 2 или 1 одинаковых остатков от деления на 3.
1) $x = y = z \neq 0(mod3)$ 2) $x = y \neq z(mod3)$ 3) $x \neq y \neq z \neq x(mod3)$.
В первом случае берем $\varepsilon_3 =1$, во втором $\varepsilon_i = -1$, где $i$ - номер переменной, несравнимой с остальными, а в третьем опять берем $\varepsilon_3 =1$. Тогда в любом случае существует такое преобразование исходного решения, что в новом решении все новые переменные не делятся на 3. Ч. т. д.
В общем случае для $N$ рассуждения только немного усложняются и добавляется индукция.
Если исходные переменные делятся точно на $3^a$, то рассмотренным преобразованием их можно перевести в нобор переменных, которое делятся точно на $3^{a-1}$.
Тогда по индукции искомый набор переменных существует.

[Sonic86]

Для натуральных чисел $m$ и $n$ обозначим через $F(m,n)$ количество вcех связных
клеточных фигур в прямоугольнике c размерами $m$ на $n$. Докажите, что четность
числа $F(m,n)$ совпадает с четностью числа $m(m+1)/2*n(n+1)/2$ .
(Связная клеточная фигура – это такое непустое множество клеток, что из любой клетки
этого множества можно пройти в любую другую клетку этого множества по клеткам
этого множества, переходя каждый раз в соседнюю по стороне клетку.)

Есть ли элементарное доказательство следующих соотношений:
1. Доказать, что если $k,n$ - взаимно просты, то $C^{k}_{n}$ делится на $n$.
2. Доказать, что $C^{k}_{n}+C^{k/2}_{n/2}$ делится на $n$.
3. Доказать, что, если $p=gcd(n,k)$ - простое число, то $C^{k}_{n}+(p-1)C^{k/p}_{n/p}$ делится на $n$.
Доказательства есть, но они хорошо используют теорию групп

[Руст]

Sonic86 писал(а):

Есть ли элементарное доказательство следующих соотношений:
1. Доказать, что если $k,n$ - взаимно просты, то $C^{k}_{n}$ делится на $n$.
2. Доказать, что $C^{k}_{n}+C^{k/2}_{n/2}$ делится на $n$.
3. Доказать, что, если $p=gcd(n,k)$ - простое число, то $C^{k}_{n}+(p-1)C^{k/p}_{n/p}$ делится на $n$.
Доказательства есть, но они хорошо используют теорию групп

Первое тривиальное и следует из $C_n^k=\frac{nC_{n-1}^{k-1}}{k}.$
Второе доказывается чуть посложнее использовав это.
Третье слелует из более хорошей делимости $p^3|C_{ap}^{bp}-C_a^b$ для нечётных простых, для р=2 делимость только на квадрат.

[Kid Kool]

Sonic86 писал(а):

Докажите, что четность
числа $F(m,n)$ совпадает с четностью числа $m(m+1)/2*n(n+1)/2$

Индукция по m+n. Переход делается так.

Допустим, что m четно. Отразим нашу фигуру симметрично относительно прямой, делящей сторону m пополам. Фигуры, не переходящие в себя при таком отражении, разбиваются на пары. Поэтому четность F(m,n) совпадает с четностью количества симметричных фигур, которых было бы $F(\frac m 2, n)$, если бы не условие на связность. А несвязные симметричные фигуры - это те, у которых нижняя часть не задевает центральную полосу (ширины 2), а их $F\left(\frac m 2 - 1, n\right)$. Т.о., четность F(m,n) равна четности $F(\frac m 2, n) - F\left(\frac m 2 - 1, n\right)$, откуда следует формула.

Случай нечетного m разбирается аналогично (там отражаем относительно центральной полосы (ширины 1) и рассматриваем нижнюю часть, включая центральную полосу).

[Sonic86]

Еще 2 несложные, но красивые задачи, для любителей ТФ :
1. Доказать, что уравнение $x^3+y^3+1=z^3$ имеет бесконечно много решений в натуральных числах.
2. Доказать, что уравнение $x^3+y^3+z^3=2$ имеет бесконечно много решений в целых числах.