Простая (но олимпиадня!) задача с простыми числами

[vivaldi]

Доказать, что существует бесконечно много натуральных чисел, не представимых в виде

а) $p(q-r)$

б) $p^q-r$

(p, q, r - простые числа)

[Bulinator]

Пусть $p,q,r\neq 2$
Тогда Ваши выражения четные

[vivaldi]

Bulinator в сообщении #507730 писал(а):

Пусть $p,q,r\neq 2$
Тогда Ваши выражения четные

Что значит "пусть"?

Если число n не представимо в виде p(q-r), то оно не представимо ни при каких простых p, q, r.

[Bulinator]

vivaldi в сообщении #507734 писал(а):

Если число n не представимо в виде p(q-r), то оно не представимо ни при каких простых p, q, r.

Я в том смысле, что нечетные числа так не представить. Нужно показать, что среди нечетных есть бесконечное число таких, которые не представляются в виде
$p(q-2)$
Например $7p', p'\geq 7$

[vivaldi]

Bulinator в сообщении #507736 писал(а):

vivaldi в сообщении #507734 писал(а):

Если число n не представимо в виде p(q-r), то оно не представимо ни при каких простых p, q, r.

Я в том смысле, что нечетные числа так не представить. Нужно показать, что среди нечетных есть бесконечное число таких, которые не представляются в виде
$p(q-2)$
Например $7p'$

Что у Вас обозначает $p'$?

[Bulinator]

Какое-то простое число. Возьмите любое число вида $7p'$. Оно не представляется в Вашем виде.

-- Пт ноя 25, 2011 12:40:12 --

Сорри, туплю. Недооценил задачу.

[vivaldi]

Bulinator в сообщении #507743 писал(а):

Какое-то простое число. Возьмите любое число вида $7p'$. Оно не представляется в Вашем виде.

Не верно.

Контрпример:
14=7(5-3)

-- 25.11.2011, 12:49 --

Bulinator в сообщении #507743 писал(а):

Сорри, туплю. Недооценил задачу.

(Оффтоп)

Вы в неплохой компании.
Один мой знакомый кандидат наук (правда химических) эту задачу тоже недооценил.

[worm2]

Всё правильно, подходят числа вида $7p$, где $p$ — такое нечётное простое, что $p+2$ — составное. Очевидно, таковых бесконечно много

[Bulinator]

Все числа типа $p'q'$, где $p',q'$- простые число вида $6k-1$. Можно ли утверждать, что их кол-во бесконечно?

[vivaldi]

worm2 в сообщении #507761 писал(а):

Всё правильно, подходят числа вида $7p$, где $p$ — такое нечётное простое, что $p+2$ — составное. Очевидно, таковых бесконечно много

Да, действительно.

Вот моё решение:

Все степени семёрки (кроме первой) подходят. Действительно, p может быть только 7, но тогда q-r - тоже степень семёрки, а значит даёт остаток 1 при делении на 6. Число (большее 1), дающее остаток 1 при делении на 6, не может быть разностью двух простых, так как одно из этих простых должно быть 2, а другое 3.

Также несложно доказать, что подходят все нечётные степени пятёрки, кроме первой. Док-во аналогично.


Вот попробуйте теперь второй пункт решить. Я его тоже не осилил, а Ксюша смогла.

-- 25.11.2011, 13:19 --

Bulinator в сообщении #507771 писал(а):

Все числа типа $p'q'$, где $p',q'$- простые число вида $6k-1$. Можно ли утверждать, что их кол-во бесконечно?

Только не "минус", а "плюс".
Но это тупиковый путь, ведь придётся доказывать бесконечность множества простых вида $6k+1$.

[worm2]

По б) подходят, вроде бы, числа вида $2^m-3$, где $m$ — нечётное составное. Правда, тут тоже приходится использовать нетривиальный факт, что диофантово уравнение $2^m-p^q=1$ не имеет решений (при указанных ограничениях)...

[nnosipov]

vivaldi в сообщении #507772 писал(а):

Но это тупиковый путь, ведь придётся доказывать бесконечность множества простых вида $6k+1$.

А это вполне возможно элементарными средствами, между прочим.

[vivaldi]

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

vivaldi в сообщении #507772 писал(а):

Но это тупиковый путь, ведь придётся доказывать бесконечность множества простых вида $6k+1$.

А это вполне возможно элементарными средствами, между прочим.

Так точно, уже знаю, что можно. Но стоит ли правой рукой левое ухо чесать. Ведь сама задача намного проще, нежели это доказательство.

Меня больше интересует, кто, кроме Ксюши, справится со вторым пунктом

-- 25.11.2011, 13:46 --

worm2 в сообщении #507778 писал(а):

По б) подходят, вроде бы, числа вида $2^m-3$, где $m$ — нечётное составное. Правда, тут тоже приходится использовать нетривиальный факт, что диофантово уравнение $2^m-p^q=1$ не имеет решений (при указанных ограничениях)...

Вот Ксюша без всяких там нетривиальных фактов справилась.

[nnosipov]

worm2 в сообщении #507778 писал(а):

тут тоже приходится использовать нетривиальный факт, что диофантово уравнение $2^m-p^q=1$ не имеет решений

Это довольно очевидный факт, даже в такой редакции: равенство $2^m=a^k+1$, где всё натуральное и $a>1$, $k>1$, невозможно.

[worm2]

Да, действительно. Если $q>2$, то $p^q+1=2^m \Rightarrow p=2^t-1$, но $(2^t-1)^q+1=q2^t+\dots$ делится на $2^t$, но не на $2^{t+1}$, облом.
Если $q=2$, то $2^m-1=2^{ab}-1=(2^{a}-1)(2^{a(b-1)}+\dots)$, 2-я скобка больше первой, поэтому произведение не может быть равно квадрату простого числа.