Областная олимпиада по математике, 2003 год, 9 класс

Пусть $a_n=n^2+500$ и $d_n=2+{\mathop{\hbox{НОД}}\nolimits}(a_n, a_{n+1})$ для любого натурального $n$. Определите наибольшее значение $d_n$.

Комментарий/решение

$$ \textbf{1.} НОД(a,b)=НОД(b,a)$$

$$ \textbf{2.} НОД(a,b)=НОД(a-b,a)$$

$$ НОД(a_n,a_{n+1})=НОД(n^2,(n+1)^2+500)=НОД((n+1)^2+500,n^2)=НОД(2n+501,n^2)$$

$$\textbf{1)}n^2>(2n+501) \Rightarrow n^2=k(2n+501) \Rightarrow D=4k^2+4\cdot 501>0\Rightarrow n_{1,2}=k\pm \sqrt{k^2+501}$$

$$ k^2+501=m^2\Rightarrow (m-k)(m+k)=167\cdot 3= 3\cdot167$$

$$ (m,k): (\pm85,\mp82),(\pm85,\pm82)$$

$$ n\in N \Rightarrow n(82)=82+\sqrt{501+82^2}=167\in N$$

$$d_{167}=2+НОД(2\cdot 167+501,167^2)=2+167=169$$

$$ \textbf{2)}n^2<(2n+501) \Rightarrow 2n+501=kn^2 \Rightarrow D=4+4k\cdot501>0\Rightarrow n_{1,2}=\frac{1\pm\sqrt{1+k\cdot501}}{k}\Rightarrow k $$

$$ (nk)^2-2nk+1=1+k\cdot 501$$

$$ nk(nk-2)=k\cdot 501\Rightarrow n(nk-2)=501=167\cdot 3= 3\cdot167\Rightarrow n, k \notin N$$

$$ \textbf{3)} n^2=2n+501 \Rightarrow n \notin N$$

$$\textbf{OTBET:} \max \left\{d_n\right\}_{n\in N}=d_{167}=169$$

Почему "$a_{n}=n^2$"? $a_{n}=n^2+500$.

$Ответ: 2003$

Рассмотрим $d_{2k}$ и $d_{2k+1}$.

$d_{2k}-2=(a_{2k+1},a_{2k})=(4k+1,4k^2+500)=(4k+1,500-k)=(2001,500-k)\leq2001$

$d_{2k+1}-2=(4k^2+4k+501, 4k+3)=(-3k-3+501,4k+3)=(498-3k,k+501)=(2001,k+501)\leq2001$, значит максимум $d_{n}=2003$, например: $n=3001$.

$a_{n}=n^2+500$

$a_{n+1}=(n+1)^2+500=n^2+2n+501$

По алгоритму Эвклида:

$НОД(n^2+500, n^2+2n+501)$=$НОД(n^2+500, n^2+2n+501-n^2-500)$=$НОД(n^2+500, 2n+1)$

Пусть $n^2+500$ делится на $2n+1$, тогда

$n^2+500-k(2n+1)=0, k \Rightarrow \mathbb{N} ,$

$n(n-2k)=-500+k$

Наибольший возможный n только при k=500

$n^2+500-1000n-500=0$

$n(n-1000)=0$

$n=1000$

подставляем в $НОД(n^2+500, 2n+1)$ и получаем $НОД(1000500, 2001)=2001$

тогда максимальное значение $d_{n}=2001+2=2003$