Proof involving invertible modulo and congruence modulo

  • Thread starter dpryor5
  • Start date
  • Tags
    Proof
In summary, the student is trying to solve a system of equations in order to demonstrate that x is zero, but is having difficulty doing so due to the presence of s and a.
  • #1
dpryor5
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:
Physics news on Phys.org
  • #2
How would you go about solving the system:
as=1
ax=0​
to demonstrate that x is zero?
 
  • #3
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
dpryor5 said:
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
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
dpryor5 said:
(1/s)x = 0 => x = 0.
The important thing to think about is what you're doing in this step...
 
  • #7
Try starting with [itex] x = x \cdot 1 = \cdots [/itex].
 
  • #8
Hurkyl said:
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
dpryor5 said:
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?
 

What is an invertible modulo?

An invertible modulo is a mathematical operation that involves finding the inverse of a number in a given modulus. This means finding a number that, when multiplied by the original number, results in a remainder of 1 when divided by the modulus.

How is invertible modulo used in proofs?

Invertible modulo is often used in proofs involving congruence modulo, which is the concept of two numbers having the same remainder when divided by a given modulus. It allows for the manipulation of equations involving modular arithmetic to prove certain statements.

What are the key properties of invertible modulo?

The key properties of invertible modulo are:

  1. The existence of an inverse for every number in a given modulus
  2. The commutative property, meaning the order of the numbers in the operation does not affect the result
  3. The associative property, meaning the grouping of numbers in the operation does not affect the result
  4. The distributive property, meaning the distribution of numbers in the operation does not affect the result

What is the difference between invertible modulo and congruence modulo?

Invertible modulo is a mathematical operation that involves finding the inverse of a number in a given modulus, while congruence modulo is a relation between two numbers that have the same remainder when divided by a given modulus. Invertible modulo is used in proofs involving congruence modulo to manipulate equations and prove statements.

How is invertible modulo related to modular arithmetic?

Invertible modulo is a key concept in modular arithmetic, which is a branch of mathematics that deals with numbers and their remainders when divided by a given modulus. It allows for the manipulation and solving of equations involving modular arithmetic, making it an important tool in many mathematical proofs and applications.

Similar threads

Replies
11
Views
368
  • Precalculus Mathematics Homework Help
Replies
5
Views
872
  • Precalculus Mathematics Homework Help
Replies
1
Views
864
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
4
Views
950
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
864
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Linear and Abstract Algebra
Replies
11
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
1K
Back
Top