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!

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]??
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Divisibility question
  1. Divisibility Questions (Replies: 5)

Loading...