Modular Arithmetic Proof

In summary: I mean, you know that Zn is not the set of equivalence classes, right?Your proof is incorrect. To prove that there exist nonzero numbers a and b in Zn such that a*b \equiv 0 mod n, you need to show that there are some numbers a and b in Zn for which the congruence holds.Let's start with a simple example. Consider the set Z10
  • #1
dancergirlie
200
0

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!
 
Physics news on Phys.org
  • #2
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.
 
  • #3
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...
 
  • #4
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.
 
  • #5
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?
 
  • #6
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?
 
  • #7
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?
 
  • #8
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.
 
  • #9
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.
 
  • #10
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.
 
  • #11
dancergirlie said:
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.
 
  • #12
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
 
  • #13
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?
 
  • #14
Your proof should start with the hypothesis: if n is composite, then---

What follows immediately from the definition of "composite"?
 
  • #15
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.
 
  • #16
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.
 
  • #17
...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..
 
  • #18
daveyinaz said:
...why do i think you copied that from somewhere?...
Who is this addressed to?
daveyinaz said:
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.
 
  • #19
Mark44 said:
Who is this addressed to?

the OP
 
  • #20
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
 
  • #21
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
 
  • #22
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.
 
  • #23
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.
 

1. What is modular arithmetic?

Modular arithmetic is a branch of mathematics that deals with the properties and operations of integers under a certain modulus. It is often used to solve problems involving remainders, cycles, and periodic patterns.

2. How is modular arithmetic used in proofs?

Modular arithmetic can be used in proofs to show that a statement or equation holds true for all integers within a certain modulus. This is done by using modular arithmetic properties and operations to manipulate the equation or statement until it is equivalent to the original one.

3. What are some common properties of modular arithmetic?

Some common properties of modular arithmetic include the distributive property, the commutative property, and the associative property. These properties allow for the manipulation of equations and statements within a given modulus.

4. Can modular arithmetic be used to prove divisibility?

Yes, modular arithmetic can be used to prove divisibility. For example, if a number is congruent to 0 modulo another number, then it is divisible by that number. This can be shown through various modular arithmetic proofs.

5. How is modular arithmetic used in cryptography?

Modular arithmetic is an essential tool in cryptography, particularly in the field of public key encryption. It is used to generate large prime numbers, which are then used to create encryption keys that are difficult to crack. Modular arithmetic is also used in the encryption and decryption algorithms themselves.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
24
Views
786
  • Calculus and Beyond Homework Help
Replies
2
Views
952
  • Calculus and Beyond Homework Help
Replies
27
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
684
  • Calculus and Beyond Homework Help
Replies
4
Views
227
  • Calculus and Beyond Homework Help
Replies
7
Views
405
  • Calculus and Beyond Homework Help
Replies
1
Views
504
  • Calculus and Beyond Homework Help
Replies
1
Views
569
  • Calculus and Beyond Homework Help
Replies
6
Views
370
Back
Top