Вопрос по системе сравнений

[spywebka]

имеется система сравнений примерно такая:
$a*100+b\equiv51 mod m$
$a*50+b\equiv37 mod m$
$a*37+b\equiv41 mod m$
и т.д.
все получено из
$x_{n+1}= (ax_n+b)mod m$ (1)

помогите кто сможет.
Данный пример хорошо подходит для предугадания следующего значения последовательности случайных чисел заданных (1). Т.е. зная хотябы 3 подряд идущие значения последовательности определить последующие. Как найти a,b,m чтобы это было воможно!
Тут для примера последовательность 100,51,37... - значения конечно могут быть другие

[Sonic86]

spywebka
$\pmod$ пишется \pmod
Короче говоря, у Вас дана система сравнений
$100a+b \equiv 51 \pmod m$
$50a+b \equiv 37 \pmod m$
$37a+b \equiv 41 \pmod m$
и Вам надо найти $a,b,m$? Это нетрудно. Сравнения можно складывать, вычитать и умножать на число (причем если умножать на число, взаимно простое с модулем, то преобразование будет эквивалентным). Попробуйте и напишите, что у Вас получилось, если что, мы Вам поможем

[spywebka]

Да, надо найти a,b,m!!!
для х= 5 3 7 11
и системы от них:
$a*5+b\equiv3 \pmod m$
$a*3+b\equiv7 \pmod m$
$a*7+b\equiv11 \pmod m$

решая 1-3 получил
$a\equiv4 \pmod m$
решая 2-3 получил
$a\equiv1 \pmod m$

как дальше быть, чет я в тупике (китайскую теорему как здесь использовать?) или есть особое решение. ведь m-неизвестна
и с b тож самое получается практичски!

[Sonic86]

spywebka писал(а):

решая 1-3 получил
$a \equiv 1 \pmod m$
решая 2-3 получил
$a \equiv 4 \pmod m$

как дальше быть?

Вы уже почти все сделали, теперь отнимите из второго полученного сравнения первое, а потом вспомните смысл обозначения $x \equiv y \pmod m$.

[spywebka]

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

.... теперь отнимите из второго полученного сравнения первое, а потом вспомните смысл обозначения $x \equiv y \pmod m$.

меня берут смутные сомнения, потому что так я тоже пытался вычесть из второго первое. Но ведь получал $0 \equiv 3 \pmod m$ или я неправильно считаю???

[Sonic86]

spywebka писал(а):

$0 \equiv 3 \pmod m$

Совершенно верно . Теперь вспоминаем, что запись $x \equiv y \pmod m$ означает "$m$ делит $x-y$" и делаем вывод.

[spywebka]

но чтоже тогда получается?: -3 делится на m. Следует что m=3. И из уравнения
$a\equiv1 \pmod 3$
Получаем что a может быть равным 4,7,10...,
Решая для b получаем тоже самое:
может быть равным 4,7,10...

Решаем уравнение для а b - разных:
послитал что 4=а и 7=b
посчитал что следующий х=17 из
$4*11+7\equiv x \pmod 3$
следует
$51\equiv x \pmod 3$
$x=17$
верно? я правильно посчитал? даж народоваться немогу от счастья.....

если считать высчитывать дальше члены то как дыть? пришел к этому:
$4*17+7\equiv x \pmod 3$
$75\equiv x \pmod 3$
$x=25$

$4*25+7\equiv x \pmod 3$
$107\equiv x \pmod 3$
чему равен x? можно думать что x=17? или x=2 ,или х=29,а может x в этом случае зависит также от предыдущего(щих) значений?
если вы заметили я изначально задал псевдопроизвольную последовательность из простых чисел, и решая данную систему мы пришли к выводу что мы не можем определить точное значение следующего элемента, а мы можем просто определить все составляющие данной последовательности.так?
решая задачу все больше тупиковых моментов.....

[Sonic86]

spywebka
Ну дело в том, что если Вы решаете систему сравнений в целых числах, то сразу нужно знать, что неизвестные (кроме модуля $m$), вы не найдете точно, вы их найдете с точностью до класса по модулю $m$, т.е. $b$ у Вас будет равно $b_0 + mk, k \in \mathbb{Z}$. Поэтому система обычно решается в классах вычетов (ну или проще - в остатках от деления). То есть вот Вы нашли $a \equiv 1 \pmod 3$, теперь можете подставить это значение в уравнение $5a+b \equiv 3 \pmod m$, найти $b \equiv b_0 \pmod m$ и все, решение окончено. В ответе можно записать минимальные решения, т.е. $a=1, b=b_0, m=3$.

