For a positive integer $n$, we dene $D_n$ as the largest integer that is a divisor of $a^n + (a + 1)^n + (a + 2)^n$ for all positive integers $a$. 1. Show that for all positive integers $n$, the number $D_n$ is of the form $3^k$ with $k \ge 0$ an integer. 2. Show that for all integers $k \ge 0$ there exists a positive integer n such that $D_n = 3^k$.
Problem
Source: Dutch IMO TST 2015 day 1 p5
Tags: number theory, divisor, maximum, exponential
30.08.2019 16:59
1. If there exist a prime number p such that $p\neq 3$ and $p| D_n$, $p| a^n+(a+1)^n +(a+2)^n$ and $p| (a-1)^n+a^n+(a+1)^n$ so $p| a^n+(a+1)^n +(a+2)^n - ((a-1)^n+a^n+(a+1)^n)=(a+2)^n-(a-1)^n$ plugging a=1 we get $p| 3^n$ and so we get a contradiction that $p\neq 3$ and so $D_n$ must be of the for $3^k$ 2. one of $a,a+1,a+2$ must be divisible by 3 and 2 of them are not divisible by 3. We take the two not divisible by 3 and label them x,y. 3 doesnt divide x nor y but divides x+y so we can use LTE. $V_3(x^n+y^n)=V_3(x+y)+V_3(n)$ setting $n=3^{k-1}$ we can ensure that $V_3(a^n+(a+1)^n+(a+2)^n)\ge k$ for all positive integer $a$ however when $a=1$ , $V_3(a^n+(a+1)^n+(a+2)^n)=V_3(a^n+(a+1)^n)=V_3(3)+V_3(n)=k$ so $D_n=3^k$ when $n=3^{k-1}$ and we are done
16.03.2020 23:23
anthonyshinex wrote: 1. If there exist a prime number p such that $p\neq 3$ and $p| D_n$, $p| a^n+(a+1)^n +(a+2)^n$ and $p| (a-1)^n+a^n+(a+1)^n$ so $p| a^n+(a+1)^n +(a+2)^n - ((a-1)^n+a^n+(a+1)^n)=(a+2)^n-(a-1)^n$ plugging a=1 we get $p| 3^n$ and so we get a contradiction that $p\neq 3$ and so $D_n$ must be of the for $3^k$ 2. one of $a,a+1,a+2$ must be divisible by 3 and 2 of them are not divisible by 3. We take the two not divisible by 3 and label them x,y. 3 doesnt divide x nor y but divides x+y so we can use LTE. $V_3(x^n+y^n)=V_3(x+y)+V_3(n)$ setting $n=3^{k-1}$ we can ensure that $V_3(a^n+(a+1)^n+(a+2)^n)\ge k$ for all positive integer $a$ however when $a=1$ , $V_3(a^n+(a+1)^n+(a+2)^n)=V_3(a^n+(a+1)^n)=V_3(3)+V_3(n)=k$ so $D_n=3^k$ when $n=3^{k-1}$ and we are done At 1. if a=1 ,a-1=0 and this is not positive integer.
16.03.2020 23:39
Take a=p+1