См. теорию на e-maxx: расширенный алгоритм Евклида, обратный по простому модулю, линейные диофантовы уравнения, линейное уравнение по модулю китайская теорема об остатках.