Results 1 to 2 of 2

Thread: 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
    10
    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: Dec 11th 2011, 06:30 AM
  2. ODE Proof: Solution to this will always exist?
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: Oct 10th 2010, 05:33 AM
  3. Replies: 6
    Last Post: Jan 21st 2009, 02:13 PM
  4. Replies: 3
    Last Post: Sep 16th 2007, 05:57 PM
  5. solution please...can anyone show the proof...
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jul 19th 2006, 07:12 PM

Search Tags


/mathhelpforum @mathhelpforum