Банальная задача. Подбор множителя.

[Ascar]

Наверное такой вопрос задавали 1000 раз
Приношу заранее свои извенения

Дано уравнение вида

$k \cdot Z+t$

и известно число $y$ где $y<k$ и $t<k$

Все числа положительные целые, все известны кроме значения числа $Z$

Задача - наити первое (или любое) значение целого числа $Z$
что бы выполнялось условие

$(k \cdot Z+t) \mod y = 0$

Например
Дано

$27263 \cdot Z+1$
и значение $y = 9553$

методом прямого перебора (от 1 и до..... ) находим $Z = 349$

$(27263 \cdot 349+1) \mod 9553 = 0$
-----------
Вопрос, можно ли както быстро находить значение $Z = 349$, не перебором

[3D Homer]

Для решения этого уравнения достаточно найти обратный к $k$ по модулю $y$. Это можно сделать с помощью расширенного алгоритма Евклида (см. [url]http://ru.wikipedia.org/wiki/Соотношение_Безу#Следствия[/url]), если $k$ и $y$ взаимно простые, как в описанном случае. Все остальные операции (сложение, вычитание, умножение) выполняются по модулю $y$, то есть берется остаток от результата при делении на $y$.

[Ascar]

3D Homer в сообщении #1545689 писал(а):

Для решения этого уравнения достаточно найти обратный к $k$ по модулю $y$. Это можно сделать с помощью расширенного алгоритма Евклида (см. [url]http://ru.wikipedia.org/wiki/Соотношение_Безу#Следствия[/url]), если $k$ и $y$ взаимно простые, как в описанном случае. Все остальные операции (сложение, вычитание, умножение) выполняются по модулю $y$, то есть берется остаток от результата при делении на $y$.

спасибо большое, давно не читал теории :) но это то что нужно, буду читать и разбирать
да действительно забыл написать что $k$, $t$ и $y$ все взаимно простые.... это одно из условий

[nnosipov]

Ascar в сообщении #1545713 писал(а):

давно не читал теории :)

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