podumka

Помогите, пожалуйста!

Мне задали на ЗЗМШ две задачи. Как ни я, ни моя учительница не пытались решить их, ничего не получилось. Вот эти задачи:
1. Докажите, что когда n и m — простые числа, больше трёх, то значения выражения n^2-m^2 делится на 24.
2. Найдите все простые числа р, чтобы числа 2р+1 и 4р+1 были тоже простыми. Ответ обоснуйте.
Пожалуйста, помогите мне решить эти задачи!
  • +2
  • 26 декабря 2010, 23:09
  • znaika

Комментарии (11)

RSS свернуть / развернуть
+
+1
Взял из википедии
[текст доступен после регистрации]
Некоторые свойства:
…
Если p > 3 — простое, то p2 − 1 кратно 24 (справедливо также для всех нечётных чисел, не делящихся на 3)

Это можно записать так:

(p1^2-1)/a=24 и (p2^2-1)/b=24, где

a,b – натуральные числа

отсюда:

p1^2-1=24a => p1^2-24a=1
p2^2-1=24b => p2^2-24b=1 =>

=> p1^2-24a= p2^2-24b => p1^2-p2^2=24a-24b=>

=> p1^2-p2^2=24(a-b) – что и требовалось доказать…

Хотя, может я и глупость написал….
avatar

fuelcs

  • 27 декабря 2010, 15:53
+
0
Спасибо, но я уже эту задачу по-другому решил (решил всё-таки!), используя то, что любое простое число можно представить в виде 6а+-1, где а — целое число. Доказательство могу привести, если хотите. А твоё свойство — это задача, но совсем другая, и почему Википедия поместила её в свойства, не знаю. Но так, в принципе, тоже можно.
Так что помогите мне с другой задачей (я знаю, что р может быть только 3).
avatar

znaika

  • 27 декабря 2010, 17:46
  • ↑
+
0
Выкладывай…
avatar

fuelcs

  • 27 декабря 2010, 17:50
  • ↑
+
0
Число р(простое и больше 3) при делении на 6 даёт остачи 1, 2, 3, 4, 5, 0 или -1(если р=5, к примеру, это в нашем случае, ведь а обязательно положительное). Тогда р можно записать в виде:
р=6а;
р=6а+1;
р=6а+2;
р=6а+3;
р=6а+4;
р=6а+5;
р=6а-1.
Очевидно, что в первом, третьем, четвёртом, пятом и шестом случаях число р всегда будет составным, хотя в последнем случае не всегда, только когда р делится на 5, но мы исключаем все случаи, когда р хотя бы при одном а будет составным. Но р — простое. Значит, его можно представить только в виде р=6а+-1.
Вроде так.
avatar

znaika

  • 27 декабря 2010, 18:03
  • ↑
+
0
Мне кажется что это не полное решение;-)
avatar

fuelcs

  • 27 декабря 2010, 20:11
  • ↑
+
0
Это не решение, а доказательство теоремы:
любое простое число можно представить в виде 6а+-1, где а — целое число
Помогите со 2-ой задачей, пожалуйста!
avatar

znaika

  • 27 декабря 2010, 21:42
  • ↑
+
+1
Обозначим A=2p+1 и B=4p+1. Заметим, что B=2A-1 («мастер-равенство»).

Для простых чисел p>3 (что важно!) известно, что p=6n+-1. Соответственно, сделаем допущение, что p>3 и запишем все возможные при этом условии варианты представления A и В через n и исследуем их на «простоту»:

1) А=2(6n+1)+1=3(4n+1)
2) A=2(6n-1)+1=12n-1
3) B=4(6n+1)+1=24n+5
4) B=4(6n-1)+1=3(8n-1)

1) и 4) нас не интересуют, т.к. делятся на три, т.е. не являются простыми. 

2) и 3) поверхностно похожи на простые числа, так что продолжим с ними работу. 

Подставим 2) и 3) в «мастер-равенство».

Получим: 24n+5=24n-3, что невозможно! 

Следовательно, наше допущение, что p>3 — не годится. Остаётся проверить p=2 и p=3, из которых нам подходит только p=3 (A=7, В=13).
avatar

aquila

  • 08 января 2011, 02:32
  • ↑
+
0
Я практически так и решал. Кстати, могу выложить другое решение 1-ой задачи.
Насчёт 2-ой:
Простое число р(если р>3) при делении на 3 может давать остатки 1 или 2. Для числа 2р+1 они равны или остатку от деления (2*1+1)/3=1*3+0, или (2*2+1)/3=1*3+2. Очевидно, что подходит для простых чисел только второй случай. Проверим остатки для 4р+1:
(4*1+1)/3=1*3+2;
(4*2+1)/3=3*3+0.
Остаток от деления есть в первом случае. Но для 2р+1 его нет, значит, 2р+1 делится нацело на 3, что противоречит условию. Тогда простое число во втором случае. Но тогда 4р+1 делится нацело на 3, и снова мы приходим к нестыковке. Остаётся р=2 или р=3. Элементарной подстановкой убеждаемся, что для р возможно лишь единственное значение р=3.
Ответ: 3.
Жаль, что только после отправки нашёл этот способ :(
avatar

znaika

  • 08 января 2011, 12:36
  • ↑
+
0
Между прочим, это не единственные решения 1-ой задачи. Кто может привести ещё, выкладывайте!
avatar

znaika

  • 03 января 2011, 00:49
+
+1
Не зная свойства простых (типа p^2-1 кратно 24) можно пойти простым путем рассуждений в 1-ой задаче. запишем n^2-m^2=(n+m)*(n-m).Так как простые числа >3 всегда нечетные, то обе скобки четные, т.е. mod(2).
Далее, любое простое число (опять же >3) при делении на 3 дает остаток 1 или 2. В случае, когда остатки n и m одинаковые, то разность будет кратна трем — mod(3). А если разные — то сумма.
Та же логика с делимостью на 4. Очевидно, что остатки от деления на 4 любого простого числа 1 или 3. Причем, если они одинаковы, тогда разность будет кратна четырем — mod(4). И наоборот.
Тогда получаем, что оба сомножителя делятся на 2, один из низ на 3, и один (тот же или другой — неважно) — на 4. 2*3*4=24. Произведение кратно 24.
avatar

Mat-i-mat

  • 14 декабря 2011, 16:34
+
0
ЗЫ Видимо вышеуказанное свойство получено тем же путем :)
avatar

Mat-i-mat

  • 14 декабря 2011, 16:35
  • ↑

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.