# Solving MultiVariable Congruences

• Jul 8th 2012, 03:01 PM
Nizbel99
Solving MultiVariable Congruences
Hello Everyone,

This is my first post here in this forum, so I look forward to discussing things with everyone here. But for now, I have a little problem. I know that to solve a single linear congruence, once can use the Extended Euclidean Algorithm, and to solve a system of linear congruences, one can use the CRT. However, I believe that these only work with one variable.

I have the following two congruences:
$
s_1 = k^{-1}(m_1 + a r_1) \mod q \\
s_2 = k^{-1}(m_2 + a r_2) \mod q
$

If all of the variables are known (but k and a), how do I go about on solving this? I tried eliminating k, but then I obtain this messy non-linear congruence, that I don't know how to solve as well. I would also like to point out that this isn't for a math course, but a CS course involving a little cryptography... so I'm guessing the solution shouldn't be to complicated.

Thanks!

EDIT: I am looking for a general procedure/algorithm for solving something like this. The goal of the question is to show that even if someone does not know k, he can still determine the value of a ( for a CS security/cryptography course). If more info is needed, I would be glad to provide.