Доказательство в кольце вычетов

Psilon · Регистрация: 10.07.2011

Студворк — интернет-сервис помощи студентам

День добрый.

Извиняюсь за тему, просто нужно восполнить знания, которых в универе не дали, а сам вот как-то пытаюсь освоить, но получается криво

Было у меня простое уравнение, свел к простейшему вида
(x² + y²) mod 3 = 0

и застрял. Нужно доказать, что решением являются
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x = 3{a}_{1}, y = 3{a}_{2}, {a}_{1,2}\in Z$

Проверил методом тупого перебора и вольфрамальфы, а хотелось бы аналитически доказать. Наилучшим, наверное, является доказательство от противного, но я вообще не умею оперировать в кольце вычетов. Без mod 3 я бы легко показал, что x² + y² = 0 верно только при x = 0, y = 0, т.к. достаточно найти производную и показать, что функция выпуклая с единственным экстремумом f(0,0) = 0, а вот методы анализа подобных выражения я, каюсь, не знаю.

@Том Ардер · 21.01.2015, 04:13

Psilon, подобные задачи относятся к "Диофантовым уравнениям", достаточно обширная тема в математике. Напр. http://www.ega-math.narod.ru/Liv/Diophant.htm
Здесь можно попробовать различные представления переменных (вариантов мало):
x = 3n, x = 3n ± 1 (y аналогично).

Добавлено через 9 минут
Один из вариантов:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv \pm 1 (mod\, 3)\Rightarrow x^2\equiv 1 (mod\, 3)$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y\equiv \pm 1 (mod\, 3)\Rightarrow y^2\equiv 1 (mod\, 3)$

Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi? x^2+y^2\equiv 2 (mod\, 3)$

Перебор небольшой, единственное решение: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv 0 (mod\, 3),\, y\equiv 0 (mod\, 3)$

Psilon · 21.01.2015, 04:14 **[ТС]**

Том Ардер, ну у нас всего лишь 0 1 2 возмнжных вариантов для x и y, получаем 9 комбинаций.
Но нет ли аналитического варианта? Для обычного уравнения (без mod) можно просто найти производную поверхности, и получить один экстремум, и всё. А тут переборный вариант какой-то выходит.

Потому что желательно решить общую задачу:
(x² + y²) mod n = 0
найти все x,y для которых выполняется это равенство при некотором n.

@Том Ардер · 21.01.2015, 04:28

В данном случае всего три варианта, это даже не перебор.
Общая же задача на порядок сложнее. По-моему, не существует общих методов для квадратичного Диофантова уравнения. И без серьёзного теоретико-числового исследования не обходится.

@kabenyuk · 21.01.2015, 08:00

Сообщение от Psilon

Для обычного уравнения (без mod) можно просто найти производную поверхности, и получить один экстремум, и всё.

При решении вашей задачи по mod 3 все неизмеримо проще. Замечаем, что любой квадрат по модулю 3 либо 0, либо 1. Значит сумма квадратов нулевая лишь тогда, когда оба слагаемых равны 0.
Было бы посложнее, если бы вы попытались решить такое же уравнение но по mod 89 (взял наугад небольшое простое число). Кстати, в этом случае есть ненулевое решение, возможно даже и много их.

Psilon · 21.01.2015, 14:42 **[ТС]**

Том Ардер, насколько я нагуглил, не решаются в общем виде только уравнения 3 порядка и выше.

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

Добавлено через 6 минут

Сообщение от kabenyuk

Замечаем, что любой квадрат по модулю 3 либо 0, либо 1.

вот как это мы замечаем?

Уменя в демидовичах и ко любимое слово - "очевидно". Ну а второе любимое "доказательство оставим читателю для тренировки".

Вот я не вижу причины, почему ∄x, x² mod 3 == 2. То есть я могу это увидеть для x = 1,2,3,... Но не вижу причины для x = 102145125712; Нужна индукция, а интуиция может жестоко обмануть.

@Том Ардер · 21.01.2015, 15:22

