Страница 419 - гдз по алгебре 10 класс учебник Мерзляк, Номировский

12. Целозначные многочлены.

Рекомендуемая литература:

1) Панкратьев Е. В. Элементы компьютерной алгебры : учебное пособие. — М. : Интернет-ун-т информ. технологий : БИНОМ. Лаб. знаний, 2007. (Основы информатики и математики).

2) Полиа Г., Сеге Г. Задачи и теоремы из анализа. Ч. 2. — М. : Наука, 1978.

3) Прасолов В. В. Многочлены. — 4-е изд., испр. — М. : МЦНМО, 2014. (Классические направления в математике).

На изображении указана тема "Целозначные многочлены". Это многочлены, которые, несмотря на то, что их коэффициенты могут быть нецелыми (рациональными), принимают целочисленные значения для всех целочисленных аргументов.

Определение: Многочлен $P(x)$ с рациональными коэффициентами называется целозначным, если для любого целого числа $n \in \mathbb{Z}$ значение $P(n)$ также является целым числом.

Простейшими примерами целозначных многочленов являются многочлены с целыми коэффициентами. Например, $P(x) = 2x^2 - 3x + 5$. Очевидно, что при любом целом $x$ значение этого многочлена будет целым.

Однако существуют и целозначные многочлены, у которых не все коэффициенты целые. Классический пример — многочлен $P(x) = \frac{x(x-1)}{2}$.
Распишем его в стандартном виде: $P(x) = \frac{1}{2}x^2 - \frac{1}{2}x$. Коэффициенты $\frac{1}{2}$ и $-\frac{1}{2}$ не являются целыми. Тем не менее, для любого целого $x$, одно из чисел $x$ или $x-1$ является чётным, поэтому их произведение $x(x-1)$ всегда делится на 2. Следовательно, $P(x)$ принимает целые значения для всех целых $x$.

Этот пример является частным случаем так называемых биномиальных многочленов (или многочленов-коэффициентов Ньютона):
$C_k(x) = \binom{x}{k} = \frac{x(x-1)\dots(x-k+1)}{k!}$
Для любого натурального $k$, многочлен $C_k(x)$ является целозначным.

Возникает вопрос: как описать все целозначные многочлены? Оказывается, любой целозначный многочлен может быть представлен в виде линейной комбинации биномиальных многочленов с целыми коэффициентами. Это утверждение является основной теоремой о целозначных многочленах.

Теорема (Полиа): Многочлен $P(x)$ степени $d$ с рациональными коэффициентами является целозначным тогда и только тогда, когда он может быть единственным образом представлен в виде:
$P(x) = a_d \binom{x}{d} + a_{d-1} \binom{x}{d-1} + \dots + a_1 \binom{x}{1} + a_0 \binom{x}{0}$,
где коэффициенты $a_0, a_1, \dots, a_d$ являются целыми числами.

Доказательство (идея):
1. Достаточность (⇐): Если многочлен $P(x)$ представлен в указанном виде с целыми $a_k$, то он является целозначным. Это следует из того, что каждый биномиальный многочлен $\binom{x}{k}$ является целозначным, а сумма целозначных многочленов с целыми коэффициентами также является целозначным многочленом.
2. Необходимость (⇒): Пусть $P(x)$ — целозначный многочлен степени $d$. Нужно показать, что коэффициенты $a_k$ в его разложении по базису из $\binom{x}{k}$ являются целыми. Эти коэффициенты можно найти с помощью оператора конечной разности $\Delta$, который определяется как $\Delta P(x) = P(x+1) - P(x)$. Если $P(x)$ — многочлен степени $d$, то $\Delta P(x)$ — многочлен степени $d-1$. Если $P(x)$ — целозначный, то $\Delta P(x)$ также целозначный.
Коэффициенты $a_k$ находятся по формулам:
$a_0 = P(0)$
$a_1 = \Delta P(0) = P(1) - P(0)$
$a_2 = \Delta^2 P(0) = \Delta(P(1)-P(0)) = (P(2)-P(1)) - (P(1)-P(0)) = P(2) - 2P(1) + P(0)$
...
$a_k = \Delta^k P(0)$
Поскольку $P(x)$ принимает целые значения во всех целых точках ($P(0), P(1), P(2), \dots$), то все его конечные разности $\Delta^k P(0)$ также будут целыми числами. Таким образом, все коэффициенты $a_k$ являются целыми.

