How Can You Prove Zero Product in Modular Arithmetic for Composite Numbers?

[dancergirlie]

Homework Statement

If n is composite, prove that there exist a,b in Zn such that a and be are nonzero, but ab=0

Homework Equations

if a is congruent to b mod n, then n divides (a-b)

The Attempt at a Solution

So this is what i have so far, please let me know if i am on the right track, and if i am then where would i go next?

Suppose n is composite and a,b are in Zn where ab=0
which means,
ab is congruent to 0(mod n)
where n divides ab
*this is where i get stuck, I'm thinking i have to say something about n having a unique prime number factorization, but i don't know how to show that in my proof...

any help/hints would be great =)

Thanks!

 

[Mark44]

Let's think about this a bit less abstractly. Suppose you're dealing with Z10. I can think of two nonzero numbers in Z10, a and b, such that a*b = 0 mod 10.

In Z5, there aren't any numbers that do this.

 

[dancergirlie]

I understand the concept that there exists these numbers, but i don't know how to show that in my proof without using examples (which I'm not allowed to do). So, i was wondering if i could just say that there are non-zero primes that factorize n, which would mean that a is nonzero and b is also nonzero... I'm just so lost...

 

[Mark44]

I provided the examples just to get you thinking about the problem, not as suggestions for proofs. Sometimes students get so tangled up in the symbolism, they lose track of what the symbolism means.

Think about why it is that if n is composite, Zn can have nonzero elements that act the same way that zero does in multiplication. And if n is prime, Zn won't have any such elements.

You said this:

Suppose n is composite and a,b are in Zn where ab=0
which means,
ab is congruent to 0(mod n)
where n divides ab

You're starting at the conclusion you're supposed to reach (ab=0) and working from there. You need to start at your hypothesis (n is composite and a and b are in Zn) and work from there to the conclusion.

 

[daveyinaz]

Mark44 is giving you good direction...

You need to start with Zn and let n be composite. Then are there numbers in the set Zn, such that when they are multiplied and mod n..it results in 0. Which two numbers are they?

 

[dancergirlie]

ok... so if i just use the hypothesis n is composite and a and b are in zn, then how would i start my proof?

should i try a proof by contradiction by assuming that ab=0 where a or b=0 and finding a contradiction?

 

[Mark44]

No, just go through directly.

Maybe I'm wrong, but I'm not sure you understand my examples, yet. If you don't understand these concrete examples, you'll never be able to put together a proof that is more abstract.

Going back to my two examples:
In Z10 I can think of two nonzero numbers, a and b, where a*b = 0 mod 10? What are they? There are only two.
In Z5, are there any nonzero numbers a and b for which a*b = 0 mod 5?

 

[daveyinaz]

You do know that Z10 is { 0, 1, 2, ... , 9 } correct?

In that case, let x and y be two different numbers in Z10...what values for x and y will give you 0 when multiplied and modded by 10?

You should notice the importance of the two numbers you selected for x and y...then it happens to be the case in general...that is for any composite number.

 

[dancergirlie]

I understand the concrete examples, i do. The two numbers would be 5 and 2, both of which are prime numbers. I know that the product of two prime numbers equals a composite number. I can do any non-abstract example, i just don't know how to show that using a non-concrete example.

 

[daveyinaz]

Let n be a composite number. Then Zn contains the prime factors of n (since all of them are < n). Moreover, when you multiply the prime factors and mod by n the result is 0.

 

[Mark44]

I understand the concrete examples, i do. The two numbers would be 5 and 2, both of which are prime numbers. I know that the product of two prime numbers equals a composite number. I can do any non-abstract example, i just don't know how to show that using a non-concrete example.

But what is (5 * 2) mod 10? That's the part I don't think you're seeing.

 

[dancergirlie]

i know that 10 is congruent to 0(mod 10), because 10 divides 10-0
meaning 5*2 is congruent to 0(mod 10)
so i know that a can equal 5 and b can equal 2

 

[Mark44]

OK, now let's look at it more generally.
Consider Zn where n is a composite. Are there nonzero numbers a and b such that a*b = 0 mod n? If so, what are they? If not, why not?

 

[HallsofIvy]

Your proof should start with the hypothesis: if n is composite, then---

What follows immediately from the definition of "composite"?

 

[dancergirlie]

ok, i attempted to redo this, let me know if this is better or if i am skipping any steps...

Suppose [n] is composite and [a] and are integers in Zn.

So, there exists a prime factorization of [n] so that [n]=[p1][p2]...[pn] for [n]>1
Let [a]=[p1][p2]...[pn]
meaning,
[a]=[n]
hence,
ab is congruent to 0(mod n)
and therefore, [a]=[0]
where [a] and are unequal to zero because they are prime factors.

 

[Mark44]

Why do you have most everything in brackets?

You're asked to prove that there exist nonzero numbers a and b in Zn such that a*b [itex]\equiv [/itex] 0 mod n.
I don't see that you have shown that there are any such numbers.
You have "Let [a] = [p1][p2]...[pn]"
Give me two numbers, a and b.
The proof is actually very simple and doesn't require much in the way of supporting statements.

 

[daveyinaz]

...why do i think you copied that from somewhere?...

plus i think she's referring to equivalence classes or something...which is another reason for my thoughts..

 

[Mark44]

...why do i think you copied that from somewhere?...

Who is this addressed to?

plus i think she's referring to equivalence classes or something...which is another reason for my thoughts..

That would be my thought, but I think the problem can be done with a minimal use of them.

 

[daveyinaz]

Who is this addressed to?

the OP

 

[dancergirlie]

wait, what... i didn't copy it from anywhere lol, i just wrote it myself. Is that the correct way to do it though? i use the brackets to show the equivalence classes

 

[dancergirlie]

also to mark: I can't just say that the two numbers are prime and that be my proof, i wouldn't get any points for that. I know that the product of two prime numbers is congruent to 0 mod n, where n is a composite number. I know that 5 and 2 are nonzero for the example 5*2 is congruent to 0(mod n)
which would mean that 5*2=0 for Zn.

Also, my professor said we need to write out the equivalence classes or we will get points taken off. So the only time i am allowed to not use the equivalence brackets would be for when I'm making a congruence statement

 

[Mark44]

No, I didn't say anything about the two numbers being prime, although my example for Z10 might have appeard that way. If you're dealing with, Z36, say, where n = 36, there are several pairs of factors that are nonprime, namely 4*9, 6*6, and 3*12. In all three of these cases I have exhibited pairs of nonzero numbers a and b for which a*b = n [itex]\equiv [/itex] 0 mod n, so a*b = [0] (if I'm using the equivalence class notation correctly).

You have n broken up into prime factors, so you should be able to demonstrate the existence of an a and a b by specifying them.

 

[HallsofIvy]

You still haven't used the definition of "composite"! If n is composite, then by definition of "composite" there exist integers, a, b, such that n= ab. That tells you immediately that ab is congruent to 0 mod n. You don't need anything more complicated than that.