Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By johng

Math Help - divisibility

  1. #1
    Junior Member
    Joined
    Apr 2013
    From
    palestine
    Posts
    29
    Thanks
    6

    divisibility

    help please

    prove that if n natural , 2 does not divide n ,3 does not divide n

    then 24 divides n^2 -1
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    688
    Thanks
    281

    Re: divisibility

    Hi,
    The problem is easy if you know about the multiplicative group of integers mod 24. See Multiplicative group of integers modulo n - Wikipedia, the free encyclopedia.

    Alternatively, for n less than 24, n=1, 5, 7, 11, 13, 17, 19 or 23 are the values prime to 24. By direct calculation each of these satisfy n2 is congruent to 1 mod 24. So any natural number n prime to 24 is congruent to one of these and you're done.
    Thanks from abualabed
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: divisibility

    A slightly less abstract formulation than johng's:

    if 3 does not divide n, then n = 3m + 1, or 3m + 2 for some integer m.

    Case 1: n = 3m + 1.

    Then n2 - 1 = (3m + 1)2 - 1 = 9m2 + 6m + 1 - 1 = 3(3m2 + 2), which is divisible by 3.

    Case 2: n = 3m + 2.

    Then n2 - 1 = (3m + 2)2 - 1 = 9m2 + 12m + 4 - 1 = 3(3m2 + 4m + 1), also divisible by 3.

    So in all cases, we have n2 - 1 is divisible by 3.

    Almost there: we now need to show that 8 divides n2 - 1, and since gcd(3,8) = 1, this will show 24 divides n2 - 1.

    Now since 2 does not divide n, n is odd. Thus n - 1 and n + 1 are both even. One of these must be divisible by 4:

    If n - 1 is not divisible by 4, since it is even, it must be of the form n - 1 = 4k + 2. In that case, n + 1 = n - 1 + 2 = 4k + 2 + 2 = 4(k + 1).

    Since one factor of n2 - 1 is a multiple of 4, and the other is even, their product is a multiple of 8. Thus 8 divides n2 - 1, and we are done.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility by 9
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: August 28th 2010, 06:18 AM
  2. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 03:41 AM
  3. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 05:44 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 04:53 AM
  5. Divisibility 7
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 18th 2008, 03:04 PM

Search Tags


/mathhelpforum @mathhelpforum