Этот результат показывает, что множество целозначных многочленов образует кольцо, а многочлены $\binom{x}{k}$ для $k=0, 1, 2, \dots$ образуют базис этого кольца как свободного $\mathbb{Z}$-модуля.

Ответ: Целозначный многочлен — это многочлен с рациональными коэффициентами, который принимает целые значения при всех целых значениях аргумента. Основная теорема утверждает, что любой такой многочлен степени $d$ может быть единственным образом представлен как линейная комбинация биномиальных многочленов $\binom{x}{0}, \binom{x}{1}, \dots, \binom{x}{d}$ с целыми коэффициентами.

13. Цепные дроби и диофантовы уравнения.

Рекомендуемая литература:

1) Арнольд В. И. Цепные дроби. — 2-е изд., стер. — М. : МЦНМО, 2009. (Библиотека «Математическое просвещение»; вып. 14).

2) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПб. [и др.] : Лань, 2015. (Классическая учебная литература по математике).

3) Нестеренко Ю. В., Никишин Е. М. Очерк о цепных дробях // Квант. 1983. № 5. — С. 16–20; № 6. — С. 26–30.

4) Хинчин А. Я. Цепные дроби. — 4-е изд., стер. — М. : Едиториал УРСС, 2004.

На изображении представлен заголовок темы «Цепные дроби и диофантовы уравнения» и список рекомендуемой литературы. Поскольку конкретной задачи или вопроса нет, ниже приведено развернутое объяснение этой темы, раскрывающее суть цепных дробей, диофантовых уравнений и связи между ними.

Что такое цепные дроби?

Цепная (или непрерывная) дробь — это способ представления действительного числа в виде выражения с последовательностью вложенных дробей. Общий вид цепной дроби:

где $a_0$ — целое число, а все последующие $a_i$ (при $i \ge 1$) — натуральные числа. Эти числа $a_i$ называются неполными частными или элементами цепной дроби. Для краткости используется запись $[a_0; a_1, a_2, a_3, \dots]$.

Основные свойства цепных дробей:

• Любое рациональное число (обыкновенная дробь $p/q$) представляется в виде конечной цепной дроби. Алгоритм нахождения её элементов совпадает с алгоритмом Евклида для нахождения наибольшего общего делителя чисел $p$ и $q$.
• Любое иррациональное число (например, $\sqrt{2}$ или $\pi$) представляется в виде бесконечной цепной дроби.
• Квадратичные иррациональности (числа вида $a + b\sqrt{D}$, где $a, b$ — рациональные, а $D$ — натуральное число, не являющееся полным квадратом) представляются в виде бесконечных периодических цепных дробей.

Пример. Разложим число $\frac{97}{31}$ в цепную дробь.

1. $\frac{97}{31} = 3 + \frac{4}{31}$. Первый элемент $a_0 = 3$.
2. Переворачиваем остаток: $\frac{31}{4} = 7 + \frac{3}{4}$. Второй элемент $a_1 = 7$.
3. Переворачиваем новый остаток: $\frac{4}{3}{ = 1 + \frac{1}{3}}$. Третий элемент $a_2 = 1$.
4. Переворачиваем последний остаток: $\frac{3}{1} = 3$. Четвертый элемент $a_3 = 3$.

Таким образом, $\frac{97}{31} = 3 + \frac{1}{7 + \frac{1}{1 + \frac{1}{3}}}$, или в краткой записи $[3; 7, 1, 3]$.

Фрагменты цепной дроби, называемые подходящими дробями (например, $[a_0]$, $[a_0; a_1]$, $[a_0; a_1, a_2]$ и т.д.), дают наилучшие рациональные приближения исходного числа.

Ответ: Цепная дробь — это представление числа в виде "многоэтажной" дроби. Конечные цепные дроби соответствуют рациональным числам, а бесконечные — иррациональным. Они являются ключевым инструментом в теории чисел, в частности, в теории приближения чисел.

