Наименьший простой множитель/делитель

[Olya]

Помогите решить задачку из GMAT!
Число р принадлежит множеству четных положительных чисел: 2, 4, 6, 8...
Функция h(р) равна произведению всех четных положительных чисел от 2 до р.
Например, h(10)=2*4*6*8*10
Необходимо найти наименьший простой множитель для h(100) + 1!
Ответ в виде промежутка: (1) 2-10, (2) 10-20, (3) 20-30, (4) 30-40 и (5) больше 40

Мое частичное решение
В общем, h(р) = 2 ^ (p/2) * (p/2)!
То есть h(100) = 2^50 * 50!

В статье Гальперина Просто о простых числах нашла, что для числа N = n! + 1 наименьший простой делитель больше n. Но как влияет 2^50 на ответ и как это доказать?

Вообще, важно понять именно ход мыслей!
Заранее спасибо!

[juna]

Если вы имеете в виду, что нужно оценить наименьший простой множитель для $2^{50}\cdot 50!+1$, то используйте утверждение, что $\forall a\in \mathbb N: \text{НОД}(a,a+1)=1$.
Его и нужно доказать.

[Olya]

To Juna
Спасибо за ответ! То, что для n!+1 наименьший простой множитель больше n - я понимаю. Но в моем случае есть еще 2^n перед n! Так вот как эта 2^n влияет на ответ?

Насколько я понимаю, наименьший простой множитель будет больше 2^50 * 50?[/math]

[bot]

Olya писал(а):

Ответ в виде промежутка: (1) 2-10, (2) 10-20, (3) 20-30, (4) 30-40 и (5) больше 40

Ну вот, последовательно смотрите на эти пункты и задавайте себе один и тот же вопрос:
Может ли простое число из указанного промежутка быть делителем числа $2^{50}50! +1$?

Olya писал(а):

В статье Гальперина Просто о простых числах нашла, что для числа N = n! + 1 наименьший простой делитель больше n

А почему это так, не задумывались?

Olya писал(а):

Так вот как эта $2^n$ влияет на ответ?

На ответ или на оценку снизу этого ответа? А Вас об этом спрашивают или Вы хотите усложнить совсем простенькую задачу?

[Olya]

To bot

Спасибо за правильно поставленные вопросы!

Насколько я понимаю, для N = n! + 1, наименьший простой делитель больше n, так как при делении N на любое число, меньшее n, получаем остаток 1. (То есть это частное равно n! / это любое число + 1 / это любое число)

В моем примере 2^50 * 50! + 1. Вы написали, что эта 2^50 влияет на нижнюю границу! В данном случае наименьший простой множитель будет в интервале (50; 2^50 * 50! + 1].

Но если бы нам поставили эту же задачу для 2^51 * 51! + 1, то нижняя граница была бы не 51, а 102? Я не понимаю, почему это так, но заметила эту закономерность: если 2 в четной степени, то нижняя граница для наименьшего простого множителя является число перед факториалом, а если нечетная, то в два раза больше!

Прокомментируйте, пожалуйста, мои размышления! Буду очень благодарна, если порекомендуете какие базовые темы в математике необходимо повторить, чтобы справляться с такими задачками! Было бы здорово, если бы Вы посоветовали и хороших авторов/ книжки / статьи / интернет - источники!

Заранее огромное спасибо!

[bot]

Olya писал(а):

Но если бы нам поставили эту же задачу для 2^51 * 51! + 1, то нижняя граница была бы не 51, а 102? Я не понимаю, почему это так, но заметила эту закономерность: если 2 в четной степени, то нижняя граница для наименьшего простого множителя является число перед факториалом, а если нечетная, то в два раза больше!

Я уже писал - зачем усложнять задачу? Ну подвинули слегка вверх эту нижнюю оценку с 40 до 50, что очень просто и хорошо. Почему Вы думаете, что вычисление этого наименьшего простого - так же просто? Это уже совсем не "такая" задача.
Вот, замеченная Вами закономерность нарушается уже при n=4:
$2^44!+1=5\cdot7\cdot11$
Для $2^{51} 51! + 1$ наименьший простой его делитель будет не меньше 53, а вот насколько он будет превосходить 53 - шут его знает. Задавать такие вопросы гораздо проще, чем отвечать на них.

[worm2]

Оказывается, не сильно намного - 67. Но найти её можно только методом тыка, на компьютере.
А вот, например для $2^{7}7!+1$ наименьший простой делитель --- 167.
Для $2^{25}25!+1$ --- 1227870767.

Добавлено спустя 18 минут 50 секунд:

(входя в раж)
А $2^{259}259!+1$ так вообще простое

[Olya]

To bot

Вопрос был в следующем: почему имеет место такая закономерность?

А закономерность не нарушается при n = 4.

2 * 4 + 1 = 2^2 *2! +1 = 9 НПМ = 3 (что больше числа перед факториалом, то есть 2, но меньше 4)

2 * 4 * 6 + 1 = 2^3 * 3! + 1 = 49 НПМ = 7 (больше 3 и 6)

2 * 4 * 6 * 8 + 1 = 2^4 * 4! + 1 = 385 НПМ = 5 ( больше 4, но меньше 8)

2 * 4 * 6 * 8 * 10 +1 = 2^5 * 5! = 3 841 НПМ = 23 (больше 5 и 10)

2^6 * 6! + 1 = 46 081 НПМ = 7 (больше 6, но меньше 12)

Таким образом, эта закономерность помогает сократить интервал за счет уточнения нижней границы. Сути это не меняет. Просто фраза типа «больше 51» заменяется фразой «больше 102». Мне стало интересно, чем объясняется эта закономерность с четностью / нечетностью!

В общем, на поставленный в теме вопрос мы ответили! Спасибо!

To Juna

В задаче спрашивается не наименьший общий множитель, а наименьший простой делитель для числа 2^50 * 50! + 1.

Всем спасибо!

[juna]

Olya писал(а):

В задаче спрашивается не наименьший общий множитель, а наименьший простой делитель для числа 2^50 * 50! + 1.

Обычно говорят о наибольшем общем делителе. А то, о чем я говорил дает грубую оценку больше $47$.
Замеченная Вами закономерность нарушается при $n=8$. Имеем $2^88!+1=19\cdot 543259$. По-вашему, должно получаться больше 8 и меньше 16.

[maxal]

Разложение на простые:

$$2^{50}50! + 1 = 79\times 179\times $$

$$40243333194650166662539\times $$

$$60172851008118822045702963426274510210057447929035999$$

разбил формулу // нг

[bot]

bot писал(а):

Вот, замеченная Вами закономерность нарушается уже при n=4:
$2^44!+1=5\cdot7\cdot11$

Здесь, разумеется, сбрендил - устамши был и не вник. Проще надо было написать, что не вижу никаких предпосылок для каких-либо предположений в уточнении оценки. Ну это уже другие проделали.