congruence

[quasar987]

Given n and m positive integers, how can I find all the solutions to na=0 (mod m)??

[ThirstyDog]

If na = 0 (mod m) then na = km for some k. To find all a consider d = gcd(n,m), if we let a = m/d * l for l any positive integer then a is guaranteed to be an integer as d divides m and as d divides n we must have na = m * (n*l/d) which implies na is a integer multiple of m.

I assume that a = m/d is the smallest a allowed as d is the greatest common divisor and I don't want to think of a proof.

[ramsey2879]

solve an = mt

PS the congruence relation m/n does not work since n does not have to be a divisor of m, eg 11/5 = 9 mod n since 9*5 = 1 mod n, but the congruence relation m/gcd(m,n)*t mod m works. as m/1 is the solution for a in that case. (Re the t If a = 2 is a solution to m = 14, n = 7 so are 4,6,8,10.12 and 14)

Sorry but Thirsty Dog gave the correct solution before me.

[quasar987]

Thanks for the reply guys.

However, I had already figured out that all elements of the form a = m/d * l (ThirstyDog's notation) are solutions. What remains for me to do is prove that these are the only solutions.

Also, I actually only interested in solutions mod m... that is, solutions such that 1\leq a \leq m.

[quasar987]

Ok, I found the solution in a book.

Write m=pd and n=qd (where d=gcd(m,n)) and notice that p and q are relatively prime, otherwise, d would not be the greatest common divisor of m and n.

And then it's easy: we have that m|an <==>pd|aqd <==>p|aq <==> p|a.

So the solutions are all the multiples of p.