Results 1 to 2 of 2

Math Help - Proof ax=0 has a non-zero solution in (modn)

  1. #1
    Newbie
    Joined
    Mar 2009
    From
    With my Parents
    Posts
    4

    Proof ax=0 has a non-zero solution in (modn)

    I'm really not sure where to start with this one. The problem goes as follows:

    Let (a) be not equal to 0 in (mod n). Prove that ax=0 has a non-zero solution in (mod n) iff ax = 1 has a solution.

    I'm thinking a proof by contradiction, but really a starting point would be really helpful!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by BlueAngel View Post
    I'm really not sure where to start with this one. The problem goes as follows:

    Let (a) be not equal to 0 in (mod n). Prove that ax=0 has a non-zero solution in (mod n) iff ax = 1 has a solution.

    I'm thinking a proof by contradiction, but really a starting point would be really helpful!!
    That can't be correct. I think the question should read Let (a) be not equal to 0 in (mod n). Prove that ax=0 has a non-zero solution in (mod n) iff ax = 1 has no solution.

    To see how to prove that, notice that if ax=1 (mod n) and ay=0 (mod n) then y=(ax)y=x(ay)=0 (mod n). So ay=0 has no nonzero solution.

    Conversely, if ay=0 (mod n) has no nonzero solution then the n numbers az (for z=0,1,2,...,n1) must all be different (mod n), so one of them must be equal to 1 (mod n)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Second order ODE's, proof of solution method
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: December 11th 2011, 07:30 AM
  2. ODE Proof: Solution to this will always exist?
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: October 10th 2010, 06:33 AM
  3. Replies: 6
    Last Post: January 21st 2009, 03:13 PM
  4. Replies: 3
    Last Post: September 16th 2007, 06:57 PM
  5. solution please...can anyone show the proof...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: July 19th 2006, 08:12 PM

Search Tags


/mathhelpforum @mathhelpforum