2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Общая формула для НОД
Сообщение25.07.2016, 12:54 
Прошу совета, как подступиться к решению такой задачи - найти НОД (n+1)! и (n!+1). Теория чисел в университете совсем прошла мимо

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 13:21 
Ну, если совсем уж мимо — прочтите какую-нибудь начальную книгу по теории чисел, коли уж вы знаете её (области математики) название. К примеру, И.М. Виноградов, Основы теории чисел — не пропагандирую, просто она у меня ближе всех лежит и к тому ж точно есть в интернете.

-- 25.07.2016, 20:23 --

Впрочем, можете, как по мне, попытаться и так. Начните с вопроса: как описать множество простых делителей $n!$ одной фразой?

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 13:28 
iifat в сообщении #1140033 писал(а):
Ну, если совсем уж мимо — прочтите какую-нибудь начальную книгу по теории чисел, коли уж вы знаете её (области математики) название. К примеру, И.М. Виноградов, Основы теории чисел — не пропагандирую, просто она у меня ближе всех лежит и к тому ж точно есть в интернете.

-- 25.07.2016, 20:23 --

Впрочем, можете, как по мне, попытаться и так. Начните с вопроса: как описать множество простых делителей $n!$ одной фразой?


С факторизацией n! проблем конечно нет :) А вот второе число? Экспериментальное решение очевидно - n+1, если n+1 - простое и 1 в противном случае

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 13:36 
Аватара пользователя
renegator
Что Вы можете сказать о делимости $n!+1$ на числа $2, 3, ..., n$?

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 13:45 
пианист в сообщении #1140037 писал(а):
renegator
Что Вы можете сказать о делимости $n!+1$ на числа $2, 3, ..., n$?


Мне очевидно только, что это число нечетное

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 14:11 
renegator в сообщении #1140038 писал(а):
это число нечетное

А как с делимостью на 3 (какой будет остаток?). И т.д.
Если теория чисел прошла мимо, то у Вас - проблемы...
Но можно попробовать. Например, так, как Вам советуют. Или:
По поводу непростых $n+1$:
Есть алгоритм Евклида для нахождения НОД: Нод$(a,b)=$ НОД$(a-b,b)=...=$ НОД$(r,b)$, где $r$ - остаток от деления $a$ на $b$ (а можно даже и лишнего повычитать - иногда это удобно, а отрицательные числа ничуть не хуже положительных)

-- 25.07.2016, 15:16 --

renegator в сообщении #1140035 писал(а):
Экспериментальное решение очевидно - n+1, если n+1 - простое

А вот этот замечательный факт, обнаруженный Вами эксрериментально, называется "Теорема Вильсона" - не так прост....

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 14:31 
пианист в сообщении #1140037 писал(а):
Что Вы можете сказать о делимости $n!+1$ на числа $2, 3, ..., n$?

$n!+1=2^a\cdot 3^b\cdot 5^c\cdot.....\cdot p+1,\;\;p\leqslant n,\;[\frac n p]=1$

 
 
 
 Re: Общая формула для НОД
Сообщение25.07.2016, 14:35 
renegator в сообщении #1140035 писал(а):
С факторизацией n! проблем конечно нет
Таки если вы думаете, что эта фраза точно описывает множество делителей факториала, то нет.

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group