a, b, c, d are each relatively prime to n = ad - bc, and r and s are integers. Show ar + bs is a multiple of n iff cr + ds is a multiple of n.
Solution
d(ar+bs) - b(cr+ds) = (ad-bc)r = nr, so if (ar+bs) is a multiple of n, then so is b(cr+ds). But b is relatively prime to n, so (cr+ds) is a multiple of n. Similarly, if (cr+ds) is a multiple of n, then so is d(ar+bs) and hence (ar+bs).
© John Scholes
jscholes@kalva.demon.co.uk
1 Nov 2003
Last corrected/updated 1 Nov 03