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).
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.