Any five consecutive numbers must contain a multiple of 5, a multiple of 2 (that's not a multiple of 4), a multiple of 4, and a multiple of 3. There will be another multiple of 3, unless n is a multiple of 3, but then n^2 is a multiple of 3*3. So (n-2)*(n-1)*n*n*(n+1)*(n+2) must be a multiple of 5 * 2 * 4 * 3 * 3 = 360. Thirty seconds, perhaps?
For n = 2 we get n⁵ - n = 30, so k can not be greater than 30. But can it be 30? 30 = 2 * 3 * 5 and n⁵ - n = n (n - 1) (n³ + n² + n + 1) Either n or (n - 1) is divisible by 2. For n = 3m the factor n = 3m is divisible by 3. For n = 3m + 1 the factor (n - 1) = 3m is divisible by 3. Finally for n = 3m + 2 the term n³ + n² + n + 1 = 3 (9m³ + 21m² + 17m +5) is divisible by 3. For n = 5m or 5m + 1 the first or second factor is divisible by 5. For n = 5m +2, 5m + 3 or 5m + 4 (n³ + n² + n + 1) is divisible by 5. So yes, 30 is the largest value for k that will always divide n⁵ - n.
I had nearly the same approach; note that n^5-n = (n-1)n(n+1)(n^2+1). k|(2^5-2) = 30 Either (n-1), or n is dividible by 2. Either (n-1), n, or (n+1) is dividible by 3. Either (n-1), n, (n+1), (n+2), or (n+3) is dividible by 5. ==> Either (n-1), n, (n+1), (n-2)*(n+2)+5, or (n-3)*(n+3)+10 is dividible by 5. Either (n-1), n, (n+1), (n^2+1), or (n^2+1) is dividible by 5 5|(n^5-n) 5|k k|30 and 2,3,5|k k=30
@oatil1998 If a number is divisible by 5, then all multiples of that number are also divisible by five. Also if you add a mutliple of 5 to a number divisible by 5, then the resulting sum is divisble by 5.
I’d prove this by induction if I were asked that question
1. k = p^a * q^b *... | n^5 - n
2. p^a | n^5 - n
3. a = 1, p | n^5 - n
4. a = 1, p - 1 | 4
5 a = 1, p \in {2, 3, 5}
1 2 ... 5
k = p^a * q^b *... | n^5 - n a = 1, p \in {2, 3, 5} k = 2^{0, 1} * 3^{0, 1} * 5 ^ {0, 1} => max k = 2 * 3 * 5 = 30.
Any five consecutive numbers must contain a multiple of 5, a multiple of 2 (that's not a multiple of 4), a multiple of 4, and a multiple of 3. There will be another multiple of 3, unless n is a multiple of 3, but then n^2 is a multiple of 3*3. So (n-2)*(n-1)*n*n*(n+1)*(n+2) must be a multiple of 5 * 2 * 4 * 3 * 3 = 360. Thirty seconds, perhaps?
My snarky way of solving this: n^2(n^2-1)(n^2-4)/360 == (n+3 choose 6)+(n+2 choose 6) which is an integer
@@noahtaul hmmmm, how did you come up with the sum of binomial coefficients there?
@@JPiMaths (n+3 choose 6) = (n+3)! / (6! * (n-3)!) = (n+3)(n+2)(n+1)n(n-1)(n-2)/6! Similarly, (n+2 choose 6) = (n+2)(n+1)n(n-1)(n-2)(n-3)/6!
So (n+3 choose 6) + (n+2 choose 6) = [ (n+3) + (n-3) ] * [ (n+2)(n+1)n(n-1)(n-2) ] / 6! = 2n^2 * (n+2)(n+1)n(n-1)(n-2) / 6!
Since 6! = 720, we have (n+3 choose 6) + (n+2 choose 6) = 2 * n^2 * (n+2)(n+1)n(n-1)(n-2) / 720 = n^2 * (n^2 - 1) * (n^2 -4) / 360. So it's an integer.
The binomial coefficients contain the product of consecutive integers and are a not-uncommon means of expressing such products.
For n = 2 we get n⁵ - n = 30, so k can not be greater than 30. But can it be 30?
30 = 2 * 3 * 5 and n⁵ - n = n (n - 1) (n³ + n² + n + 1)
Either n or (n - 1) is divisible by 2.
For n = 3m the factor n = 3m is divisible by 3. For n = 3m + 1 the factor (n - 1) = 3m is divisible by 3. Finally for n = 3m + 2 the term n³ + n² + n + 1 = 3 (9m³ + 21m² + 17m +5) is divisible by 3.
For n = 5m or 5m + 1 the first or second factor is divisible by 5. For n = 5m +2, 5m + 3 or 5m + 4 (n³ + n² + n + 1) is divisible by 5.
So yes, 30 is the largest value for k that will always divide n⁵ - n.
I had nearly the same approach; note that n^5-n = (n-1)n(n+1)(n^2+1).
k|(2^5-2) = 30
Either (n-1), or n is dividible by 2.
Either (n-1), n, or (n+1) is dividible by 3.
Either (n-1), n, (n+1), (n+2), or (n+3) is dividible by 5.
==> Either (n-1), n, (n+1), (n-2)*(n+2)+5, or (n-3)*(n+3)+10 is dividible by 5.
Either (n-1), n, (n+1), (n^2+1), or (n^2+1) is dividible by 5
5|(n^5-n)
5|k
k|30 and 2,3,5|k k=30
@@derwolf7810 Yes this is a simpler (=better) prove. I missed the (n + 1)(n² + 1) factorization.
@@MrGeorge1896 these are both nice solves! Thanks for sharing
@derwolf7810
Could you explain how you arrived at the first implication, the rest makes sense but how did you get that?
@oatil1998 If a number is divisible by 5, then all multiples of that number are also divisible by five.
Also if you add a mutliple of 5 to a number divisible by 5, then the resulting sum is divisble by 5.