Given n and m positive integers, how can I find all the solutions to na=0 (mod m)??
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.
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.
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 [itex]1\leq a \leq m[/itex].
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.
Separate names with a comma.