Есть равенство a в степени p равно b факториал плюс p, где p простое число, a и b натуральные числа. Найти все тройки a, b, p, при которых равенство верно😂😂😅🤣
Обозначим буквой [imath]x[/imath] выражение [imath]b!+p[/imath]. Тогда мы имеем уравнение [imath]a^p=x[/imath]. В свою очередь, по теореме Вильсона мы знаем, что [imath](p - 1)! \equiv -1 \pmod{p}[/imath]. Отсюда следует:
[math]\begin{aligned} x = b! + p \ &\equiv \ b \cdot (b-1)! - 1 \pmod{p} \\ &\equiv \ -1 \pmod{p} \end{aligned}[/math]
Таким образом, [imath]x[/imath] должно быть также сравнимо с [imath]-1[/imath] по модулю [imath]p[/imath].
Если [imath]a^p = x[/imath] для некоторых [imath]p[/imath], [imath]a[/imath], [imath]b[/imath], то, очевидно, [imath]s =\nu_p(x) = \nu_p(a^p) = p\nu_p(a)[/imath] для любого простого [imath]p[/imath].
Пусть [imath]p_1 < p_2 < \dots < p_k[/imath] --- простые числа, на которые делится [imath]x[/imath]. Тогда из [imath]s=p\nu_p(a)[/imath] следует, что все [imath]\nu_{p_j}(a)[/imath] равны [imath]s/p_j[/imath], а [imath]\nu_p(a)=0[/imath] для всех других простых [imath]p[/imath].
Мы знаем, что [imath]x \equiv -1 \pmod{p}[/imath], поэтому [imath]p \nmid b[/imath], что означает [imath]\nu_p(x) = \nu_p(p) = 1[/imath]. В результате получаем
[math]p = \min \left \{ q \ \Bigg | \ q \text{ --- простое число и } q | x + 1 \right \}[/math]
Итак, мы проверяем [imath]p[/imath] по всем простым [imath]q[/imath] от [imath]2[/imath] до [imath]x+1[/imath]. Если находим простой делитель, то проверяем, равен ли [imath]a^p[/imath] выражению [imath]x[/imath]. Если равенство выполняется, то находим все простые [imath]p_j[/imath], на которые делится [imath]x[/imath], и находим [imath]\nu_{p_j}(a)[/imath]. Если для всех простых [imath]p_j[/imath] выполняется [imath]\nu_{p_j}(a)=s/p_j[/imath], то тройка [imath](a, b, p)[/imath] является допустимой.
Приведу код на Python:
```python
def is_prime(x):
if x < 2:
return False
d = 2
while d * d <= x:
if x % d == 0:
return False
d += 1
return True
def find_smallest_prime_factor(x):
for i in range(2, x + 1):
if x % i == 0:
return i
return -1
def prime_divisors(x):
result = []
p = find_smallest_prime_factor(x)
while p > 0:
result.append(p)
while x % p == 0:
x //= p
p = find_smallest_prime_factor(x)
if x > 1:
result.append(x)
return result
def factorials(x):
result = []
f = 1
for i in range(1, x + 1):
result.append(f)
f *= i
return result
factorials = factorials(200)
for b in range(1, 201):
for p in range(2, 201):
if is_prime(p) and factorials[b - 1] + p <= 200:
x = factorials[b - 1] + p
smallest_p = find_smallest_prime_factor(x + 1)
if smallest_p == p:
a = x ** ((p - 1) // p)
if a ** p == x:
divisors = prime_divisors(x)
s = p // divisors[0]
correct = True
for k in range(1, len(divisors)):
d = divisors[k]
if p // d != s:
correct = False
break
if correct:
print("a = {0}, b = {1}, p = {2}".format(a, b, p))
```
Здесь функция `is_prime(x)` возвращает `True`, если число `x` простое, а функция `find_smallest_prime_factor(x)` возвращает наименьший простой делитель числа `x` (или `-1`, если такового нет).
