Maths Olympiad Prep

Library / /3 of 3

Number theory Difficulty 6.0 National Olympiad Prove it JBMO

Problem:

Prove that for every positive integer nn the number a=(2n+1)52n1a = (2n+1)^5 - 2n - 1 is divisible by 240240.

Solution

Solution:

Let a=(2n+1)52n1a = (2n+1)^5 - 2n - 1.

First, expand (2n+1)5(2n+1)^5 using the binomial theorem:

(2n+1)5=k=05(5k)(2n)k(1)5k=1+52n+10(2n)2+10(2n)3+5(2n)4+(2n)5(2n+1)^5 = \sum_{k=0}^5 \binom{5}{k} (2n)^k (1)^{5-k} = 1 + 5 \cdot 2n + 10 \cdot (2n)^2 + 10 \cdot (2n)^3 + 5 \cdot (2n)^4 + (2n)^5

Calculate each term:

11

52n=10n5 \cdot 2n = 10n

10(2n)2=104n2=40n210 \cdot (2n)^2 = 10 \cdot 4n^2 = 40n^2

10(2n)3=108n3=80n310 \cdot (2n)^3 = 10 \cdot 8n^3 = 80n^3

5(2n)4=516n4=80n45 \cdot (2n)^4 = 5 \cdot 16n^4 = 80n^4

(2n)5=32n5(2n)^5 = 32n^5

So,
(2n+1)5=1+10n+40n2+80n3+80n4+32n5(2n+1)^5 = 1 + 10n + 40n^2 + 80n^3 + 80n^4 + 32n^5

Therefore,
a=(2n+1)52n1=[1+10n+40n2+80n3+80n4+32n5]2n1a = (2n+1)^5 - 2n - 1 = [1 + 10n + 40n^2 + 80n^3 + 80n^4 + 32n^5] - 2n - 1

11=01 - 1 = 0, 10n2n=8n10n - 2n = 8n

So,
a=8n+40n2+80n3+80n4+32n5a = 8n + 40n^2 + 80n^3 + 80n^4 + 32n^5

Factor 8n8n:
a=8n(1+5n+10n2+10n3+4n4)a = 8n(1 + 5n + 10n^2 + 10n^3 + 4n^4)

Now, 240=2435240 = 2^4 \cdot 3 \cdot 5.

We will show that aa is divisible by 1616, 33, and 55 for all positive integers nn.

**Divisibility by 1616:**

Since a=8n(1+5n+10n2+10n3+4n4)a = 8n(1 + 5n + 10n^2 + 10n^3 + 4n^4), 8n8n is always divisible by 88. We need to check divisibility by 22 more (to get 1616).

Consider nn even: n=2kn = 2k, then 8n8n is divisible by 1616.

If nn is odd: n=2k+1n = 2k+1, 8n8n is still divisible by 88, but is it divisible by 1616?

But 1+5n+10n2+10n3+4n41 + 5n + 10n^2 + 10n^3 + 4n^4 is always even for integer nn (since nn odd, n2n^2 odd, n3n^3 odd, n4n^4 odd, so sum is odd + odd + even + even + even = odd, but times 8n8n which is even, so the product is divisible by 1616 for all nn).

Alternatively, check aa modulo 1616:

(2n+1)5(2n+1)5(mod16)(2n+1)^5 \equiv (2n+1)^5 \pmod{16}

But 2n+12n+1 is odd, so 2n+11,3,5,7,9,11,13,15(mod16)2n+1 \equiv 1, 3, 5, 7, 9, 11, 13, 15 \pmod{16}.

Compute (2n+1)5(2n+1)^5 modulo 1616 for all odd residues:

But x5x(mod16)x^5 \equiv x \pmod{16} for odd xx (since x41(mod16)x^4 \equiv 1 \pmod{16} for odd xx), so (2n+1)52n+1(mod16)(2n+1)^5 \equiv 2n+1 \pmod{16}.

Therefore,
a=(2n+1)52n1(2n+1)2n1=0(mod16)a = (2n+1)^5 - 2n - 1 \equiv (2n+1) - 2n - 1 = 0 \pmod{16}