Сообщение от Psilon

Вот я не вижу причины, почему ∄x, x2 mod 3 == 2

Достаточно признать, что любое целое принадлежит к одному из классов: 3n, 3n+1, 3n+2==3n-1 (остаток при делении на 3 равен 0, 1, 2).
Спасибо за ссылку, прекрасно.

@kabenyuk · 21.01.2015, 16:54

Сообщение от Psilon

Но не вижу причины для x = 102145125712;

Вот даже считать ничего не надо. В свое время было доказано, говорят древним греком Евклидом (действительно индукцией, он правда не знал, что это назовут потом индукцией а его родину Древней), что для любого b>0 любое целое a можно представить в виде a=bq+r, 0<=r<b, r и q целые. Больше ничего не надо для малых модулей a.
А пример в ссылке чрезвычайно поучительный.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5

	Доказательство в кольце вычетов 21.01.2015, 02:03. Показов 1003. Ответов 7 Метки вычеты, кольцо, кольцо вычетов, уравнение (Все метки) День добрый. Извиняюсь за тему, просто нужно восполнить знания, которых в универе не дали, а сам вот как-то пытаюсь освоить, но получается криво Было у меня простое уравнение, свел к простейшему вида (x² + y²) mod 3 = 0 и застрял. Нужно доказать, что решением являются $https://www.cyberforum.ru/cgi-bin/latex.cgi?x = 3{a}_{1}, y = 3{a}_{2}, {a}_{1,2}\in Z$ Проверил методом тупого перебора и вольфрамальфы, а хотелось бы аналитически доказать. Наилучшим, наверное, является доказательство от противного, но я вообще не умею оперировать в кольце вычетов. Без mod 3 я бы легко показал, что x² + y² = 0 верно только при x = 0, y = 0, т.к. достаточно найти производную и показать, что функция выпуклая с единственным экстремумом f(0,0) = 0, а вот методы анализа подобных выражения я, каюсь, не знаю. 0

@Том Ардер $Эксперт по математике/физике$ 4218 / 3418 / 396 Регистрация: 15.06.2009 Сообщений: 5,818
	21.01.2015, 04:13
	Psilon, подобные задачи относятся к "Диофантовым уравнениям", достаточно обширная тема в математике. Напр. http://www.ega-math.narod.ru/Liv/Diophant.htm Здесь можно попробовать различные представления переменных (вариантов мало): *x = 3n, x = 3n ± 1* (y аналогично). Добавлено через 9 минут Один из вариантов: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv \pm 1 (mod\, 3)\Rightarrow x^2\equiv 1 (mod\, 3)$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?y\equiv \pm 1 (mod\, 3)\Rightarrow y^2\equiv 1 (mod\, 3)$ Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi? x^2+y^2\equiv 2 (mod\, 3)$ Перебор небольшой, единственное решение: $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\equiv 0 (mod\, 3),\, y\equiv 0 (mod\, 3)$ 0

Psilon Master of Orion 6102 / 4958 / 905 Регистрация: 10.07.2011 Сообщений: 14,522 Записей в блоге: 5
	21.01.2015, 04:14 [ТС]
	Том Ардер, ну у нас всего лишь 0 1 2 возмнжных вариантов для x и y, получаем 9 комбинаций. Но нет ли аналитического варианта? Для обычного уравнения (без mod) можно просто найти производную поверхности, и получить один экстремум, и всё. А тут переборный вариант какой-то выходит. Потому что желательно решить общую задачу: (x² + y²) mod n = 0 найти все x,y для которых выполняется это равенство при некотором n. 0

@Том Ардер $Эксперт по математике/физике$ 4218 / 3418 / 396 Регистрация: 15.06.2009 Сообщений: 5,818
	21.01.2015, 04:28
	В данном случае всего три варианта, это даже не перебор. Общая же задача на порядок сложнее. По-моему, не существует общих методов для квадратичного Диофантова уравнения. И без серьёзного теоретико-числового исследования не обходится. 1