Олимпиадные задачи из источника «глава 3. Алгоритм Евклида и основная теорема арифметики» для 9 класса - сложность 3-4 с решениями

Докажите, что при  <i>k</i> ≥ 1  выполняется равенство:   <img width="73" height="56" align="MIDDLE" border="0" src="/storage/problem-media/60622/problem_60622_img_2.gif"> = [<i>a^F_k</i>; <i>a</i>^{<i>F</i>_<i>k</i>–1}, ..., <i>a</i>^<i>F</i>₀],   где {<i>F_k</i>} – последовательность чисел Фибоначчи.

Докажите равенство:  [<img width="76" height="59" align="MIDDLE" border="0" src="/storage/problem-media/60618/problem_60618_img_2.gif">]  = <img width="199" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60618/problem_60618_img_3.gif">.

Разложите в цепные дроби числа:

  а) <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_2.gif">;   б) <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_3.gif">;   ½ + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60613/problem_60613_img_4.gif">.

Наиболее точный календарь ввёл в Персии в 1079 году персидский астроном, математик и поэт Омар Альхайями. Восстановите этот календарный стиль, рассмотрев третью подходящую дробь  [365; 4, 7, 1]  к длительности астрономического года. За сколько лет в этом календаре накапливается ошибка в одни сутки?

Докажите следующие свойства подходящих дробей:

  а)  <i>P_kQ</i>_<i>k</i>–2 – <i>P</i>_<i>k</i>–2<i>Q_k</i> = (–1)<i>^ka_k</i>  (<i>k</i> ≥ 2);

  б)  <img width="28" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60602/problem_60602_img_2.gif"> – <img width="45" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60602/problem_60602_img_3.gif"> = <img width="65" height="56" align="MIDDLE" border=&...

  Пусть <i>a</i>₀ – целое, <i>a</i>₁, ..., <i>a_n</i> – натуральные числа. Определим две последовательности

<i>P</i>_–1 = 1,  <i>P</i>₀ = <i>a</i>₀,  <i>P_k = a_kP</i>_<i>k</i>–1 + <i>P</i>_<i>k</i>–2  (1 ≤ <i>k ≤ n</i>);   <i>Q</i>_–1 = 0,  <i>Q</i>₀ = 1,  <i>Q_k = a_kQ</i><sub><i>k</i>–1</sub&...

Пусть <i>a</i>₁, <i>a</i>₂, ... – такая последовательность ненулевых чисел, что  (<i>a_m, a_n</i>) = <i>a</i>_{(<i>m, n</i>)}  (<i>m, n</i> ≥ 1).Докажите, что все <i>обобщенные биномиальные коэффициенты</i>   <img align="absMIDDLE" src="/storage/problem-media/60594/problem_60594_img_2.gif">   являются целыми числами.

Пусть число <i>m</i>₁ в десятичной системе счисления записывается при помощи <i>n</i> цифр.

Докажите, что при любом <i>m</i>₀ число шагов <i>k</i> в алгоритме Евклида для чисел <i>m</i>₀ и <i>m</i>₁ удовлетворяет неравенству  <i>k</i> ≤ 5<i>n</i>.

Решите в целых числах уравнения:   а)  <i>x</i>² – <i>xy – y</i>² = 1;   б)  <i>x</i>² – <i>xy – y</i>² = –1.

Последовательность<i>чисел Люка</i> {<i>L</i>₀,<i>L</i>₁,<i>L</i>₂, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i>₀=2,<i>L</i>₁=1,<i>L</i>_n=<i>L</i>_n-1+<i>L</i>_n-2при n>1. Выразите<i>L</i>_nв замкнутой форме через$\varphi$и$\widehat{\varphi}$.

<b>Определение</b>. Последовательность<i>чисел Люка</i> {<i>L</i>₀,<i>L</i>₁,<i>L</i>₂, ...} = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, ...} задается равенствами<i>L</i>₀=2,<i>L</i>₁=1,<i>L</i>_n=<i>L</i>_n-1+<i>L</i>_n-2при n>1. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями: а)<i>L</i>_n=<i>F</i>_{n - 1}+<i>F</i>_{n + 1}; б)5 <i>F</i><sub>...

