Следствие от Теоремата на Ферма

[Neko- chan]

Може ли някой да каже какво е "класическото следствие от Теоремата на Ферма"? :/
Задачата е от ЗМС от 2015-та година.

[pal702004]

Не знам колко е "класическо", но все пак си е следствие, макар и съвсем не "очевидно" - сбора на два квадратите на две взаимнопрости числа няма делител от вида $4k+3$. Следствие на следствието - ако сбора от квадратите на 2 числа се дели на просто число от вида $p=4k+3$, то и двете числа се делят на $p$.

[pal702004]

Как се стига от теоремата до следствието. Малката теорема на Ферма гласи, че ако $p\not \mid a$, то $a^{p-1}\equiv 1 \pmod p$

1) $x^2+1$ няма прости делители от вида $4k+3$ Доказателство:

Нека $p \mid (x^2+1)$ Или $x^2\equiv -1 \pmod p$. Тогава $x^{2t} \equiv -1 \pmod p$ за всяко нечетно $t$

$x^{2t}=(x^2)^t\equiv (-1)^t\equiv -1 \pmod p$

И при $t=\frac{p-1}{2}$, а то ще е нечетно, ако $p=4k+3$, получаваме $x^{p-1} \equiv -1 \pmod p$ - противоречие с МТФ.

2) $a^2+b^2$ няма прости делители от вида $p=4k+3$, освен ако и $a$, и $b$ не се делят на $p$. Доказателство:

Нека $a^2+b^2$ се дели на просто $p$

$p \mid (a^2+b^2) \Rightarrow p \mid (ay)^2+(px-by)^2 \; \forall x,y \in \mathbb{Z}$

За всички взаимнопрости $p$ и $b$ уравнението $px-by=1$ има безброй решения в цели $(x,y)$

Тоест, съществува $y$, такова че $p\mid (ay)^2+1$

По-горе доказахме, че такива $p=4k+3$ не съществуват.