• Support PF! Buy your school textbooks, materials and every day products Here!

Proof involving invertible modulo and congruence modulo

  • Thread starter dpryor5
  • Start date
  • #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:

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
How would you go about solving the system:
as=1
ax=0​
to demonstrate that x is zero?
 
  • #3
4
0
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.
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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.
 
  • #5
4
0
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.
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
(1/s)x = 0 => x = 0.
The important thing to think about is what you're doing in this step....
 
  • #7
360
0
Try starting with [itex] x = x \cdot 1 = \cdots [/itex].
 
  • #8
4
0
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.
 
  • #9
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
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?
 

Related Threads on Proof involving invertible modulo and congruence modulo

  • Last Post
Replies
7
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
4K
Replies
2
Views
4K
  • Last Post
Replies
6
Views
6K
  • Last Post
Replies
24
Views
2K
Top