11-я Балканская математическая олимпиада среди юниоров Шумен, Болгария, 2007 год

Пусть $ p$ — простое число. Докажите, что число $ 7p+3^{p}-4$ не является полным квадратом.

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

$\textbf{Решение:}$ По Малой теореме Ферма $3^p-3$ делится на $p$. Тогда число $7p+3^p-4$ при делении на $p$ дает остаток $-1$.Любое простое число при делении на $4$ дает остаток $1$, либо $3$. Так как $p -$ простое число, то необходимо рассмотреть два случая:

$\textbf{Случай №1.}$ $p=4k+3 \Rightarrow 7p+3^p-4=7(4k+3)+3^{4k+3}-4=28k+3^{4k+3}+17\equiv -1 \quad (mod \quad p) \Rightarrow (28k+3^{4k+3}+17)^{2k+1}\equiv (-1)^{2k+1}=-1 \quad (mod \quad p) $

С другой стороны, число $7p+3^p-4$ является полным квадратом, то есть $7p+3^p-4=x^2, \quad x\in \mathbb{Z}$. Тогда имеем противоречие: $$-1=(-1)^{2k+1}\equiv(28k+3^{4k+3}+17)^{2k+1} = (x^2)^{2k+1}=x^{4k+2}=x^{p-1}\equiv 1\quad (mod \quad p) $$

$\textbf{Случай №2.}$ $p=4k+1 \Rightarrow 7p+3^p-4=7(4k+1)+3^{4k+1}-4=28k+3+3^{4k+1}=4\cdot 7k+(3^{4k+1}+1)+2\equiv 2\quad (mod \quad 4) $ Но это противоречит условию задачи, так как квадрат целого числа не может давать остаток $2$ при делении на $4$.

$Решение$:

Как пример выше, мы знаем что если к начальному примеру прибавить 1, то оно будет делиться на $p$.

$i)$ Если прибавить 1, то справа будет $a^2$+1 которое тоже будет делиться на $p$.

$ii)$ Используя $mod$ 4, получаем что $p=4k+3$ (сразу исключаем пример когда $p$-четное когда сравниваем по $mod$ 4).

$iii)$ Так как $a^2$+1 делится на p, то соответсвенно оно делится на $4k+3$.

Но если так подумать..

Это невозможно, ибо по Лемме$(1)$ $a$ и $1$ делится на $p$, но 1 не может делиться на $p$.

$(1)$ Лемма:

Если какие ни-будь $a^2$+$b^2$ делится на $p$ где $p$ вида $4k+3$, то $a$ и $b$ делятся на $p$ ($p$-простое)

$Доказательство$:

Допустим что это не так.И $(a;b,p)$=1.

$a^2$ оставляет $-b^2$ $(mod$ $p$)

соответсвенно $a^{4k+2}$ оставляет $-b^{4k+2}$ ($mod$ $p$)

но по Малой Теореме Ферма $a ^{4k+2},b^{4k+2}$ оставляют 1 по модулю $p$

Противоречие. Значит $a,b$ делится на $p$.

Если что, эта лемма называется теоремой Жерара (если понадобится)

скинь ссылку, не могу найти

Не могу загрузить саму книгу, вот скрин:

Вы будите отдыхать? сидите задачи решаете. С окончанием учебного года! Лучше празднуйте этот день!

Кстати да, с праздником всех

Абен, как я знаю вы закончили 11 класс в этом году

удачи с поступлением и с жизнью студента! (могу ошибаться, буду рад если подправите)

Да вы правы. Как приятно такое слышать от человека которого почти не знаешь

не уверен что это теорема, но хорошо.

можете скинуть мне книгу? думаю она интересная.

мой телеграм- qw1304

email- [e-mail]

