Имя: Пароль:
IT
 
Факториал, простое число и количество решений
0 Ненавижу 1С
 
гуру
02.09.13
14:31
Конечно или бесконечно число решений уравнения:
(p-1)!+1 = p^n
где
p - простое число, а n - натуральное число.
1 Йохохо
 
02.09.13
14:38
т.е. оценить количество таких пар (p, n) при которых (0)?
2 Ненавижу 1С
 
гуру
02.09.13
14:39
(1) типа того
3 Ненавижу 1С
 
гуру
02.09.13
14:51
Для любого простого p выражение (p-1)!+1 делится на p
4 Барбариска
 
02.09.13
14:53
(3) ну да, теорема Эйлера )
А к чему задача из (0) ?
Просто ностальгия по математике? Или из практического приложения?
5 sda553
 
02.09.13
14:54
(3) Каковы ващи доказательства!
6 Ненавижу 1С
 
гуру
02.09.13
14:55
(4) это не теорема Эйлера
(5) это теорема Вильсона
7 sda553
 
02.09.13
14:58
Тогда из (3) следует бесконечность количества решений
8 Ненавижу 1С
 
гуру
02.09.13
15:00
(7) почему?
9 Ненавижу 1С
 
гуру
02.09.13
15:01
(p-1)! = p^n-1 = (p-1)*(p^(n-1)+ ... + p + 1)
(p-2)! = p^(n-1)+ ... + p + 1
10 sda553
 
02.09.13
15:01
(8) Потому что множество простых чисел бесконечно и мы имеем бесконечное количество p решающих уравнение
11 sda553
 
02.09.13
15:02
при n=1
12 Ненавижу 1С
 
гуру
02.09.13
15:02
(10) то есть для любого p есть решение?
почему тогда его нет для p=7?
13 sda553
 
02.09.13
15:02
что то гоню я, сорри, обедать пора
14 sda553
 
02.09.13
15:03
Я знак равно протрактовал как "делится" почему то
15 Нуф-Нуф
 
02.09.13
15:11
всю ветку не читал. "нах?" уже было?
16 Ненавижу 1С
 
гуру
03.09.13
10:52
Для p=2,3,5 решения очевидны
Рассмотрим p>5

Факт 1.
2 < (p-1)/2 < p-2
значит 2 и (p-1)/2 входят множителями в (p-2)!
то есть (p-2)! делится на 2*(p-1)/2 = p-1 или
(p-2)! = R*(p-1), где R - целое

Факт 2.
для любого целого k>0 (p^k-1) делится на (p-1)
то есть p^k = 1+(p-1)*Q(k), где Q(k) - целое

Рассмотрим тождество из (9)
(p-2)! = p^(n-1)+ ... + p + 1
согласно Факт 1 и Факт 2 можно переписать:
R*(p-1) = (1+(p-1)*Q(n-1))+(1+(p-1)*Q(n-2))+ ... + (1+(p-1)*Q(1)) + 1
R*(p-1) = (1+...+1) + (p-1)*(Q(n-1)+...+Q(1))
(1+...+1) - здесь ровно n единиц, остальные слагаемые делятся на (p-1) значит n=k*(p-1)>=p-1

оценим теперь (p-2)!
(p-2)! > p^(n-1) >= p^(p-2) - противоречие

При p>5 решений нет
Я не хочу быть самым богатым человеком на кладбище. Засыпать с чувством, что за день я сделал какую-нибудь потрясающую вещь — вот что меня интересует. Стив Джобс