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
    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
    \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


    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


    User Avatar
    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


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

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


    User Avatar
    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). :)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook