Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Solutions to na=0 (mod m)

  1. Apr 2, 2009 #1

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Given n and m positive integers, how can I find all the solutions to na=0 (mod m)??
     
  2. jcsd
  3. Apr 3, 2009 #2
    Re: congruence

    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.
     
  4. Apr 3, 2009 #3
    Re: congruence

    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.
     
    Last edited: Apr 3, 2009
  5. Apr 3, 2009 #4

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: congruence

    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].
     
  6. Apr 3, 2009 #5

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Re: congruence

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Solutions to na=0 (mod m)
  1. Ab ≡ 0 (mod N) (Replies: 1)

Loading...