Help With Proving a is Zero Divisor Mod n iff gcd(a,n)>1

  • Thread starter SomeRandomGuy
  • Start date
  • Tags
    Proof
In summary, to prove that a number a is a zero divisor mod n, it is necessary and sufficient for gcd(a,n) to be greater than 1. The proof for this involves showing that if gcd(a,n) > 1, then a is a zero divisor mod n, and vice versa. This can be done by considering the integer n/gcd(a,n) and showing that it is not divisible by n, thus making a a zero divisor mod n. Additional resources, such as the mathematics reference desk on Wikipedia, can be helpful in understanding and solving this proof.
  • #1
SomeRandomGuy
55
0
Prove that a number a is a zero divisor mod n iff gcd(a,n)>1.

I have the proof assuming a is a zero divisor mod in => gcd(a,n)>1. However, going in the other direction has me stumped. Basically, here is all I have so far that I feel is correct:

Assume gcd(a,n)=d>1
=> da' = a and dn' = n and if x|a and x|n => x|d
Thus, there exists w,z where aw + nz = d
=> aw = d mod n.

I've tried subbing in from here. in a few different ways but I feel like it just leads me into a brick wall. Ultimately, I'm looking to get aw = 0 mod n which makes a a zero divisor.
 
Physics news on Phys.org
  • #2
nevermind, I believe I solved it
 
  • #3
I hope this would be helpful

ok,i asked some mathematicians and they replied with this:Think about n/gcd(a,n) - let's call this b. First of all, you can be sure that b is an integer - why ? Secondly, you can be sure that if gcd(a,n) > 1 then b mod(n) is not 0 - why ? Now think about the product ab - what is ab mod(n) ? How does this help you show that a is a zero divisor mod(n) ?p.s:you can finde more help on http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Mathematics
 

FAQ: Help With Proving a is Zero Divisor Mod n iff gcd(a,n)>1

1. What is a zero divisor modulo n?

A zero divisor modulo n is an integer a that, when multiplied by another integer b, results in a multiple of n (i.e. ab is divisible by n). In other words, a zero divisor modulo n is an element in a set of numbers that, when combined with other elements, produces a multiple of n.

2. What is the significance of proving that a is a zero divisor modulo n?

Proving that a number is a zero divisor modulo n is important because it helps to determine the structure and properties of the set of numbers modulo n. It also helps to identify the elements that are not invertible modulo n, which can be useful in solving certain mathematical problems.

3. How do you prove that a is a zero divisor modulo n?

To prove that a is a zero divisor modulo n, you must show that there exists an integer b such that ab is a multiple of n. This can be done by finding the greatest common divisor (gcd) of a and n, and showing that it is greater than 1. If the gcd(a,n) > 1, then a is a zero divisor modulo n.

4. What is the relationship between a zero divisor modulo n and the gcd of a and n?

The gcd of a and n is closely related to the concept of a zero divisor modulo n. In fact, it can be used to determine whether or not an integer a is a zero divisor modulo n. If the greatest common divisor of a and n is greater than 1, then a is a zero divisor modulo n.

5. Can a number be a zero divisor modulo n if its gcd with n is 1?

No, a number cannot be a zero divisor modulo n if its gcd with n is 1. This is because if the gcd(a,n) = 1, then a and n are relatively prime and do not share any common factors. This means that there is no integer b that can be multiplied by a to produce a multiple of n, making a not a zero divisor modulo n.

Similar threads

I Understanding the Results of gcd(x,n)
Replies
8
Views
1K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
Replies
3
Views
2K
MHB GCD of a and b: Proving $gcd(a',b')=1$
Replies
4
Views
1K
I Proof for subgroup -- How prove it is a subgroup of Z^m?
Replies
11
Views
2K
MHB Zero divisor for polynomial rings
Replies
1
Views
2K
MHB Zero Divisor Help: Prove & Example
Replies
1
Views
1K
U(n) as an External Direct Product
Replies
11
Views
1K
I Proof that if T is Hermitian, eigenvectors form an orthonormal basis
Replies
3
Views
2K
What is the proof for Byron's Conjecture? Define Znx and prove its properties.
Replies
3
Views
2K
Proving Linear Manipulation to Reduce to GCD of Two Numbers
Replies
6
Views
3K

Hot Threads

Recent Insights

Back
Top