Сравнимость по модулю.Отыскать модуль и свободную переменную

[denfedorov]

Доброго времени суток, участники dxdy!

Существует задача, которая относится к дискретной математике

$a(a+1) сравнимо с $A по модулю $m , где $A известно и дано, $a$ - зависит от найденного $m, найти все возможные $m<A

Если разложить$A$ на множители, то $a=m_1$ и $a+1=m_2$, где $m_1$ и $m_2$- некоторые комбинации из сомножителей A.
Вопрос, существуют ли другие решения, и если да, то какие?

[svv]

Конечно, существуют, например, $a=6,\; m=5,\; A=37$:
$6\cdot 7=42 \equiv 37 \;(\operatorname{mod} 5)$
Здесь вообще $A$ простое, и об общих множителях нет и речи. Специально подобрал, чтобы всё было взаимно-простое.

[Sonic86]

$a(a+1) \equiv A \pmod m$. Число решений равно $\prod\limits_{p|A}\left( 1+ \left( \frac{4A+1}{p} \right)\right)$, где $\left( \frac{4A+1}{p} \right)$ - символ Лежандра.
Все решения можно найти простым перебором чисел $m: 1 \leqslant m <A$ и корней уравнения - пойдет такой метод?

Интересно, можно ли попытаться оценить $\sum\limits_{1 \leqslant m <A}\prod\limits_{p|A}\left( 1+ \left( \frac{4A+1}{p} \right)\right)$?

[denfedorov]

svv в сообщении #521536 писал(а):

Конечно, существуют, например, $a=6,\; m=5,\; A=37$:
$6\cdot 7=42 \equiv 37 \;(\operatorname{\mod} 5)$
Здесь вообще $A$ простое, и об общих множителях нет и речи. Специально подобрал, чтобы всё было взаимно-простое.

Спасибо, Вы меня здорово поправили.
Точно, задача слишком размыта. Мне бы хотелось внести уточнение - теперь условия немного другие (система):

$b \equiv a \pmod {m}$
$t \equiv a^2 \pmod {m}$
найти $m$, когда $t$ и $b$ - даны и известны. Если $2<m ; m\to\min$.

[Sonic86]

Сравнимо пишется \equiv. По модулю можно писать \pmod{m}.
Наводите мышку на формулы - увидите их код.
Исправьте, пожалуйста, свой пост во имя читабельности.

Задача не стала понятнее: что такое $b,t$? Пишите целиком.

[denfedorov]

Sonic86 в сообщении #521546 писал(а):

Сравнимо пишется \equiv. По модулю можно писать \pmod{m}.
Наводите мышку на формулы - увидите их код.
Исправьте, пожалуйста, свой пост во имя читабельности.

Задача не стала понятнее: что такое $b,t$? Пишите целиком.

Про эти числа можно сказать, что они:
$b,t$ - целые положительные числа $2b>t; (b,t)=1$

[bot]

А $a$ - какое? Если просто какое-то, то заменив во втором сранении $a$ на $b$, получим $t\equiv b^2 \pmod m$. Тогда $m$ - это делитель известной разности $b^2-t$.

[denfedorov]

bot в сообщении #521552 писал(а):

А $a$ - какое? Если просто какое-то, то заменив во втором сранении $a$ на $b$, получим $t\equiv b^2 \pmod m$. Тогда $m$ - это делитель известной разности $b^2-t$.

Да, да... Точно. Спасибо, я вроде понял куда копать.

[Sonic86]

Sonic86 в сообщении #521541 писал(а):

$a(a+1) \equiv A \pmod m$.

denfedorov в сообщении #521551 писал(а):

$b,t$ - целые положительные числа $2b>t; (b,t)=1$

denfedorov в сообщении #521545 писал(а):

$b \equiv a \pmod {m}$
$t \equiv a^2 \pmod {m}$
найти $m$, когда $t$ и $b$ - даны и известны. Если $2<m ; m\to\min$.

denfedorov в сообщении #521551 писал(а):

$b,t$ - целые положительные числа $2b>t; (b,t)=1$

Явно какая-то нецельная задача, явно какая-то фигня.
Сразу $b \equiv a \pmod m$ и $b$ может быть элиминировано из задачи.
Далее

denfedorov в сообщении #521545 писал(а):

$t \equiv a^2 \pmod {m}$

Если $t$ - квадратичный невычет, то решений нет, так что сразу считаем, что $\left( \frac{t}{m}\right)=1$ (отсюда можно получить классы вычетов, к которым принадлежит $m$ по модулю $t$, если охота).
Все это вроде бы ничего не дает - все эти условия можно проверить после нахождения $m$.
И тогда просто решаем перебором: у нас $a(a+1) \equiv A \pmod m$, причем $a,A$ даны. Перебираем все делители $m \mid a(a+1)-A$ и проверяем для них $\left( \frac{t}{m}\right)=1$ и все. Делителей довольно мало - порядка $O(\ln A)$. Т.е.. работать будет быстро.
Пойдет?
Непонятная задача...

[denfedorov]

Sonic86 в сообщении #521556 писал(а):

Явно какая-то нецельная задача, явно какая-то фигня.
.........
Делителей довольно мало - порядка $O(\ln A)$. Т.е.. работать будет быстро.
Пойдет?
Непонятная задача...

Согласен, задача нецельная, и решить ее видимо неперебором не представляется возможности.