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

<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). Для записи числа в фибоначчие...

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

  а)  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.

Докажите, что число  <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>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">

Найдите наименьшее число вида  <i>n</i> = 2^α<i>pq</i>,  где <i>p</i> и <i>q</i> – некоторые нечётные простые числа, для которого  σ(<i>n</i>) = 3<i>n</i>.

Докажите, что при  <i>m ≠ n</i>  выполняются равенства:

  а)  (<i>a^m</i> – 1, <i>aⁿ</i> – 1) = <i>a</i>^{(<i>m, n</i>)} – 1  (<i>a</i> > 1);

  б)  (<i>f_n, f_m</i>) = 1,  где  <i>f_k</i> = 2^{2^<i>k</i>} + 1  – числа Ферма.

При каких целых <i>n</i> сократимы дроби

  а)   <img width="89" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60503/problem_60503_img_2.gif">;   б)  <img width="98" height="55" align="MIDDLE" border="0" src="/storage/problem-media/60503/problem_60503_img_3.gif">?

<i>a, b, c</i> – целые числа; <i>a</i> и <i>b</i> отличны от нуля.

Докажите, что уравнение  <i>ax + by = c</i>  имеет решения в целых числах тогда и только тогда, когда <i>c</i> делится на  <i>d</i> = НОД(<i>a, b</i>).

Натуральные числа <i>p</i> и <i>q</i> взаимно просты. Отрезок  [0, 1]  разбит на  <i>p + q</i>  одинаковых отрезков.

Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из  <i>p + q</i> – 2  чисел  ¹/_<i>p</i>, ²/_<i>p</i>, ..., ^<i>p</i>–1/_<i>p</i>,  ¹/_<i>q</i>, ²/_<i>q</i>, ..., ^<i>q</i>–1/_<i>q</i>.