InteractiveMind
asked on
Modulo arithmetic problem
Let a,b,c be pairwise-coprime integers. I need to find the smallest integer t satisfying
at+b=0 (mod c)
Any ideas? I keep thinking something along the lines of the Euclidean algorithm except the modulo complicates things.
Thanks in advance.
at+b=0 (mod c)
Any ideas? I keep thinking something along the lines of the Euclidean algorithm except the modulo complicates things.
Thanks in advance.
ASKER
Indeed. Unfortunately though, these numbers could be very large so I require a deterministic approach.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
I just did it. (wasted my time?, gah)
A, B & C relatively prime
Find
Ax + B = 0 mod C
Using Euclids algorithm since A & C coprime then there is m & n st
mA + nC = 1
Multiplying both sides by B
(mB)A + (nB)C = B
(-mB)A + B = (nB)C
(-mB)A + B = 0 mod C
(-mB mod C)A + B = 0 mod C
eg
5x + 7 = 0 mod 9
By Euclid
2*5 - 9 = 1
14* 5 - 63 = 7
(-14)* 5 + 7 = 0 mod 9
(-14 mod 9)* 5 + 7 = 0 mod 9
4*5 + 7 = 0 mod 9
x = 4
A, B & C relatively prime
Find
Ax + B = 0 mod C
Using Euclids algorithm since A & C coprime then there is m & n st
mA + nC = 1
Multiplying both sides by B
(mB)A + (nB)C = B
(-mB)A + B = (nB)C
(-mB)A + B = 0 mod C
(-mB mod C)A + B = 0 mod C
eg
5x + 7 = 0 mod 9
By Euclid
2*5 - 9 = 1
14* 5 - 63 = 7
(-14)* 5 + 7 = 0 mod 9
(-14 mod 9)* 5 + 7 = 0 mod 9
4*5 + 7 = 0 mod 9
x = 4
ASKER
I solved it.
ASKER
Gwynfor, I only just saw your solution now by chance. My points-bag is empty but thank you for the effort.
Open in new window