- #1

- 4

- 0

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

Last edited: