Recognitions:
Gold Member
Homework Help

## solutions to na=0 (mod m)

Given n and m positive integers, how can I find all the solutions to na=0 (mod m)??
 PhysOrg.com science news on PhysOrg.com >> King Richard III found in 'untidy lozenge-shaped grave'>> Google Drive sports new view and scan enhancements>> Researcher admits mistakes in stem cell study
 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.
 Blog Entries: 2 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.

Recognitions:
Gold Member
Homework Help

## solutions to na=0 (mod m)

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