Что такое диофантовы уравнения?

Диофантово уравнение — это алгебраическое уравнение с целыми коэффициентами, для которого требуется найти целочисленные решения. Названы они в честь древнегреческого математика Диофанта Александрийского.

Примеры диофантовых уравнений:

• Линейное диофантово уравнение: $ax + by = c$, где $a, b, c$ — заданные целые числа, а $x, y$ — неизвестные целые. Такое уравнение имеет решение тогда и только тогда, когда $c$ делится нацело на наибольший общий делитель (НОД) чисел $a$ и $b$.
• Уравнение Пелля: $x^2 - Dy^2 = 1$, где $D$ — заданное натуральное число, не являющееся полным квадратом. Это уравнение всегда имеет бесконечное множество целочисленных решений.
• Уравнение Пифагора: $x^2 + y^2 = z^2$. Его целочисленные решения $(x, y, z)$ называются пифагоровыми тройками (например, (3, 4, 5)).

Общей теории решения произвольных диофантовых уравнений не существует. Как показал Юрий Матиясевич, не существует и универсального алгоритма, который бы для любого диофантова уравнения определял, есть ли у него целочисленные решения (отрицательное решение десятой проблемы Гильберта).

Ответ: Диофантово уравнение — это уравнение, для которого ищутся решения в целых числах. Их изучение является одной из центральных и самых сложных областей теории чисел.

Как связаны цепные дроби и диофантовы уравнения?

Цепные дроби предоставляют мощный и элегантный метод для решения некоторых важных классов диофантовых уравнений.

1. Решение линейных диофантовых уравнений.

Рассмотрим уравнение $ax - by = 1$, где $a$ и $b$ — взаимно простые натуральные числа. Чтобы найти его решение, нужно разложить дробь $a/b$ в конечную цепную дробь. Пусть $a/b = [a_0; a_1, \dots, a_n]$. Обозначим предпоследнюю подходящую дробь как $P_{n-1}/Q_{n-1}$. Тогда выполняется тождество:

Отсюда легко получить решение исходного уравнения. Если $n-1$ — четное, то $(x_0, y_0) = (Q_{n-1}, P_{n-1})$ является решением. Если $n-1$ — нечетное, то решением будет $(-Q_{n-1}, -P_{n-1})$.

2. Решение уравнения Пелля.

Для нахождения целочисленных решений уравнения $x^2 - Dy^2 = 1$ (где $D > 0$ и не является квадратом) необходимо разложить число $\sqrt{D}$ в бесконечную периодическую цепную дробь. Оказывается, что все решения $(x, y)$ этого уравнения являются числителями и знаменателями подходящих дробей для $\sqrt{D}$.

Пример. Найдем решение уравнения $x^2 - 3y^2 = 1$.

Разложим $\sqrt{3}$ в цепную дробь:

Получаем периодическую дробь: $\sqrt{3} = [1; 1, 2, 1, 2, \dots] = [1; \overline{1, 2}]$.

Найдем подходящие дроби:

• $\frac{P_0}{Q_0} = \frac{1}{1}$ (Проверка: $1^2 - 3 \cdot 1^2 = -2$)
• $\frac{P_1}{Q_1} = 1 + \frac{1}{1} = \frac{2}{1}$ (Проверка: $2^2 - 3 \cdot 1^2 = 1$)

Мы нашли наименьшее нетривиальное решение (его называют фундаментальным): $(x, y) = (2, 1)$. Все остальные решения можно получить из фундаментального.

Ответ: Аппарат цепных дробей является одним из основных методов решения диофантовых уравнений. Алгоритм Евклида, лежащий в основе разложения в цепную дробь, напрямую приводит к решению линейных уравнений. Разложение квадратных иррациональностей в цепную дробь позволяет находить все решения уравнения Пелля.

14. Числовые функции теории чисел.

Рекомендуемая литература:

1) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПБ. [и др.] : Лань, 2015. (Классическая учебная литература по математике).

