26-я Балканская математическая олимпиада среди юниоров. Босния и Герцеговины, 2022 год

Найти все четверки натуральных чисел $(p, q, a, b)$, где $p$ и $q$ — простые числа и $a > 1$, для которых выполнено равенство $p^a = 1 + 5q^b.$

Комментарий/решение

Ответ: $(p,q,a,b)=(2,3,4,1); (3,2,4,4)$

Очевидно, что одно из чисел $p$ и $q$ четное, а другое нечетное

i) $p=2,q\geq3$

Тогда $2^a=5q^b+1$. $5q^b+1\equiv 1 (mod 5)$, $2^a\equiv 2,4,3,1 (mod 5) \Longrightarrow 4\vert a$. Тогда получим, что $5\times q^b=2^a-1\vdots3 \Longrightarrow q=3$. Если $b\geq2$, то $2^a\equiv 1 (mod 9)$. Но $ord_{9} 2=6$. Значит $a=6k$ для $k\in{Z}$. Это означает, что $2^{6k}=5\times3^b+1$. Заметим, что $(2^6)^l\equiv1(mod 7)$ по малой теореме Ферма. Следовательно, $5\times3^b$ делится на 7 что невозможно

Значит $b=1$ и $a=4$ В этом случае ответ $p=2$, $q=3$, $a=4$, $b=1$

ii)$q=2, p\geq3$

$p^a=1+5\times2^b$. Допустим, что $a$ нечетное. Тогда:

$$(p+1)(p^{a-1}+\dots+1)=5\times2^b$$

Поскольку число $a$ нечетно, то число $(p^{a-1}+\dots+1)$ тоже. Следовательно оно равно 5. Но это очевидно невозможно поскольку $a\geq3, p\geq 3$.

Значит $2\vert a$. Заметим, что $5\times2^b+1\equiv 2,0 (mod 3)$. Мы уже знаем что $a$ нечетно, значит $p=3$. Теперь уравнение имеет вид $3^a=5\times2^b+1$. Рассмотрим (mod 5). $3^k\equiv 3,4,2,1 (mod 5)\Longrightarrow 4\vert a$. Тогда $(3^{\frac{a}{2}}+1)(3^{\frac{a}{2}}-1)=5\times2^b$. Заметим что $v_2(3^{\frac{a}{2}}+1)=1$. Значит $3^{\frac a2}+1\in \{2,10\}$. Из этого следует $p=3$, $q=2$, $a=4$, $b=4$.

Понятно что одно из них равно двум

1)p=2

По моду 3 понимаем что q=3. По моду 5 понимаем что а делится на 4. По моду 9 если b хотя бы 2 понимаем что a делится на 6 отсюда по моду 25 $2^{24k}$ дает 1 , но $5•3^b$ не может делится на 25 значит (p,a,b,q)=(2,4,1,3)

2)q=2

По моду 5 понимаем что а делится на 4 отсюда так как

$p^{2k}+1$ и $p^{2k}-1$ имеют нод 2 значит один из них равен 10 отсюда (p,a,b,q)=(3,4,4,2)

$p^a = 5q^b + 1$

$Очевидно, что одно из чисел это\ 2$

$***Первый\ случай***$

$p=2$

$2^a - 1 = 5q^b$

$Рассматривая\ степени\ двойки\ по\ \bmod\ 10,\ поймем,\ что\ a\ четное,\ значит\ LHS\ делится\ на\ 3,\ значит\ q=3$

$2^a -1 = 5\cdot3^b$

$По\ \bmod\ 5$

$2^a \equiv 1$

$Где\ a\ делится\ на\ 4$

$a=4n$

$2^{4n} – 1 = 5\cdot3^b$

$(2^{2n} – 1)(2^{2n} + 1) = 5\cdot3^b$

$Только\ первая\ скобка\ делится\ на\ 3$

$Значит\ вторая\ скобка\ делится\ на\ 5$

$2^{2n} + 1 = 5$

$n=1$

$a=4$

$b=1$

$p=2$

$q=3$

$***Второй\ случай***$

$p^a = 5\cdot2^b + 1$

$По\ \bmod\ 3$

$p^a \equiv 2^{b+1} + 1$

$Если\ b\ нечетное$

$То\ a\ нечетное\ (\text{пояснение: если } b \text{ нечетное то } RHS \equiv 2\ (\bmod\ 3)\ \text{и если } a \text{ четное то окажется,\ что квадрат целого числа дает остаток 2 при делении на 3})$

$По\ \bmod\ 5$

$p^a \equiv 1$

$Очевидно,\ что\ p\ \text{не равно}\ 5$

$Тогда\ по\ малой\ теореме\ Ферма$

$p^4 \equiv 1\ (\bmod\ 5)$

$Отсюда\ a\ делится\ на\ 4;\ a=4n$

$ПРОТИВОРЕЧИЕ$

$Тогда\ b\ четное,\ значит\ p=3$

$3^a – 1 = 5\cdot2^b$

$3^{4n} – 1 = 5\cdot2^b$

$(3^{2n} – 1)(3^{2n} + 1) = 5\cdot2^b$

$\gcd(3^{2n} – 1,\ 3^{2n} + 1) = \gcd(2,\ 3^{2n} + 1) = 2$

$(3^{2n} + 1)\ делится\ только\ на\ 2^1$

$3^{2n} + 1 = 2,\ \text{в данном случае числа не натуральные}$

$3^{2n} + 1 = 10,\ n=1,\ a=4,\ b=4,\ p=3,\ q=2$

$Ответ:\ (p,\ q,\ a,\ b) = (2,\ 3,\ 4,\ 1)\ ;\ (3,\ 2,\ 4,\ 4)$