Proof involving invertible modulo and congruence modulo

[dpryor5]

Homework Statement

Prove the following statement, or provide a counterexample showing its falsity:

Let n be an integer greater than 1. For all a ∈ Z, if a is invertible mod n and there exists x ∈ Z such that
ax ≡ 0 (mod n), then x ≡ 0 (mod n).

Homework Equations

If a is invertible mod n, then there exists some integer s such that as ≡ 1 (mod n).

The Attempt at a Solution

I start with the following congruence relations:
as ≡ 1 (mod n)
ax ≡ 0 (mod n)

and I need to derive the following relation from them:
x ≡ 0 (mod n)

I've tried using different modular equivalences for the relations and doing modular arithmetic, but I can't seem to get rid of the s and a. I don't know if I'm approaching this problem in an entirely incorrect way, but I would appreciate a nudge in the right direction.

 

[Hurkyl]

How would you go about solving the system:

as=1
ax=0​

to demonstrate that x is zero?

 

[dpryor5]

Solving for a in the first equation, and substituting for it in the second.

The closest I've been able to get to a system like that is using the equivalence of a ≡ b (mod n) to a mod n = b mod n. Applying that to the two congruence relations I start with produces:

as mod n = 1 and
ax mod n = 0.

But, if I then use the definition of mod to get a system of equations such as as = nq + 1 for some integer q and ax = nt for some integer t, I've just introduced two new variables I have to eliminate in order to establish the conclusion.

I feel like I'm missing something really simple, but I can't get a grasp of it.

 

[Hurkyl]

Solving for a in the first equation, and substituting for it in the second.

Could you show me what you mean? It's not what I would have expected -- and I think you're omitting the particular detail I was trying to get you to say and think about.

I feel like I'm missing something really simple, but I can't get a grasp of it.

The "simple" thing is that you can do algebra with modular equations. Usually, it's simpler and more efficient than trying to replace them with integer equations (e.g. by replacing as=1 (mod n) with as = 1 + nq, as you did) -- you just have to be careful to do the algebra correctly, since there are a couple ways algebra behaves differently modulo n.


If you're unsure about doing it correctly, you can always convert to integer equations after you've figured out what needs to be done to solve the system, to be sure things work out.

 

[dpryor5]

Could you show me what you mean? It's not what I would have expected -- and I think you're omitting the particular detail I was trying to get you to say and think about.

as = 1 => a = 1/s
ax = 0 => (1/s)x = 0 => x = 0.

 

[Hurkyl]

(1/s)x = 0 => x = 0.

The important thing to think about is what you're doing in this step...

 

[spamiam]

Try starting with x = x \cdot 1 = \cdots.

 

[dpryor5]

The important thing to think about is what you're doing in this step...

This makes intuitive sense to me. n divides into a*s with a remainder of 1, whereas a*x is divisible by n. It follows necessarily that x is divisible by n. But, it feels like this reasoning has to be explained more concretely for a good proof. I've been unable to do this by converting the modular relations into integer equations. I'm not sure how to establish this with modular arithmetic.

 

[Hurkyl]

This makes intuitive sense to me. n divides into a*s with a remainder of 1, whereas a*x is divisible by n. It follows necessarily that x is divisible by n. But, it feels like this reasoning has to be explained more concretely for a good proof. I've been unable to do this by converting the modular relations into integer equations. I'm not sure how to establish this with modular arithmetic.

What is preventing you from doing nearly the exact same thing you did in post #5?