1
1

Числа p и q - простые, больше 1000 и разные. Можно ли найти такие натуральные а и b, что ар+bq-простое для любых таких p и q?

задан 31 Мар '12 21:48

изменен 1 Апр '12 11:46

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

Для каждой пары (p, q) свою пару (a, b) или для всех пар (p, q) универсальную пару (a, b) ?

(1 Апр '12 0:04) Андрей Юрьевич

Универсальную.

(1 Апр '12 7:26) Lerman
1

Название "Решить задачу", как и метка "математика" не дают никакой информации о вопросе. Я переметила.

(1 Апр '12 9:17) DocentI

Хорошо, что поменяли название. Еще лучше было упоямнуть в нем простые числа.

(1 Апр '12 13:23) DocentI
10|600 символов нужно символов осталось
2

Продолжу идею @Anatoliy с использованием теоремы Дирихле. (Я ее не знала, спасибо за информацию!)

Рассмотрим остатки от деления всех чисел на 3. Т.е. $%a\equiv a_1(\mod 3)$%, $%b\equiv b_1(\mod 3)$%. Оба числа a, b не могут делиться на 3 (иначе и ap + bq делится на 3). Пусть, например, $%b_1 \ne 0$%.

Будем считать, что $%p\equiv 1(\mod 3)$%, т.е. $%p = 3k + 1, p>1000$%. Это возможно в силу теоремы Дирихле, т.к. 1 и 3 - взаимно просты. Будем считать, что $%q\equiv r(\mod 3)$%.

Подберем остаток r так, чтобы сумма ap + bq делилась на 3. Для этого должно выполняться равенство $%(a_1+b_1 r)\equiv 0(\mod 3)$%, т.е. $%b_1r\equiv -a_1(\mod 3)$%. Последнее равенство всегда имеет решение (т.е. r), так как $%b_1\ne 0$%, а остатки по модулю 3 образуют поле.

Теперь постараемся найти простое число q вида 3k + r, большее 1000. Если $%r\ne 0$%, то r взаимно просто с 3, значит, такие q существуют по теореме Дирихле. Для этих p, q сумма ap + bq будет делиться на 3, т.е. не будет простым числом.

Значит, для выполнения условия задачи следует потребовать, чтобы r = 0, т.е. $%a$% делится на 3.

Ясно, что такое же рассуждение можно провести для любого простого числа d, а не только для 3. Итак, для каждого простого числа d один из коэффициентов a, b не делится на d, а другой - делится. Но число простых делителей (a, b) - конечно. Пришли к противоречию.

ссылка

отвечен 3 Апр '12 22:45

изменен 3 Апр '12 22:46

10|600 символов нужно символов осталось
1

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

Прежде всего, простое число $%q>1000$% можно зафиксировать, и тогда, рассуждая от противного, предположим, что существуют $%a$% и $%b$% из условия задачи. Мы получим, что для любого простого $%p>q$% число $%ap+B$% должно быть простым, где $%B=bq$%.

Проитерируем этот процесс, применяя его к новому простому числу $%ap+B$% вместо $%p$%. Тогда окажется, что число $%a(ap+B)+B=a^2p+(a+1)B$% будет простым. Если теперь подставить это число в формулу, то простым будет $%a(a^2p+(a+1)B)+B=a^3+(a^2+a+1)B$%. В итоге окажутся простыми все числа вида $%a^np+(a^{n-1}+a^{n-2}+\cdots+a+1)B$%, где $%n\in{\mathbb N}$%.

Покажем, что этого быть не может, подбирая такое $%n$%, для которого множитель при $%B$%, равный $%(a^n-1)/(a-1)$%, делится на $%p$%. Число $%a$% у нас зафиксировано, поэтому можно считать простое $%p$% достаточно большим. Тогда число $%a< p$% не будет делиться на $%p$%. Далее можно применить малую теорему Ферма, полагая $%n=p-1$%, а можно просто использовать факт повторяемости остатков при делении на $%p$% для степеней числа $%a$%. В итоге мы найдём натуральное $%n$%, для которого $%a^n-1=(a-1)(a^{n-1}+a^{n-2}+\cdots+a+1)$% делится на $%p$%, откуда сразу ясно, что второй сомножитель делится на $%p$%, что завершает доказательство.

ссылка

отвечен 23 Фев '13 12:20

изменен 3 Мар '13 12:53

10|600 символов нужно символов осталось
0

Не только такой пары, но и вообще какой-либо конечной алгебраической формулы, дающей гарантированно простые числа в настоящий момент неизвестно. Есть некоторые формулы (числа Мерсенна, числа Эйлера, числа Ферма) среди значений которых много простых чисел, но получение простого числа по ним не гарантировано. Думаю, что ваша задача не имеет решения: если бы такие a и b существовали, их бы давно нашли.

ссылка

отвечен 1 Апр '12 16:18

изменен 1 Апр '12 16:18

Конечно, скорее всего так. Но это же не доказательство!

(1 Апр '12 16:26) DocentI

Разумеется, не доказательство.

(1 Апр '12 16:37) Андрей Юрьевич
10|600 символов нужно символов осталось
0

Теорема Дирихле гласит: "Каждая арифметическая прогрессия, первый член и разность которой — натуральные взаимно простые числа, содержит бесконечное число простых чисел." Если рассмотреть арифметическую прогрессию с a1=p и d=q, то такие числа a и b существуют (можно взять a=1).

ссылка

отвечен 2 Апр '12 18:25

Я же специально уточнял условие. Конечно, для конкретных p и q такие a и b можно найти. Но в задаче речь идет об УНИВЕРСАЛЬНОЙ паре (a,b), подходящей для ЛЮБОЙ пары (p,q), правда, при условии p>1000, q>1000, но это уже несущественно.

(2 Апр '12 18:46) Андрей Юрьевич

Дело не в том, что простые числа в последовательности существуют, а в том, чтобы все они были простыми. Кстати, множество, описываемое формулой, не содержит бесконечных арифметических прогрессий.

(2 Апр '12 19:30) DocentI

Но такие числа не сущестуют.

(2 Апр '12 20:34) ASailyan

Скорее всего, так. Но как это доказать?!!

(2 Апр '12 22:36) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×508

задан
31 Мар '12 21:48

показан
1629 раз

обновлен
3 Мар '13 12:53

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru