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

Divisibility question

  1. Mar 9, 2009 #1

    kreil

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Suppose that [itex]n^2[/itex] is odd and that 3 does not divide [itex]n^2[/itex]. Show that [itex]12|(n^2-1)[/itex]


    2. Relevant equations
    none


    3. The attempt at a solution
    Well I know that since [itex]n^2[/itex] is odd, [itex]n^2-1[/itex] is even. I'm not sure what the next step would be.
     
  2. jcsd
  3. Mar 9, 2009 #2

    kreil

    User Avatar
    Gold Member

    hmm i did some more thinking on this. Please let me know if you think this is correct:

    - since [itex]n^2[/itex] is odd, [itex]n^2-1[/itex] is an even number and [itex]2|n^2-1[/itex]

    - [itex]n^2[/itex] is not prime since it has at least 3 divisors: {1, n, [itex]n^2[/itex]}

    - if 3 does not divide [itex]n^2[/itex], then the remainder of this division must be either 1 or 2 (a remainder of 3 implies that 3 does divide [itex]n^2[/itex]). However, the remainder cannot be 2 or else [itex]n^2[/itex] would be prime, therefore the remainder must be 1.

    - this implies 3|[itex]n^2-1[/itex] evenly, since the -1 cancels with the remainder on division with [itex]n^2[/itex].

    Since 2|[itex]n^2-1[/itex], 3|[itex]n^2-1[/itex] and [itex]12=2^2 3^1[/itex], it follows that 12|[itex]n^2-1[/itex].
     
  4. Mar 9, 2009 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi kreil! :smile:
    forget n2 :rolleyes:

    … what is the remainder if you divide n by 2 or 3? :wink:
     
  5. Mar 9, 2009 #4

    kreil

    User Avatar
    Gold Member

    n is odd

    so 2 divides into n with r=1

    3 divides into n with r=2 since r=1 implies n is even and r=0 or 3 implies 3 divides [itex]n^2[/itex]


    soo does this mean that 3 divides into [itex]n^2[/itex] with remainder [itex]r^2[/itex] (i.e. r=1)?
     
  6. Mar 9, 2009 #5

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    No it doesn't …

    what about 7? :wink:
     
  7. Mar 9, 2009 #6

    kreil

    User Avatar
    Gold Member

    oops, so 3|n with r=1 or r=2

    what does this mean?
     
  8. Mar 9, 2009 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    that's better! :smile:

    now you have the possible remainders for 2 and 3 …

    so … ? :wink:
     
  9. Mar 9, 2009 #8

    kreil

    User Avatar
    Gold Member

    so if 3|n with r=1 or r=2, then 3|[itex]n^2[/itex] with r=1 or r=4 and since if r=4 3|4 with r=1, 3|[itex]n^2[/itex] with r=1

    is that correct logic?
     
  10. Mar 9, 2009 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    wot's incorrect logic? :confused:

    anyway, how can 3 divide anything with r = 4??
     
  11. Mar 9, 2009 #10

    kreil

    User Avatar
    Gold Member

    haha, this doesn't tell me very much about whether what i wrote was right or not...

    is it true that if 3|n with remainder r, that 3|[itex]n^2[/itex] with remainder [itex]r^2[/itex]??
     
  12. Mar 9, 2009 #11

    kreil

    User Avatar
    Gold Member

    i now know that this problem reduces to the problem of showing that 3|[itex]n^2[/itex] with r=1, i just don't understand how to connect division of n by 2 and 3 to this..
     
  13. Mar 9, 2009 #12

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hint: 6

    and i'm going to bed :zzz:​
     
  14. Mar 9, 2009 #13

    kreil

    User Avatar
    Gold Member

    i dont understand how to make the next step to saying 6|n rem 1..

    i think i'm missing something here
     
  15. Mar 9, 2009 #14

    kreil

    User Avatar
    Gold Member

    for ex if n is 11,

    2|11 rem 1

    3|11 rem 2

    6|11 rem 5...

    BUT 6|121 rem 1
     
  16. Mar 9, 2009 #15

    kreil

    User Avatar
    Gold Member

    i am so lost on this now...
     
  17. Mar 10, 2009 #16

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    just got up :zzz: …

    what are the possible remainders on dividing by 6? :smile:
     
  18. Mar 10, 2009 #17

    kreil

    User Avatar
    Gold Member

    because of the condition 0<r<6 for the equation n = 6b + r for some b, r can be 1,2,3,4,5.
     
  19. Mar 10, 2009 #18

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    uhh? :confused: but n2 is odd and 3 does not divide n2.
     
  20. Mar 10, 2009 #19

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    tiny tim is pointing you at the Chinese remainder theorem.


    But let's try a different way.

    n is odd, so n=2m+1 for some m. Now what divides n^2-1?

    n is not divisible by 3, so either n=3r+1 or 3r+2. In either case, what can you show divides n^2-1?

    Equivalently, n^2-1 is congruent to what mod what and what? (insert useful things instead of 'what' in that sentence.)
     
  21. Mar 10, 2009 #20

    kreil

    User Avatar
    Gold Member

    [itex]n^2=(2m+1)(2m+1)=4m^2+4m+1 \implies n^2-1=4(m^2+m)[/itex] for some m, and 4|[itex]n^2-1[/itex]

    [itex]n^2=9r^2+6r+1[/itex]

    or [itex]n^2=9r^2+6r+4[/itex]

    so [itex]n^2-1=9r^2+6r=3(3r^2+2r)[/itex]

    or [itex]n^2-1=9r^2+6r+3=3(3r^2+2r+1)[/itex]

    and in both cases 3|[itex]n^2-1[/itex]

    so [tex]n^2-1=(3r^2+2r)(mod 3) [/tex] and [tex]n^2-1=(3r^2+2r+1)(mod 3)[/tex]??
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook