| Thread Closed |
solutions to na=0 (mod m) |
Share Thread | Thread Tools |
| Apr2-09, 11:37 PM | #1 |
|
|
solutions to na=0 (mod m)
Given n and m positive integers, how can I find all the solutions to na=0 (mod m)??
|
| Apr3-09, 06:45 AM | #2 |
|
|
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. |
| Apr3-09, 06:51 AM | #3 |
|
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. |
| Apr3-09, 10:18 AM | #4 |
|
|
solutions to na=0 (mod m)
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]. |
| Apr3-09, 12:11 PM | #5 |
|
|
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. |
| Thread Closed |
| Thread Tools | |
Similar Threads for: solutions to na=0 (mod m)
|
||||
| Thread | Forum | Replies | ||
| Congruence difficulty | Linear & Abstract Algebra | 1 | ||
| Congruence - subject difficulty | General Math | 0 | ||
| Congruence | Precalculus Mathematics Homework | 3 | ||
| solution to the general congruence | Linear & Abstract Algebra | 2 | ||
| congruence help | Linear & Abstract Algebra | 5 | ||