Разделы 
Дополнительно
Задача по математике - 3060
2019-05-06 
Доказать, что
а) для каждого простого числа $p$ можно найти такие целые числа $x$ и $у$, что $x^2+y^2+1$ делится на $p$;
б) если простое число $p$ дает при делении на 4 остаток 1 (и для нечетных простых чисел - только в этом случае), существует такое целое число $x$, что $x^2+1$ делится на $p$.
Решение:
а) Если $p = 2$, то $p = 1^2 + 0^2+ 1$. Пусть теперь простое число $p$ нечетно; покажем, что можно найти два числа $x$ и $у$,
оба меньших чем $\frac{p}{2}$, удовлетворяющих условию задачи.
Рассмотрим $\frac{p+1}{2}$ чисел $0, 1, 2, \cdots, \frac{p-1}{2}$, Квадраты любых двух из этих чисел будут давать при делении на $p$ различные остатки; действительно, если было бы
$x_1^2 = k_1p$ и $x_2^2 = k_2p + r$,
то имело бы место равенство
$x_1^2 - x_2^2 = (x_1 - x_2)(x_1 + x_2) = (k_1 - k_2)p$,
т. е. $(x_1 - x_2)(x_1 + x_2)$ делилось бы на $p$, что невозможно, так как $x_1 < \frac{p}{2}, x_2 < \frac{p}{2}$ и $x_1 + x_2 < p$, |x_1 - x_2| < p (напоминаем, что $p$ - простое). Итак, $\frac{p+1}{2}$ чисел
$0^2, 1^2, 2^2, \cdots, \left ( \frac{p-1}{2} \right )^2$
при делении на $p$ дают $\frac{p+1}{2}$ различных остатков. Отсюда вытекает, что и следующие $\frac{p+1}{2}$ (отрицательных!) чисел: $—1, —1^2 — 1, -2^2 - 1, \cdots, - \left ( \frac{p-1}{2} \right )^2 - 1$ также при делении на $p$ дают $\frac{p+1}{2}$ различных остатков (если бы $— x_1^2 - 1$ и $- x_2^2 - 1$ давали одинаковые остатки, то и $x_1^2$ и $x_2^2$ давали бы одинаковые остатки). Но так как при делении на $р$ могут встречаться лишь $p$ различных остатков (а именно, $0, 1, 2, \cdots, p—1$), то ясно, что из $р + 1$ чисел $0^2, 1^2, 2^2, \cdots, \left ( \frac{p-1}{2} \right )^2, - 1, -1^2 - 1, \cdots, - \left ( \frac{p-1}{2} \right )^2 - 1$ по крайней мере два дают при делении на $p$ одинаковые остатки. В силу доказанного выше из такой пары чисел одно обязательно должно быть вида $x^2$, а второе — вида — $y^2 — 1$. Но если
$x^2 = kp + r$ и $— у^2 — 1 = lp + r$, то $x^2 + у^2 = (k-l)p — 1 = mp — 1$,
т. е. $x^2 + у^2 + 1 = mp$ делится на $p$.
б) Пусть $p = 4n + 1$ — простое число. В силу теоремы Вильсона (задача 3059) число
$(p - 1)! + 1 = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (4n) + 1$
делится на $р$. Заменим теперь в последнем выражении все множители большие $\frac{p-1}{2} = 2n$, через разности числа $р$ и чисел меньших $\frac{p-1}{2}$:
$(p-1)! + 1 = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n(р-2n)(р-2n + 1) \cdot \cdots \cdot (p - 1) + 1 = (1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n)[А_р + (- l)^{2n} 2n \times (2n - 1) \cdot \cdots \cdot 1] + 1 = A_1p + (1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n)^2 + 1$.
Так как это число делится на $р$, то и сумма $((2n)!)^2 + 1$ делится на $р$. Итак, условию задачи удовлетворяет число $х = (2n)! = \left ( \frac{p-1}{2} \right )!$.
Доказать, что
а) для каждого простого числа $p$ можно найти такие целые числа $x$ и $у$, что $x^2+y^2+1$ делится на $p$;
б) если простое число $p$ дает при делении на 4 остаток 1 (и для нечетных простых чисел - только в этом случае), существует такое целое число $x$, что $x^2+1$ делится на $p$.
Решение:
а) Если $p = 2$, то $p = 1^2 + 0^2+ 1$. Пусть теперь простое число $p$ нечетно; покажем, что можно найти два числа $x$ и $у$,
оба меньших чем $\frac{p}{2}$, удовлетворяющих условию задачи.
Рассмотрим $\frac{p+1}{2}$ чисел $0, 1, 2, \cdots, \frac{p-1}{2}$, Квадраты любых двух из этих чисел будут давать при делении на $p$ различные остатки; действительно, если было бы
$x_1^2 = k_1p$ и $x_2^2 = k_2p + r$,
то имело бы место равенство
$x_1^2 - x_2^2 = (x_1 - x_2)(x_1 + x_2) = (k_1 - k_2)p$,
т. е. $(x_1 - x_2)(x_1 + x_2)$ делилось бы на $p$, что невозможно, так как $x_1 < \frac{p}{2}, x_2 < \frac{p}{2}$ и $x_1 + x_2 < p$, |x_1 - x_2| < p (напоминаем, что $p$ - простое). Итак, $\frac{p+1}{2}$ чисел
$0^2, 1^2, 2^2, \cdots, \left ( \frac{p-1}{2} \right )^2$
при делении на $p$ дают $\frac{p+1}{2}$ различных остатков. Отсюда вытекает, что и следующие $\frac{p+1}{2}$ (отрицательных!) чисел: $—1, —1^2 — 1, -2^2 - 1, \cdots, - \left ( \frac{p-1}{2} \right )^2 - 1$ также при делении на $p$ дают $\frac{p+1}{2}$ различных остатков (если бы $— x_1^2 - 1$ и $- x_2^2 - 1$ давали одинаковые остатки, то и $x_1^2$ и $x_2^2$ давали бы одинаковые остатки). Но так как при делении на $р$ могут встречаться лишь $p$ различных остатков (а именно, $0, 1, 2, \cdots, p—1$), то ясно, что из $р + 1$ чисел $0^2, 1^2, 2^2, \cdots, \left ( \frac{p-1}{2} \right )^2, - 1, -1^2 - 1, \cdots, - \left ( \frac{p-1}{2} \right )^2 - 1$ по крайней мере два дают при делении на $p$ одинаковые остатки. В силу доказанного выше из такой пары чисел одно обязательно должно быть вида $x^2$, а второе — вида — $y^2 — 1$. Но если
$x^2 = kp + r$ и $— у^2 — 1 = lp + r$, то $x^2 + у^2 = (k-l)p — 1 = mp — 1$,
т. е. $x^2 + у^2 + 1 = mp$ делится на $p$.
б) Пусть $p = 4n + 1$ — простое число. В силу теоремы Вильсона (задача 3059) число
$(p - 1)! + 1 = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot (4n) + 1$
делится на $р$. Заменим теперь в последнем выражении все множители большие $\frac{p-1}{2} = 2n$, через разности числа $р$ и чисел меньших $\frac{p-1}{2}$:
$(p-1)! + 1 = 1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n(р-2n)(р-2n + 1) \cdot \cdots \cdot (p - 1) + 1 = (1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n)[А_р + (- l)^{2n} 2n \times (2n - 1) \cdot \cdots \cdot 1] + 1 = A_1p + (1 \cdot 2 \cdot 3 \cdot \cdots \cdot 2n)^2 + 1$.
Так как это число делится на $р$, то и сумма $((2n)!)^2 + 1$ делится на $р$. Итак, условию задачи удовлетворяет число $х = (2n)! = \left ( \frac{p-1}{2} \right )!$.