Пусть $7p$ $+$ $3^p$ $-$ $4$ $=$ $n^2$ для какого то натурального $n$,так как $LHS$ четно, то рассмотрев по $mod$ $4$, понимаем что $7p$ $+$ $3^p$ $-$ $4$ делиться на 4, откуда находим что простое число $p$ имеет вид $4k+3$, по Великой Теореме Ферма число $7p$ $+$ $3^p$ $-$ $3$ делиться на $p$, откуда и $n^2$ $+$ $1$ делиться на $p$, но по Теореме Жерара для $4k+3$, $1$ должен делиться на $p$, противоречие.

Для $p$ $=$ $2$ так же невозможно

**По малая теореме Ферма:**

Если $p$ — простое число и $a$ — целое число, не делящееся на $p$, то выполняется сравнение:

$$ a^{p-1} \equiv 1 \pmod{p} $$

**Доказательство:**

Рассмотрим множество остатков по модулю $p$:

$$ S = \{a, 2a, 3a, \dots, (p-1)a\} $$

Так как $a$ не делится на $p$, то все элементы $S$ попарно различны по модулю $p$.

Это означает, что $S$ является перестановкой множества:

$$ \{1, 2, 3, \dots, p-1\} $$

Следовательно, их произведения сравнимы по модулю $p$:

$$ (a \cdot 2a \cdot 3a \cdots (p-1)a) \equiv (1 \cdot 2 \cdot 3 \cdots (p-1)) \pmod{p} $$

Вынесем $a^{p-1}$ за скобки:

$$ a^{p-1} \cdot (1 \cdot 2 \cdot 3 \cdots (p-1)) \equiv (1 \cdot 2 \cdot 3 \cdots (p-1)) \pmod{p} $$

Так как $1 \cdot 2 \cdot \dots \cdot (p-1)$ взаимно просто с $p$, можно сократить:

$$ a^{p-1} \equiv 1 \pmod{p} $$

Доказана. $\square$

Решим от противного.

Пусть $7p + 3^p - 4 = a^2$, где $a$ — натуральное число.

При $p=2$: $7\cdot2 + 3^2 - 4 = 14 + 9 - 4 = 19$ — не квадрат.

При $p=3$: $7\cdot3 + 3^3 - 4 = 21 + 27 - 4 = 44$ — тоже не квадрат.

Пусть теперь $p \geq 5$.

Тогда рассмотрим равенство по модулю $p$:

$a^2 \equiv 7p + 3^p - 4 \equiv 3^p - 4 \pmod{p}$.

Заметим, что $3^p \equiv 3 \pmod{p}$ (по малой теореме Ферма, если $p$ не делит $3$).

Тогда:

$a^2 \equiv 3 - 4 \equiv -1 \pmod{p}$.

То есть $-1$ является квадратичным вычетом по модулю $p$.

Лемма. Если $p$ — нечётное простое число, и $-1$ является квадратичным вычетом по модулю $p$, то $p \equiv 1 \pmod{4}$.

Доказательство:

Воспользуемся символом Лежандра. Известно, что:

$\left( \dfrac{-1}{p} \right) = (-1)^{\frac{p-1}{2}}$.

Если $-1$ — квадратичный вычет, то:

$(-1)^{\frac{p-1}{2}} = 1$,

значит, $\frac{p-1}{2}$ чётно, и тогда $p-1$ делится на $4$, то есть $p \equiv 1 \pmod{4}$. Лемма доказана.

Вернёмся к решению.

Итак, $p \equiv 1 \pmod{4}$.

Теперь рассмотрим исходное выражение по модулю $4$:

$7p + 3^p - 4 \equiv 7 \cdot 1 + 3^p - 4 = 7 + 3^p - 4 = 3 + 3^p \pmod{4}$.

Так как $p$ нечётное $3^p \equiv 3 \pmod{4}$.

Тогда:

$3 + 3^p \equiv 3 + 3 = 6 \equiv 2 \pmod{4}$.

А квадрат по модулю $4$ может быть только $0$ или $1$.

Противоречие.