2) Виноградов И. М. Основы теории чисел. — 10-е изд., стер. — СПБ. [и др.] : Лань, 2004.

3) Деза Е. И., Котова Л. В. Сборник задач по теории чисел : 112 задач с подробными решениями. — М. : URSS, 2011.

На изображении представлен заголовок темы «Числовые функции теории чисел» и список рекомендуемой литературы. Поскольку конкретного вопроса или задачи нет, ниже приводится развернутое объяснение этой темы.

Числовая функция (или арифметическая функция) в теории чисел — это функция $f(n)$, определённая на множестве натуральных чисел $\mathbb{N} = \{1, 2, 3, \dots\}$ и принимающая значения в множестве комплексных чисел $\mathbb{C}$ (или, чаще, в множестве действительных $\mathbb{R}$ или целых $\mathbb{Z}$ чисел). Эти функции играют фундаментальную роль в изучении свойств целых чисел, таких как делимость, распределение простых чисел и решение диофантовых уравнений. Книги, указанные в списке, являются классическими учебными пособиями, подробно освещающими эту тему.

Ответ: Числовая (арифметическая) функция — это функция, областью определения которой является множество натуральных чисел.

Существует множество важных числовых функций, каждая из которых описывает определённое свойство натуральных чисел. Рассмотрим некоторые из них.

• Число делителей $\tau(n)$ (также обозначается $d(n)$). Эта функция для каждого натурального числа $n$ находит количество его натуральных делителей. Формально, $\tau(n) = \sum_{d|n} 1$. Если каноническое разложение числа $n$ на простые множители имеет вид $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, то число его делителей вычисляется по формуле:
  $\tau(n) = (a_1+1)(a_2+1)\cdots(a_k+1)$.
  Пример: для $n=12=2^2 \cdot 3^1$, $\tau(12) = (2+1)(1+1) = 3 \cdot 2 = 6$. Делители числа 12: 1, 2, 3, 4, 6, 12.
• Сумма делителей $\sigma(n)$. Эта функция находит сумму всех натуральных делителей числа $n$. Формально, $\sigma(n) = \sum_{d|n} d$. Для числа $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ формула для суммы делителей выглядит так:
  $\sigma(n) = \frac{p_1^{a_1+1}-1}{p_1-1} \cdot \frac{p_2^{a_2+1}-1}{p_2-1} \cdots \frac{p_k^{a_k+1}-1}{p_k-1}$.
  Пример: для $n=12=2^2 \cdot 3^1$, $\sigma(12) = \frac{2^{2+1}-1}{2-1} \cdot \frac{3^{1+1}-1}{3-1} = \frac{7}{1} \cdot \frac{8}{2} = 28$. Сумма делителей: $1+2+3+4+6+12=28$.
• Функция Эйлера $\varphi(n)$. Функция Эйлера (или тотиент-функция) показывает количество натуральных чисел, не превосходящих $n$ и взаимно простых с $n$. Для $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ формула имеет вид:
  $\varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right)$.
  Пример: для $n=12=2^2 \cdot 3^1$, $\varphi(12) = 12(1-\frac{1}{2})(1-\frac{1}{3}) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4$. Взаимно простые с 12 числа: 1, 5, 7, 11.
• Функция Мёбиуса $\mu(n)$. Это функция, используемая во многих аспектах теории чисел, в частности, в формуле обращения Мёбиуса. Она определяется следующим образом:
  $\mu(n) = \begin{cases} 1, & \text{если } n=1 \\ (-1)^k, & \text{если } n \text{ — произведение } k \text{ различных простых чисел} \\ 0, & \text{если } n \text{ делится на квадрат простого числа} \end{cases}$
  Пример: $\mu(6) = \mu(2 \cdot 3) = (-1)^2=1$; $\mu(10) = \mu(2 \cdot 5)=1$; $\mu(30)=\mu(2 \cdot 3 \cdot 5) = (-1)^3=-1$; $\mu(12) = \mu(2^2 \cdot 3)=0$.
  Важное свойство: $\sum_{d|n} \mu(d) = 1$ для $n=1$ и $0$ для $n>1$.