So aa is divisible by 1616.

**Divisibility by 33:**

Compute a(mod3)a \pmod{3}:

2n+12n+1 modulo 33 can be 11, 22, or 00.

Case 1: 2n+10(mod3)2n+1 \equiv 0 \pmod{3}, i.e., 2n1(mod3)2n \equiv -1 \pmod{3}, n1(mod3)n \equiv 1 \pmod{3}.

Then a=052n102n1(mod3)a = 0^5 - 2n - 1 \equiv 0 - 2n - 1 \pmod{3}
But n1n \equiv 1, so a0211=21=30(mod3)a \equiv 0 - 2 \cdot 1 - 1 = -2 - 1 = -3 \equiv 0 \pmod{3}

Case 2: 2n+11(mod3)2n+1 \equiv 1 \pmod{3}, 2n0(mod3)2n \equiv 0 \pmod{3}, n0(mod3)n \equiv 0 \pmod{3}
Then a=152n1=12n1=2na = 1^5 - 2n - 1 = 1 - 2n - 1 = -2n
But n0n \equiv 0, so a0(mod3)a \equiv 0 \pmod{3}

Case 3: 2n+12(mod3)2n+1 \equiv 2 \pmod{3}, 2n1(mod3)2n \equiv 1 \pmod{3}, n2(mod3)n \equiv 2 \pmod{3}
Then a=252n1=322n1=312na = 2^5 - 2n - 1 = 32 - 2n - 1 = 31 - 2n
But n2n \equiv 2, so 2n41(mod3)2n \equiv 4 \equiv 1 \pmod{3}
So a311=300(mod3)a \equiv 31 - 1 = 30 \equiv 0 \pmod{3}

Therefore, aa is divisible by 33 for all nn.

**Divisibility by 55:**

Compute a(mod5)a \pmod{5}:

2n+12n+1 modulo 55 can be 1,2,3,4,01, 2, 3, 4, 0.

Case 1: 2n+10(mod5)2n+1 \equiv 0 \pmod{5}, 2n1(mod5)2n \equiv -1 \pmod{5}, n2(mod5)n \equiv 2 \pmod{5}
Then a=052n1=02n1a = 0^5 - 2n - 1 = 0 - 2n - 1
But n2n \equiv 2, so 2n42n \equiv 4, a041=50(mod5)a \equiv 0 - 4 - 1 = -5 \equiv 0 \pmod{5}

Case 2: 2n+11(mod5)2n+1 \equiv 1 \pmod{5}, 2n02n \equiv 0, n0n \equiv 0
a=152n1=101=0a = 1^5 - 2n - 1 = 1 - 0 - 1 = 0

Case 3: 2n+122n+1 \equiv 2, 2n12n \equiv 1, n3n \equiv 3
a=252n1=322n1=312na = 2^5 - 2n - 1 = 32 - 2n - 1 = 31 - 2n
n3n \equiv 3, 2n612n \equiv 6 \equiv 1, a311=300(mod5)a \equiv 31 - 1 = 30 \equiv 0 \pmod{5}

Case 4: 2n+132n+1 \equiv 3, 2n22n \equiv 2, n1n \equiv 1
a=352n1=2432n1=2422na = 3^5 - 2n - 1 = 243 - 2n - 1 = 242 - 2n
n1n \equiv 1, 2n22n \equiv 2, a2422=2400(mod5)a \equiv 242 - 2 = 240 \equiv 0 \pmod{5}

Case 5: 2n+142n+1 \equiv 4, 2n32n \equiv 3, n4n \equiv 4
a=452n1=10242n1=10232na = 4^5 - 2n - 1 = 1024 - 2n - 1 = 1023 - 2n
n4n \equiv 4, 2n832n \equiv 8 \equiv 3, a10233=10200(mod5)a \equiv 1023 - 3 = 1020 \equiv 0 \pmod{5}

Therefore, aa is divisible by 55 for all nn.

Conclusion:

aa is divisible by 1616, 33, and 55, so aa is divisible by lcm(16,3,5)=240\operatorname{lcm}(16,3,5) = 240 for all positive integers nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.