# Solving system of quadratic congruences

If you have a system ex:

$ab \equiv 1 \mod 9$

$ab \equiv 3 \mod 10$

$ab \equiv 10 \mod 11$

$ab \equiv 7 \mod 12$

is there a way to determine integers $a$ and $b$?

-

## 1 Answer

The short answer is "No" - you can use the Chinese remainder theorem to find the equivalence class of $ab \pmod{d}$, where $d$ is the lcm of your moduli, but you cannot find the values of $a$ and $b$ individually.

For example, the congruence $ab \equiv 1 \pmod{9}$ has several solutions, as does $ab \equiv 3 \pmod{10}$. You can deduce that $ab \equiv 73 \pmod{90}$, but there will be many possible pairs of values for $a$ and $b$ which will make this true.

-
Is there a way to use trial guessing or something of that sort? – Sid Jan 9 '13 at 20:45
If you look at $ab \equiv 1 \pmod{9}$, you can take $a$ to be any number which is not equivalent to $0 \pmod{9}$, and then find a value of $b$ which works. – Old John Jan 9 '13 at 20:47
Does increasing the number of congruencies decrease the possible ab? – Sid Jan 9 '13 at 20:47
*i mean pairs (a,b) – Sid Jan 9 '13 at 20:48
Assuming $ab$ and $d$ are relatively prime, $a$ could be anything relatively prime to $d$, and then $b \equiv (ab) a^{-1} \mod d$. – Robert Israel Jan 9 '13 at 20:52