Ответ: Ключевыми числовыми функциями являются число делителей $\tau(n)$, сумма делителей $\sigma(n)$, функция Эйлера $\varphi(n)$ и функция Мёбиуса $\mu(n)$, каждая из которых вычисляется на основе канонического разложения числа на простые множители.

Многие числовые функции обладают важным свойством мультипликативности или аддитивности. Это свойство значительно упрощает их вычисление.

• Мультипликативная функция. Функция $f(n)$ называется мультипликативной, если $f(1)=1$ и для любых двух взаимно простых чисел $m$ и $n$ (т.е. $\text{НОД}(m,n)=1$) выполняется равенство $f(mn) = f(m)f(n)$.
  Все рассмотренные выше функции — $\tau(n)$, $\sigma(n)$, $\varphi(n)$ и $\mu(n)$ — являются мультипликативными.
  Если равенство $f(mn) = f(m)f(n)$ выполняется для любых натуральных $m$ и $n$, то функция называется вполне (или строго) мультипликативной. Пример: $f(n)=n^k$ для некоторого $k$.
• Аддитивная функция. Функция $g(n)$ называется аддитивной, если для любых двух взаимно простых чисел $m$ и $n$ выполняется равенство $g(mn) = g(m)+g(n)$.
  Пример: функция $\omega(n)$ — число различных простых делителей числа $n$. Для $n=12=3 \cdot 4$, $\omega(12)=2$, и $\omega(3)+\omega(4)=1+1=2$.
  Если равенство $g(mn) = g(m)+g(n)$ выполняется для любых натуральных $m$ и $n$, то функция называется вполне (или строго) аддитивной. Пример: функция $\Omega(n)$ — число простых делителей числа $n$ с учётом их кратности. Для $n=12=2^2 \cdot 3^1$, $\Omega(12)=2+1=3$.

Свойство мультипликативности позволяет вычислять значение функции для любого числа, зная лишь её значения для степеней простых чисел. Если $n = p_1^{a_1} \cdots p_k^{a_k}$, то для мультипликативной функции $f$ справедливо $f(n) = f(p_1^{a_1}) \cdots f(p_k^{a_k})$.

Ответ: Мультипликативные функции удовлетворяют свойству $f(mn) = f(m)f(n)$ для взаимно простых $m$ и $n$, что позволяет легко вычислять их значения через разложение аргумента на простые множители. Аналогично, аддитивные функции удовлетворяют свойству $g(mn) = g(m)+g(n)$.

15. Теорема Ферма о сумме двух квадратов.

Рекомендуемая литература:

1) Бухштаб А. А. Теория чисел : учебное пособие. — 4-е изд., стер. — СПб. [и др.] : Лань, 2015. (Классическая учебная литература по математике).

2) Сендеров В., Спивак А. Суммы квадратов и целые гауссовы числа // Квант. 1999. № 3. С. 14—22.

3) Спивак А. Суммы квадратов // Популярные лекции по математике ММ МГУ, 2013/14 у. г., лекция № 19 (334).

4) Тихомиров В. Теорема Ферма — Эйлера о двух квадратах // Квант. 1991. № 10. С. 9—12.

5) Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — М. : МЦНМО, 2003. (Библиотека «Математическое просвещение»; вып. 1).

На изображении представлена тема «Теорема Ферма о сумме двух квадратов» и список рекомендуемой литературы. Развернутый ответ на этот неявный вопрос состоит в формулировке и доказательстве данной теоремы.

Формулировка теоремы

Теорема, сформулированная Пьером де Ферма в 1640 году и доказанная Леонардом Эйлером в 1749 году, устанавливает критерий, по которому натуральное число может быть представлено в виде суммы двух квадратов целых чисел.

Основная формулировка (для простых чисел):

Нечётное простое число $p$ может быть представлено в виде суммы двух квадратов, $p = a^2 + b^2$, где $a, b$ — целые числа, тогда и только тогда, когда $p$ имеет вид $4k+1$, то есть $p \equiv 1 \pmod{4}$.

Простое число 2 также представимо в виде суммы двух квадратов: $2 = 1^2 + 1^2$. Простые числа вида $4k+3$ не могут быть представлены в виде суммы двух квадратов.