-- Вт июн 08, 2010 08:08:08 --

А при чем тут "найти $x$" я не понял. Я думал, что $x_n$ - это последовательность, которая генерится по начальному значению $x=x_0$ и потом по рекуррентной формуле $x_{n+1}=ax_n+b \pmod m$. Если да, то как раз достаточно найти $a,b,m$ и сказать, что последовательность $x_n$ задается формулой такой-то (подставляете в общую формулу найденные значения $a,b,m$).

Ну в принципе, если у Вас начальных значений $x_0$ несколько, то подставляете каждый раз какое-то $x_0$, решаете систему сравнений, как сейчас решали, и находите для каждого $x_0$ свои $a,b,m$. Естественно $a,b,m$ могут быть разные.

[spywebka]

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

spywebka
....теперь можете подставить это значение в уравнение $5a+b \equiv 3 \pmod m$, найти $b \equiv b_0 \pmod m$ и все, решение окончено. В ответе можно записать минимальные решения, т.е. $a=1, b=b_0, m=3$.

Интересный выход, можете дать ссылку на источник откуда вы взяли это, дело в том что перелистал книжки (немного) и в них неговорилось что можно подставить - просто идут примеры, примеры и примеры с небольшим описанием. Может покажете каким образом подставили в уравнение.... может свойство какое, или в книжках я это упустил.

А насчет последовательности верно.
к примеру вы загадали последовательность из простых чисел наугад, 5 3 7 11 17 13 25 19
нам известны к примеру начальные значения 5 3 7 11 и для всех остальных известно что можно их найти решив систему (см. начало темы). но $x_n$ зависит от $x_(n-1)$. Но для данной последовательности я привел пример на пару постов выше что после х=17 мы несможем найти х=13, мы найдем 25 и так по возрастающей....

[Sonic86]

spywebka писал(а):

Интересный выход, можете дать ссылку на источник откуда вы взяли это, дело в том что перелистал книжки (немного) и в них неговорилось что можно подставить - просто идут примеры, примеры и примеры с небольшим описанием. Может покажете каким образом подставили в уравнение.... может свойство какое, или в книжках я это упустил.

А тут ничего сложного: так как $a \equiv 1 \pmod 3$, то $5a+b \equiv 3 \pmod 3 \Leftrightarrow 5+b \equiv 3 \pmod 3 \Leftrightarrow b \equiv 1 \pmod 3$. просто подставили и решили.

Я сравнения учил по книжке Бухштаба Теория чисел. Это очень простая книжка, в ней даже 11-классник может разобраться. Но есть и много других книжек, их можно погуглить. А вообще ничего сложного там почти нету. Дело просто в том, что сравнения можно складывать, умножать на число так же, как и обычные уравнения. Исключение составляет только сокращение на число вместе с модулем.

[spywebka]

дк, получается что в нашу рекурентную формулу каждый раз мы можем встявлять любую пару а и b?

[Sonic86]

spywebka писал(а):

дк, получается что в нашу рекурентную формулу каждый раз мы можем встявлять любую пару а и b?

почему любую? одну и ту же. Просто пара зависит от $x_0$. Если Вы выбрали $x_0=5$, то все: $a \equiv 1 \pmod 3, b \equiv 1 \pmod 3$ и значит $x_{n+1}=x_n+1 \pmod 3$ и все.

[spywebka]

дк если $x_0=5$ то подставляя ваши полученные a и b мы не получим x=3

[Sonic86]

spywebka писал(а):

дк если $x_0=5$ то подставляя ваши полученные a и b мы не получим x=3

Ну почему же $x_0 \equiv 2 \pmod 3$, и значит $x_1 \equiv x_0 + 1 \equiv 3 \pmod 3$
Дело-то в том, что мы не найдем $x$ точнее, чем до какого-то класса вычета, пусть даже он будет очень большой.

И, кстати:

spywebka писал(а):

решая 1-3 получил
$a \equiv 1 \pmod m$
решая 2-3 получил
$a \equiv 4 \pmod m$

Вы тут еще 1 случай пропустили. Правильно так (для 1-3):
$5a+b \equiv 3 \pmod m \wedge 7a+b \equiv 11 \pmod m \Rightarrow 2a \equiv 8 \pmod m$. А теперь в зависимости от того, делится ли $m$ на $2$ или нет соответственно имеем $a \equiv 1 \pmod {\frac{m}{2}} \vee a \equiv 1 \pmod m$, поскольку при сокращении сравнения на множитель сокращать надо с учетом того, делится ли $m$ на этот множитель или нет.

[spywebka]

всё стало еще хуже....