Divisibility and RemaindersDate: 8/23/96 at 4:59:13 From: Anonymous Subject: Divisibility and Remainders a) Show that every odd square leaves a remainder 1 when divided by 8, and that every even square leaves remainder 0 or 4. Deduce that a number of the form 8n + 7, where n is an integer, cannot be expressed as a sum of three squares. b) Prove that n^5 - n is divisible by 30. c) Suppose m is a positive integer divisible by 11. Prove that the integer m obtained by reversing the digits of m may also be divisible by 11. Date: 8/23/96 at 8:20:3 From: Doctor Anthony Subject: Re: Divisibility and Remainders >a) Show that every odd square leaves a remainder 1 when divided >by 8, and that every even square leaves remainder 0 or 4. Deduce >that a number of the form 8n + 7, where n is an integer, cannot be >expressed as a sum of three squares. An odd square is of form (2k+1)^2 = 4k^2+4k+1 = 4(k^2+k) + 1 = 4k(k+1) + 1. Now either k or k+1 is even so this is M(8) + 1 where M(8) means multiple of 8. Hence odd square leaves a remainder 1 when divided by 8. An even square is of the form (2k)^2 = 4k^2. So if k is even this will be M(8) and remainder is 0. If k is odd we could write k = 2m + 1. So (2k)^2 = 4k^2 = 4(2m+1)^2 = 4(4m^2+4m+1) = 16m^2 + 16m + 4 = M(8) + 4. So we get a remainder of 4. Deduce that a number of the form 8n+7 cannot be expressed as a sum of three squares. If we partition n so that n = a+b+c, then 8n + 7 = 8a + 8b + 8c + 7 = (8a+1) + (8b+4) + (8c+2). Now 8a + 1 or 8b + 4 could be squares but 8c + 2 could not be (see part(i) of this question). Indeed there is no way that you could split up 7 so as to give the remainders 0, 1, or 4 that are required with just three partitions of 7. We conclude that 8n + 7 could not be the sum of three squares. >b) Prove that n^5 - n is divisble by 30. We can write this as n(n^4-1) = n(n^2-1)(n^2+1) = n(n-1)(n+1)(n^2+1) = (n-1)n(n+1)(n^2+1). The product of three consecutive terms, n - 1, n, n + 1 must be divisible by 2 and by 3, and so by 6. We must therefore show that n^5 - n is also divisible by 5 to show that it is divisible by 30. We can do this by induction. We have for n = 2 2^5 - 2 = 32 - 2 = 30 = M(5). Assume it is true for n=k and then consider n = k+1 We have f(k) = k^5 - k = M(5) f(k+1) = (k+1)^5 - (k+1) f(k+1) - f(k) = (k+1)^5 - (k+1) - (k^5 - k) = k^5 + 5C1k^4 + 5C2k^3 + 5C3k^2 + 5C4k + 1 - k - 1 - k^5 + k = 5C1k^4 + 5C2k^3 + 5C3k^2 + 5C4k = 5k^4 + 10k^3 + 10k^2 + 5k So f(k+1) - f(k) = M(5), but f(k) = M(5) and so f(k+1) = M(5). If f(n) is divisible by 5, then so is f(n+1). But f(2) is divisible by 5, therefore f(3) is also divisible by 5, then f(4), f(5) and so on to all positive integral values of n. So the result is true generally. We have f(n) divisible by 6 and also by 5 for all n, and so f(n) is divisible by 30. >c) Suppose m is a positive integer divisible by 11. Prove that the >integer m obtained by reversing the digits of m may also be divisible >by 11. If a number abcd is divisible by 11 we have: 1000a + 100b + 10c + d and we write it in the form (1001-1)a + (99+1)b + (11-1)c + d = 1001a + 99b + 11c - (a+c) + (b+d). This will be divisible by 11 if -(a+c) + (b+d) is zero or a multiple of 11. If we wrote this expression in reverse order dcba = 1000d+100c+10b+a, then this is divisible by 11 if -(d+b)+(c+a) is zero or a multiple of 11. But this is the same condition that we had before, and so reversing the digits will not affect divisibility by 11. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/