Выражение для НОД

[wpoms.]

Пусть `f(n)` обозначает для всех натуральных `n` наибольший общий делитель `n! + 1` и `(n + 1)!`. Найдите и обоснуйте выражение для вычисления `f(n)` для всех `n`.

@темы: Теория чисел

Comments

[Trotil]

n! + 1 - делится на простые в диапазоне (n+1)..sqrt (n! + 1)
(n + 1)! - делится на простые из диапазона 1..(n+1)

Следовательно:
НОД = 1, если n!+1 != 0 mod (n+1) и
НОД = n, если n!+1 = 0 mod (n+1).

Осталось выяснить, когда n!+1 = 0 mod (n+1). А это, собственно, теорема Вильсона. Согласно ей, равенство возможно, если n - простое число.