Решите в целых числах уравнение   <i>x</i>φ^<i>n</i>+1 + <i>y</i>φ^<i>n</i>.

Число φ определено в задаче <a href="https://mirolimp.ru/tasks/160578">160578</a>.

<b>Фибоначчиева система счисления.</b>Докажите, что произвольное натуральное число<i>n</i>, не превосходящее<i>F</i>_m, единственным образом можно представит в виде<div align="CENTER"> <i>n</i> = $\displaystyle \sum\limits_{k=2}^{m}$<i>b</i>_k<i>F</i>_k, </div>где все числа<i>b</i>₂, ...,<i>b</i>_mравны 0 либо 1, причем среди этих чисел нет двух единиц стоящих рядом, то есть<i>b</i>_k<i>b</i>_{k + 1}= 0(2$\leqslant$<i>k</i>$\leqslant$<i>m</i>- 1). Для записи числа в фибоначчие...

В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.

Пусть первое число Фибоначчи, делящееся на <i>m</i>, есть <i>F_k</i>. Докажите, что  <i>m | F_n</i>  тогда и только тогда, когда  <i>k | n</i>.

Докажите, что для любого натурального <i>m</i> существует число Фибоначчи <i>F_n</i>  (<i>n</i> ≥ 1),  кратное <i>m</i>.

Докажите справедливость следующих утверждений:

  а)  2 | <i>F_n</i>   ⇔   3 | <i>n</i>;

  б)  3 | <i>F_n</i>   ⇔   4 | <i>n</i>;

  в)  4 | <i>F_n</i>   ⇔   6 | <i>n</i>;

  г)  <i>F_m</i> | <i>F_n</i>   ⇔   <i>m | n</i>  при  <i>m</i> > 2.

Вычислите<i>F</i>_{n + 2}⁴-<i>F</i>_n<i>F</i>_{n + 1}<i>F</i>_{n + 3}<i>F</i>_{n + 4}.

Существует ли такое целое число <i>r</i>, что  <img width="41" height="51" align="MIDDLE" border="0" src="/storage/problem-media/60559/problem_60559_img_2.gif">  является целым числом при любом <i>n</i>?

Докажите, что число  <img width="100" height="53" align="MIDDLE" border="0" src="/storage/problem-media/60558/problem_60558_img_2.gif">  (<i>m</i>, <i>n</i> ≥ 0)  целое.

При помощи <i>формулы Лежандра</i> (см. задачу <a href="https://mirolimp.ru/tasks/160553">160553</a>) докажите, что число   <img align="absmiddle" src="/storage/problem-media/60557/problem_60557_img_2.gif">   целое.

Пусть <i>p</i> – простое число и представление числа <i>n</i> в <i>p</i>-ичной системе имеет вид:   <i>n = a_kp^k + a</i>_<i>k</i>–1<i>p</i>^<i>k</i>–1 + ... + <i>a</i>₁<i>p</i>¹ + <i>a</i>₀.

Найдите формулу, выражающую показатель α_<i>p</i>, с которым это число <i>p</i> входит в каноническое разложение <i>n</i>!, через <i>n, p</i>, и коэффициенты <i>a_k</i>.

Пусть представление числа <i>n</i> в двоичной системе выглядит следующим образом:   <i>n</i> = 2^<i>e</i>₁ + 2^<i>e</i>₂ +...+ 2<i>^e_r</i>   (<i>e</i>₁ > <i>e</i>₂ > ... > <i>e_r</i> ≥ 0).

Докажите, что <i>n</i>! делится на 2^<i>n–r</i>, но не делится на 2^{<i>n–r</i>+1}.

Докажите, что число <i>p</i> входит в разложение <i>n</i>! с показателем, не превосходящим   <img align="absMIDDLE" border="0" src="/storage/problem-media/60554/problem_60554_img_2.gif">

Число <i>n</i>! разложено в произведение простых чисел:   <img align="absMIDDLE" src="/storage/problem-media/60553/problem_60553_img_2.gif">   Докажите равенство   <img align="absMIDDLE" src="/storage/problem-media/60553/problem_60553_img_3.gif">