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

Help: modular arithmetic

  1. Sep 28, 2006 #1
    hi,

    i have started "self-studying" number theory. and since i am quite new to number theory and modular arithmetic, i need some help.
    how can i prove that if a2 ≡ 0 (mod n), then a ≡ 0 (mod n).

    thanks in advance to anybody who can help.
     
    Last edited: Sep 28, 2006
  2. jcsd
  3. Sep 28, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You can't, because it is false. Find a simple counter example.
     
  4. Sep 28, 2006 #3
    well, i was trying to prove that [tex]\sqrt n[/tex] is irrational if n is not a perfect square. i assumed that it is rational and
    [tex]\sqrt n[/tex] = [tex]{a}\over{b}[/tex] where gcd(a,b) = 1.
    then [tex]a^2 = nb^2[/tex]

    now n divides a2. if only i could prove that n divides a, then i could put a = nk and get
    [tex]n^2k^2 = nb^2[/tex]

    [tex]nk^2 = b^2[/tex]

    and now n divides b2. now if n divides b then n divides both a and b. thus gcd(a,b) is not 1 as it was assumed.

    but how can i prove it? since n divides a2 doesnt imply n divides a.
     
    Last edited: Sep 28, 2006
  5. Sep 28, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Just think about the prime decompostion of n. It suffices to assume that n is square free (i.e. no prime divides n more than once).
     
  6. Sep 28, 2006 #5
    so if a prime divides n once and n divides a2, then that prime divides a2 twice. hence that prime divides a once. is that it?
     
  7. Sep 28, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No. That is not it. It is true that if p divides a^2 that p^2 divides a^2, but it if you assume that you are assuming the result. You want to prove that fact.
     
  8. Sep 28, 2006 #7
    could you please elaborate?
     
  9. Sep 28, 2006 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How have you decided p^2 divides a^2? You have either got a circular argument or an unnecessary step.

    The definition of prime is p is prime if p|ab implies p|a or p|b, by the way. (You should prove this is equivalent to your definition if yours is different.)
     
  10. Sep 28, 2006 #9
    ok, then can you please help me with the proof that [tex]\sqrt n[/tex] is irrational if n is not a perfect square?
     
    Last edited: Sep 29, 2006
  11. Sep 28, 2006 #10
    Are with you familiar with the usual argument for why, say, [itex]\sqrt{p}[/itex] is irrational when [itex]p[/itex] is prime?

    This can be reduced to the same thing. You can decompose any positive integer [itex]n[/itex] into the product of a squarefree integer and a perfect square (note that 1 is a squarefree integer AND a perfect square), which is what matt meant by "it is sufficient to assume n is squarefree." Try to use that to prove it.
     
  12. Sep 28, 2006 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Your line of argument is perfectly fine as long as you take care with it. There are all manner of fussy ways of writing it, but it suffices to assume that n is square free (and not equal to 1). Then if n=a^2/b^2, and p is a prime that divides n we reach an obvious contradiction along the lines you've discussed.
     
  13. Sep 30, 2006 #12
    ok tell me if this is right:
    if a prime p divides a2, then p2 also divides a2. and since p2 divides a2, i.e., p.p divides a.a, then p divides a. am i correct?
     
  14. Sep 30, 2006 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    How are you concluding that p^2 divides a^2 if p divides a^2? I only ask, again, because the usual way of proving this fact is to prove that p divides a by the definition of primeness. So as I am now saying for the third time you are either using a circular argument or you're doing something unnecessary.


    The fact that 'if divides a^2 then p divides a' is an immediate consequence of the (proper) definition of prime, as I have, again, already told you.

    The result is not true for non-primes, and at no point do you explain why p being prime is important, so no, this is not sufficient proof, in my opinion.
     
    Last edited: Sep 30, 2006
  15. Oct 1, 2006 #14
    suppose the prime decomposition of a = p1.p2....pn.
    then a2 = p12.p22....pn2.

    now, if pk divides a2, then pk2 also divides a2.

    and if pk2 divides a2, i.e., if pk.pk divides a.a, then pk divides a.
     
    Last edited: Oct 1, 2006
  16. Oct 1, 2006 #15

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You are assuming that prime factorization is unique, then, but not bothering to say so. That is bad: your proof is flawed.

    If p divides ab then p divides a or b is the definition of prime so use to, for pity's sake.
     
  17. Oct 2, 2006 #16
    isn't that the fundamental theorem of arithmetic? i am not assuming it. i know that it is true.
     
  18. Oct 2, 2006 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Ok, I'm going to give up flogging this dead horse and leave you with a repeat of what I've been saying all along: your argument is too long and relies on unstated results, and now that you have stated them we see it is circular. If you're going to use the fundamental theorem of arithmetic say you're using it. The fact that p divides a if p divides a^2 is a consequence of the definition of primeness. You do not need to invoke uniqueness of prime factorization to deduce it, and in fact this is circular logic beause the proof the the fundamental theorem of arithmetic is a consequence of a special case of the very result you're using the fundamental theorem of arithmetic to prove.
     
    Last edited: Oct 2, 2006
  19. Oct 2, 2006 #18
    thank you very much for this info. i couldn't understand before why you were saying "circular logic". now i see that my reasoning was indeed "circular". thanks once again.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help: modular arithmetic
  1. Modular arithmetic (Replies: 5)

  2. Modular arithmetic (Replies: 7)

Loading...