Обобщение (для составных чисел):

Натуральное число $n > 1$ представимо в виде суммы двух квадратов тогда и только тогда, когда в его каноническом разложении на простые множители все простые сомножители вида $4k+3$ входят в чётной степени.

Доказательство необходимости

Докажем, что если нечётное простое число $p$ можно представить в виде суммы двух квадратов, $p = a^2 + b^2$, то оно должно иметь вид $4k+1$.

Рассмотрим квадраты целых чисел по модулю 4:

• Если число $x$ чётно, то $x = 2m$, и $x^2 = (2m)^2 = 4m^2 \equiv 0 \pmod{4}$.
• Если число $x$ нечётно, то $x = 2m+1$, и $x^2 = (2m+1)^2 = 4m^2 + 4m + 1 \equiv 1 \pmod{4}$.

Таким образом, любой квадрат целого числа при делении на 4 даёт в остатке либо 0, либо 1.

Теперь рассмотрим сумму двух квадратов $a^2 + b^2$ по модулю 4:

• Если $a$ и $b$ оба чётные, то $a^2 + b^2 \equiv 0 + 0 = 0 \pmod{4}$.
• Если одно чётное, а другое нечётное, то $a^2 + b^2 \equiv 0 + 1 = 1 \pmod{4}$.
• Если $a$ и $b$ оба нечётные, то $a^2 + b^2 \equiv 1 + 1 = 2 \pmod{4}$.

Следовательно, сумма двух квадратов может быть сравнима с 0, 1 или 2 по модулю 4, но никогда не может быть сравнима с 3.

Поскольку $p$ — нечётное простое число, оно не может быть сравнимо с 0 или 2 по модулю 4 (т.е. быть чётным). Значит, если $p = a^2+b^2$, то $p$ может быть сравнимо только с 1 по модулю 4. Это доказывает, что простые числа вида $4k+3$ непредставимы в виде суммы двух квадратов.

Доказательство достаточности

Теперь докажем, что если простое число $p$ имеет вид $p=4k+1$, то его можно представить в виде суммы двух квадратов. Доказательство состоит из нескольких шагов.

Шаг 1: Существование числа $a$, такого что $a^2 \equiv -1 \pmod{p}$.

Согласно теореме Вильсона, для любого простого $p$ выполняется сравнение $(p-1)! \equiv -1 \pmod{p}$.

Поскольку $p = 4k+1$, мы можем записать $(p-1)!$ как:

$(4k)! = (1 \cdot 2 \cdots 2k) \cdot ((2k+1) \cdots 4k)$.

Заметим, что $p-j \equiv -j \pmod{p}$. Тогда:

$4k \equiv -1 \pmod{p}$

$4k-1 \equiv -2 \pmod{p}$

...

$2k+1 \equiv -(2k) \pmod{p}$

Переписываем вторую часть произведения:

$(2k+1) \cdots (4k) \equiv (-(2k)) \cdots (-1) \pmod{p}$.

Это произведение содержит $2k$ членов, поэтому $(-1)$ выносится в степени $2k$, которая является чётной. Следовательно,

$(2k+1) \cdots (4k) \equiv (2k)! \pmod{p}$.

Подставляя это в исходное выражение для $(p-1)!$, получаем:

$(p-1)! = (4k)! \equiv (2k)! \cdot (2k)! = ((2k)!)^2 \pmod{p}$.

Так как по теореме Вильсона $(p-1)! \equiv -1 \pmod{p}$, мы получаем, что $((2k)!)^2 \equiv -1 \pmod{p}$.

Таким образом, мы нашли целое число $a = (2k)!$, квадрат которого даёт остаток -1 при делении на $p$. То есть, $a^2+1$ делится на $p$.

Шаг 2: Применение принципа Дирихле (голубей и клеток).

Мы знаем, что существует целое $a$, для которого $a^2+1 = mp$ для некоторого целого $m$. Нам нужно найти такие целые $x$ и $y$, что $x^2+y^2=p$.

Рассмотрим множество чисел вида $u+av$, где $u, v$ — целые числа в диапазоне $0 \le u, v \le \lfloor\sqrt{p}\rfloor$.

Количество пар $(u,v)$ равно $(\lfloor\sqrt{p}\rfloor+1)^2$. Так как $\sqrt{p}$ не является целым (потому что $p$ простое), то $\lfloor\sqrt{p}\rfloor < \sqrt{p}$, и значит $(\lfloor\sqrt{p}\rfloor+1) > \sqrt{p}$. Следовательно, количество пар больше, чем $(\sqrt{p})^2=p$.

По принципу Дирихле, раз у нас больше $p$ чисел ($u+av$), а возможных остатков по модулю $p$ всего $p$, то найдутся две различные пары $(u_1, v_1)$ и $(u_2, v_2)$, для которых:

$u_1 + av_1 \equiv u_2 + av_2 \pmod{p}$.

Перегруппируем члены: $u_1 - u_2 \equiv a(v_2 - v_1) \pmod{p}$.

Обозначим $x = u_1 - u_2$ и $y = v_2 - v_1$. Тогда $x \equiv -ay \pmod{p}$.

Поскольку пары $(u_1, v_1)$ и $(u_2, v_2)$ различны, хотя бы одно из чисел $x, y$ не равно нулю. Также, $|x| = |u_1 - u_2| \le \lfloor\sqrt{p}\rfloor$ и $|y| = |v_1 - v_2| \le \lfloor\sqrt{p}\rfloor$.

Возведём сравнение $x \equiv -ay \pmod{p}$ в квадрат: $x^2 \equiv a^2 y^2 \pmod{p}$.

Так как мы знаем, что $a^2 \equiv -1 \pmod{p}$, получаем $x^2 \equiv -y^2 \pmod{p}$, что эквивалентно $x^2 + y^2 \equiv 0 \pmod{p}$.

Это означает, что $x^2+y^2 = kp$ для некоторого целого $k$.

Шаг 3: Нахождение значения $k$.

Оценим $k$. Поскольку $x$ и $y$ не оба равны нулю, $x^2+y^2 > 0$, значит $k \ge 1$.

С другой стороны, $|x| \le \lfloor\sqrt{p}\rfloor < \sqrt{p}$ и $|y| \le \lfloor\sqrt{p}\rfloor < \sqrt{p}$.

Следовательно, $x^2+y^2 < (\sqrt{p})^2 + (\sqrt{p})^2 = 2p$.

Итак, $0 < kp < 2p$, что означает $k$ может быть только 1.

Таким образом, мы нашли целые числа $x$ и $y$, для которых $x^2+y^2 = p$. Достаточность доказана.

Примеры

• $p=5$. $5 \equiv 1 \pmod{4}$. Представимо: $5 = 1^2 + 2^2$.
• $p=13$. $13 \equiv 1 \pmod{4}$. Представимо: $13 = 2^2 + 3^2$.
• $p=29$. $29 \equiv 1 \pmod{4}$. Представимо: $29 = 2^2 + 5^2$.
• $p=7$. $7 \equiv 3 \pmod{4}$. Непредставимо в виде суммы двух квадратов.
• $n=90$. Разложение на простые: $90 = 2 \cdot 3^2 \cdot 5$. Простой множитель $3$ имеет вид $4k+3$, и он входит в чётной степени (2). Другие простые множители (2 и 5) удовлетворяют условию. Значит, 90 представимо: $90 = 3^2 + 9^2$.
• $n=21$. Разложение на простые: $21 = 3 \cdot 7$. Оба простых множителя ($3$ и $7$) имеют вид $4k+3$ и входят в нечётной степени (1). Следовательно, 21 непредставимо в виде суммы двух квадратов.

Ответ:

Теорема Ферма о сумме двух квадратов утверждает, что натуральное число $n$ может быть представлено в виде суммы двух квадратов целых чисел тогда и только тогда, когда в его разложении на простые множители все простые числа вида $4k+3$ содержатся в чётных степенях. В частном случае, для нечётного простого числа $p$, это означает, что оно представимо в виде суммы двух квадратов тогда и только тогда, когда $p \equiv 1 \pmod{4}$.