Пусть `f(n)` обозначает для всех натуральных `n` наибольший общий делитель `n! + 1` и `(n + 1)!`. Найдите и обоснуйте выражение для вычисления `f(n)` для всех `n`. [изображение]
(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 - простое число.