|
Числа p и q - простые, больше 1000 и разные. Можно ли найти такие натуральные а и b, что ар+bq-простое для любых таких p и q? задан 31 Мар '12 21:48 
Lerman |
|
Продолжу идею @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 
DocentI |
|
Решение с использованием теоремы Дирихле об арифметических прогрессиях проходит, но это весьма "неэлементарный" факт, поэтому имеет смысл найти решение, опирающиеся на факты "школьного" уровня. Прежде всего, простое число $%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 
falcao |
|
Не только такой пары, но и вообще какой-либо конечной алгебраической формулы, дающей гарантированно простые числа в настоящий момент неизвестно. Есть некоторые формулы (числа Мерсенна, числа Эйлера, числа Ферма) среди значений которых много простых чисел, но получение простого числа по ним не гарантировано. Думаю, что ваша задача не имеет решения: если бы такие a и b существовали, их бы давно нашли. отвечен 1 Апр '12 16:18 
Андрей Юрьевич Конечно, скорее всего так. Но это же не доказательство!
(1 Апр '12 16:26)
DocentI
Разумеется, не доказательство.
(1 Апр '12 16:37)
Андрей Юрьевич
|
|
Теорема Дирихле гласит: "Каждая арифметическая прогрессия, первый член и разность которой — натуральные взаимно простые числа, содержит бесконечное число простых чисел." Если рассмотреть арифметическую прогрессию с a1=p и d=q, то такие числа a и b существуют (можно взять a=1). отвечен 2 Апр '12 18:25 
Anatoliy Я же специально уточнял условие. Конечно, для конкретных 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
|
Для каждой пары (p, q) свою пару (a, b) или для всех пар (p, q) универсальную пару (a, b) ?
Универсальную.
Название "Решить задачу", как и метка "математика" не дают никакой информации о вопросе. Я переметила.
Хорошо, что поменяли название. Еще лучше было упоямнуть в нем простые числа.