Inductive Proof of DivisibilityDate: 06/25/2002 at 01:40:06 From: Harsh Mantri Subject: Number Theory, Divisibility Test How do you prove that for any integer n the number (n^5)-n is divisible by 30? Thanks Date: 06/25/2002 at 08:53:51 From: Doctor Paul Subject: Re: Number Theory, Divisibility Test We proceed by induction on n. The case n = 1 is obvious. Now assume that 30 divides n^5 - n, and consider: (n+1)^5 - (n+1) = n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n A number is divisible by 30 if and only if it is divisible by 2, 3, and 5 (the prime factors of 30). So we need to show that this is the case. Let's first show that n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n is always divisible by two. If n is even, then n^5, 5*n^4, 10*n^3, 10*n^2, and 4*n will all be even. Thus their sum is even (and hence divisible by two). If n is odd, then n^5 is odd, 5*n^4 is odd, and the other three terms are even. Thus n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n = odd + odd + even + even + even which will be an even number. Thus n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n is always divisible by two. Now let's show that n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n is divisible by five. Write: n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n = (n^5 - n) + (5*n^4 + 10*n^3 + 10*n^2 + 5*n) = (n^5 - n) + 5*(n^4 + 2*n^3 + 2*n^2 + n) The second term above is clearly divisible by five. And we've assumed that the first term is divisible by 30, which means it must also be divisible by 5. Finally, we show that n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n is always divisible by three. There are three possibilities: 1. n is a multiple of three 2. n is one more than a multiple of three 3. n is two more than a multiple of three. If n is a multiple of three, then n^5 + 5*n^4 + 10*n^3 + 10*n^2 + 4*n = n*(n^4 + 5*n^3 + 10*n^2 + 10*n^1 + 4) which will also be a multiple of three. If n is one more than a multiple of three, then n^5 will also be one more than a multiple of three 5*n^4 will be five more than a multiple of three 10*n^3 will be ten more than a multiple of three 10*n^2 will be ten more than a multiple of three 4*n will be four more than a multiple of three. Thus the sum will be 1 + 5 + 10 + 10 + 4 = 30 more than a multiple of three. But 30 more than a multiple of three is in fact a multiple of three. The case where n = 2 mod 3 (2 more than a muliple of three) is similar. I'll leave it for you. That completes the proof. I hope this helps. Please write back if you'd like to talk about this some more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/ Date: 06/25/2002 at 13:26:55 From: Harsh Mantri Subject: Thank you (Number Theory, Divisibility Test) Thanks a lot, Dr. Paul. Truly it is a complete proof. |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/