x^2 mod N = 1 ? - вопрос №134166

Столько энергии приложили к уличению моей интерпретации задачи, что можно было бы ее и решить. Ваша запись смущает понимание задачи.

Обычно Вашу задачу, начиная с Гаусса, записывают в таком виде

x^2=1(mod N),

где знак равенства обычно заменяют знаком тождественного равенства.

Тогда задача решения квадратичного сравнения 

x^2=1(mod N)

индивидуальна для числа N в том смысле, что модуль N раскладывается на множители 

N= q1^n1 q2^n2… qk^nk

с простыми q1,q2,...qk, и исходное сравнение сводится к системе сравнений

x^2=1(mod q1^n1)

x^2=1(mod q2^n2)

...

x^2=1(mod qk^nk).

Затем, следуя китайской тереме об остатках, собираются решения по модулю N.

Из множества полученных решений по Вашему условию следует удалить два решения x=+-1(mod N).

Если N — простое число, то сравнение

x^2=1(mod N) 

имеет два решения

 x=+-1(mod N)

которые Вы хотите выбросить.

В общем случае проблема решения квадратичного сравнения сравнима с факторизацией модуля N. Для нечетного модуля количество решений равно 2^k. В случае четного модуля количество решений зависит от степени двойки в разложении модуля. Все это давно известно. Достаточно взглянуть в любой учебник по теории чисел, например, Виноградова, Сизого, Бухштаба и др.

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

Кроме того, позиционируя себя экспертом по технологиям создания сайтов и SEO-оптимизации, должны знать, что в Сети можно найти все, если знать, что искать. Если бы Вы набрали в своем любимом поисковике «квадратичное сравнение», то вывалилась бы сотня тысяч ссылок, из которых можно выбрать на свой взыскательный вкус то, как получить ответ на свою задачу.

Здравствуйте, Azamat!

Чтобы получить четкий ответ, надо задавать четкий вопрос. Если Ваш вопрос состоит в том, чтобы найти такие натуральные числа N, чтобы существовало натуральное решение сравнения 

x^2(mod N)=1

при заданных Вами ограничениях, то надо записать сравнение в эквивалентном виде

x^2=N+1.

Отсюда следует, что число N должно быть произведением двух последовательных четных или нечетных натуральных чисел

(x-1)(x+1)=N.

Если у Вас другое уточнение, то стучитесь.

             Azamat!  Убедительная к Вам просьба – не хамить вообще, а одному из лучших специалистов в своем деле (в теории чисел, в частности), Владимиру Чепурных – тем более! (И Ваша запоздалая оценка профессионализма В.Чепурных — увы, запоздала...)

          В противном случае, не думаете, попросят Вас — нет, не обратиться к психологам, которых Вы рекомендуете (даже если б они могли Вам помочь) — а существенно дальше: просто с этого сайта, всерьез и надолго…?!

стучись ко мне, я тебе про КТО растолкую