Results 1 to 4 of 4

Math Help - Divisibility

  1. #1
    Newbie
    Joined
    Jan 2011
    Posts
    16

    Divisibility

    Was going through the divisibility chapter and stumbled across this excercise that kinda stumped me.

    Let a be and integer. prove that 3 \mid a(a + 1)(a + 2). (Hint: Consider three cases.)

    Now I see the answer as being evident. 3 divides or is a multiple of 1 of 3 consecutive numbers. a(a + 1)(a + 2) lists 3 consecutive number so 3 is definitely going to divide their product. I'm just lost on how exactly to write the proof ... I hate divisibility chapter. The entire section is riddled with things we take for granted but have a hard time proving Thanks for any help guys!

    (Small note: This section is prior to congruence or modulo so I'd like to avoid using those to prove it.)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Consider the integer a. There are three possibilities.

    Case 1: There is an integer k such that a=3k
    Case 2: There is an integer k such that a=3k+1
    Case 3: There is an integer k such that a=3k+2

    In case 1, a is divisible by 3.
    In case 2, a+2=(3k+1)+2=3k+3=3(k+1) so that a+2 is divisible by 3
    In case 3, a+1= (3k+2)+1=3k+3=3(k+1) so that a+1 is divisible by 3

    Notice that all I am using in this argument is the definition of divisibility by 3. If you understand he definition, then the argument is straightforward and almost obvious.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Dr. Steve has given you a rigorous proof, but I think it would also be acceptable to simply say that, of any three consecutive integers, one must be a multiple of three.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Nov 2010
    Posts
    193
    I suppose one could also use the Pigeonhole Principle to do something like this in general.

    Let a,a+1,a+2,\ldots,a+(n-1) be any n consecutive integers. We wish to show that at least one of them (well, really, exactly one of them) is divisible by n.

    Suppose that none of them were. Now, we know that, by the division algorithm, when you divide an integer by n, the remainder must be smaller than n; that is, the remainder upon division by n is in the set \{0,1,2,\ldots,n-1\}.

    Since we are assuming that none of the integers a,a+1,a+2,\ldots,a+(n-1) are divisible by n, we know that none of the remainders upon division by n is 0. So our possible remainders are 1,2,\ldots,n-1; there are n-1 possible remainders. But there are n numbers in our list; since there are more numbers than remainders, the Pigeonhole Principle says that at least two (different) numbers in our list have the SAME remainder upon division by n.

    Let these two numbers be a+i and a+j, where we assume 0\leq i<j\leq n-1. Suppose their remainder upon division by n is r, and using the division algorithm, write a+i=nq_1+r,a+j=nq_2+r, for some integers q_1,q_2. Then

    j-i=(a+j)-(a+i)=(nq_2+r)-(nq_1+r)=nq_2-nq_1=n(q_2-q_1).

    Condense the equality to only the first and last terms:

    j-i=n(q_2-q_1).

    This says n|(j-i). But the inequality 0\leq i<j\leq n-1 implies 0<j-i<n-1<n. So j-i is a positive integer which is both less than n AND divisible by n. This is clearly impossible.

    Hence, the conclusion we must draw is that our assumption that none of a,a+1,a+2,\ldots,a+(n-1) are divisible by n is faulty; hence at least one of them (in fact, EXACTLY one, which can be shown using the same subtraction trick) is divisible by n.

    ----------

    Obviously this is over-elaborate, but I really put in every detail for sake of a thorough explanation of a method of doing this question that doesn't involve consideration of multiple cases. Even if you don't answer the question this way, I hope this was enlightening or useful to you in some way.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Divisibility 11
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: December 20th 2008, 02:41 AM
  2. Divisibility (gcd) 10
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 04:44 PM
  3. Divisibility (gcd) 9
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 19th 2008, 01:12 PM
  4. Divisibility (gcd) 8
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 19th 2008, 03:53 AM
  5. Divisibility
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 14th 2008, 09:24 AM

Search Tags


/mathhelpforum @mathhelpforum