1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proof by logic

  1. Feb 21, 2005 #1
    I'm supposed to prove that if:
    n^2 % 3 = 0
    Then
    n % 3 = 0

    I'm not sure how to proceed here?

    Does it got something to do with setting n^2 to x?
    x % 3 = 0
    and
    \frac{x}{n} % 3 = 0

    Not sure how that helps..

    The actual problem is to prove that if n^2 / 3 is a whole number, then n/3 is also a whole number. But, I can't figure out any other way to present it.
     
    Last edited: Feb 21, 2005
  2. jcsd
  3. Feb 21, 2005 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Seems like that was good enough...

    Assuming that [itex]n[/itex] is a whole number, we can apply the fundemental theorem of algebra, so [itex]n[/itex] has a unique prime factorization:
    [tex]n=p_1^{a_1}\times p_2^{a_2}...[/tex]
    Where all the [itex]p_i[/itex] are primes, and all the [itex]a_i[/itex] are whole numbers. Then [itex]n^2[/itex] has the following prime factorization:
    [tex]n^2=p_1^{2a_1} \times p_2^{2a_2}...[/tex]

    Should be pretty easy from there...
     
  4. Feb 21, 2005 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Work from the other side. If n is not a multiple of 3 (i.e. if n/3 is not a whole number), then n must be of the form n= 3m+1 or n= 3m+2 for some whole number m.

    Now square them: n2= (3m+1)2= 9m2+ 6m+ 1=
    3(3m2+ 2m)+ 1. In other words, it is a multiple of 3 plus 1, not a multiple of 3.

    if n= 3m+2, then n2= (3m+2)2= 9m2+ 12m+ 4=
    3(3m2+ 4m+ 1)+ 1. Again, it is not a multiple of 3.

    Okay, if n is not a multiple of 3, then n2 cannot be. What does that tell you about the case if n2 is a multiple of 3?
     
  5. Feb 21, 2005 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Or use the alternative characterizations of the primes:

    p divides ab iff p divides either a or b.

    Let =3, a=b=n
     
  6. Feb 21, 2005 #5
    I can't use prime factorization, since that is in a later chapter.

    Doesn't this give me:
    p = n^2 is even
    q = n is even
    (in logic, don't know the latex for it)
    if NOT q then NOT p

    How does this prove:
    if q then p

    I tried working with the implication law, but can't seem to figure out how you get there. Or is this just some common law of logic?
     
  7. Feb 21, 2005 #6
    HallsOfIvy's method gives you:
    p = n^2 is divisible by 3
    q = n is divisible by 3
    if NOT q then NOT p

    It doesn't, but it proves if p then q... Which is what you originally wanted, no?
     
  8. Feb 21, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You could exhaust over the possibilities for n % 3.
     
  9. Feb 22, 2005 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    "Doesn't this give me:
    p = n^2 is even
    q = n is even"

    Well, no- the "negation" of "n is a multiple of 3" is not "n is even"!

    It is a "law of logic" that "if p then q" is equivalent to "if not q then not p". That's called the contrapositive and is a special case of "proof by contradiction".
     
  10. Feb 28, 2005 #9
    Thanks guys,

    this actually helped me to solve a couple of other problems(proving the contrapositive that is). :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proof by logic
  1. Logic proof (Replies: 2)

  2. Logic in proofs question (Replies: 17)

  3. Proof logic, question (Replies: 5)

Loading...