Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.