Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular Arithmetic Proof

  1. Feb 12, 2009 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

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

    3. 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 =)

  2. jcsd
  3. Feb 12, 2009 #2


    Staff: Mentor

    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.
  4. Feb 12, 2009 #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...
  5. Feb 12, 2009 #4


    Staff: Mentor

    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:
    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.
  6. Feb 12, 2009 #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?
  7. Feb 12, 2009 #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?
  8. Feb 12, 2009 #7


    Staff: Mentor

    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?
  9. Feb 12, 2009 #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.
  10. Feb 12, 2009 #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.
  11. Feb 12, 2009 #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.
  12. Feb 12, 2009 #11


    Staff: Mentor

    But what is (5 * 2) mod 10? That's the part I don't think you're seeing.
  13. Feb 12, 2009 #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
  14. Feb 12, 2009 #13


    Staff: Mentor

    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?
  15. Feb 13, 2009 #14


    User Avatar
    Science Advisor

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

    What follows immediately from the definition of "composite"?
  16. Feb 13, 2009 #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]
    ab is congruent to 0(mod n)
    and therefore, [a]=[0]
    where [a] and are unequal to zero because they are prime factors.
  17. Feb 13, 2009 #16


    Staff: Mentor

    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.
  18. Feb 13, 2009 #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..
  19. Feb 13, 2009 #18


    Staff: Mentor

    Who is this addressed to?
    That would be my thought, but I think the problem can be done with a minimal use of them.
  20. Feb 13, 2009 #19
    the OP
  21. Feb 13, 2009 #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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook