Thread: 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!!

Originally Posted by BlueAngel

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,...,n–1) must all be different (mod n), so one of them must be equal to 1 (mod n)