8th Eötvös Competition Problems 1991

1.  Show that 5 divides 1ⁿ + 2ⁿ + 3ⁿ + 4ⁿ iff 4 does not divide n.

2.  Let α = cot π/8, β = cosec π/8. Show that α satisfies a quadratic and β a quartic, both with integral coefficients and leading coefficient 1.

3.  Let d be the greatest common divisor of a and b. Show that exactly d elements of {a, 2a, 3a, ... , ba} are divisible by b. 

Solutions

Problem 1

Show that 5 divides 1ⁿ + 2ⁿ + 3ⁿ + 4ⁿ iff 4 does not divide n.

Solution

1ⁿ+2ⁿ+3ⁿ+4ⁿ = 1 + 2ⁿ + (-2)ⁿ + (-1)ⁿ mod 5. So if n is odd it is certainly divisible by 5. If n = 4k+2, then 2ⁿ = 4·2^4k = 4 mod 5, so 1ⁿ+2ⁿ+3ⁿ+4ⁿ = 1 + 4 + 4 + 1 = 0 mod 5. 

Problem 2

Let α = cot π/8, β = cosec π/8. Show that α satisfies a quadratic and β a quartic, both with integral coefficients and leading coefficient 1.

Solution

tan(A+B) = (tan A + tan B)/(1 - tan A tan B) gives cot 2A = (cot²A - 1)/(2 cot A). So 1 = (α² - 1)/(2α) or α² - 2α - 1 = 0.

We have cos 4k = cos⁴k - 6 cos²k sin²k + sin⁴k = (1-sin²k)² - 6 sin²k(1-sin²k) + sin⁴k = 8 sin⁴k - 8 sin²k + 1. Since cos π/2 = 0, we have 8/β⁴ - 8/β² + 1 = 0 or β⁴ - 8β² + 8 = 0. 

Problem 3

Let d be the greatest common divisor of a and b. Show that exactly d elements of {a, 2a, 3a, ... , ba} are divisible by b.

Solution

Put a = Ad, b = Bd. Then A, B are relatively prime, so nA is divisible by B iff n is divisible by B. Thus the only members of {A, 2A, ... bA} divisible by B are kA where k = B, 2B, ... , dB. Hence the only members of {a, 2a, ... ba} divisible by b are the d multiples ka where a = B, 2B, ... , dB.