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

Доказать, что остаток от деления простого числа на 30 – простое число или единица.

Даны два натуральных числа <i>m</i> и <i>n</i>. Выписываются все различные делители числа <i>m</i> – числа <i>a, b, ..., k</i> – и все различные делители числа <i>n</i> – числа <i>s, t, ..., z</i>. (Само число и 1 тоже включаются в число делителей.) Оказалось, что  <i>a + b + ... + k = s + t + ... + z</i>  и  ¹/_<i>a</i> + ¹/_<i>b</i> + ... + ¹/_<i>k</i> = ¹/_<i>s</i> + ¹/_<i>t</i> + ... + ¹/<sub>&l...

Доказать: число делителей <i>n</i> не превосходит 2<img width="27" height="33" align="MIDDLE" border="0" src="/storage/problem-media/78208/problem_78208_img_2.gif">.

а) Докажите, что положительный корень квадратного уравнения  <i>bx</i>² – <i>abx – a</i> = 0,  где <i>a</i> и <i>b</i> – различные натуральные числа, разлагается в чисто периодическую цепную дробь с длиной периода, равной 2.

б) Верно ли обратное утверждение?

Докажите, что при  <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/60617/problem_60617_img_2.gif">;   б)  α = 2 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60617/problem_60617_img_3.gif">;   в)  α = 3 + <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60617/problem_60617_img_4.gif">   не более чем на 0,0001.

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

  а) <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]  к длительности астрономического года. За сколько лет в этом календаре накапливается ошибка в одни сутки?

Из астрономии известно, что год имеет  365,2420... = [365; 4, 7, 1, 3,...]  так называемых "календарных суток". В Юлианском стиле каждый четвёртый год – високосный, то есть состоит из 366 дней. За сколько лет при таком календаре накапливается ошибка в одни сутки? На сколько дней отстает Юлианский календарь за 1000 лет? И вообще, почему он отстает, если юлианский год длиннее астрономического?

Докажите, что любое иррациональное число α допускает представление  α = [<i>a</i>₀; <i>a</i>₁, ..., <i>a</i>_<i>n</i>–1, α_<i>n</i>],  где <i>a</i>₀ – целое, <i>a</i>₁, <i>a</i>₂, ..., <i>a</i>_<i>n</i>–1 – натуральные,  α_<i>n</i> > 1  – иррациональное действительное. Отсюда следует, что каждому иррациональному действительному числу можно поставить в соответствие бесконечную цепную дробь.

<b>Григорианский календарь</b>. Обыкновенный год содержит 365 дней, високосный – 366. <i>n</i>-й год, номер которого не делится на 100, является високосным тогда и только тогда, когда <i>n</i> кратно 4. <i>n</i>-й год, где <i>n</i> кратно 100, является високосным тогда и только тогда, когда <i>n</i> кратно 400. Так, например, 1996 и 2000 годы високосные, а 1997 и 1900 – нет. Эти правила были установлены папой Григорием XIII. До сих пор мы имели ввиду <i>гражданский</i> год, число дней которого должно быть целым. <i>Астрономическим</i> же годом называется период времени, за который Земля совершает полный оборот вокруг Солнца. Считая, что <i>григорианский</i> год полностью согласован с...

Разлагая число ^<i>a</i>/_<i>b</i> в непрерывную дробь, решите в целых числах уравнения  <i>ax – by</i> = 1,  если

  a)  <i>a</i> = 101,  <i>b</i> = 13;   б)  <i>a</i> = 79,  <i>b</i> = 19.

Пусть числа <i>a</i> и <i>b</i> определены равенством  ^<i>a</i>/_<i>b</i> = [<i>a</i>₀; <i>a</i>₁, <i>a</i>₂, ..., <i>a_n</i>].  Докажите, что уравнение  <i>ax – by</i> = 1  c неизвестными <i>x</i> и <i>y</i> имеет решением одну из пар  (<i>Q</i>_<i>n</i>–1, <i>P</i>_<i>n</i>–1)  или  (– <i>Q</i>_<i>n</i>–1, – <i>P</i>_<i>n</i>–1),  где  <sup&...

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

  а)  <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>n</i> приведите пример прямоугольника, который разрезался бы ровно на <i>n</i> квадратов, среди которых должно быть не более двух одинаковых.

Работу алгоритма Евклида (см. задачу <a href="https://mirolimp.ru/tasks/160488">160488</a>) можно представить следующим образом. В прямоугольник размерами  <i>m</i>₀×<i>m</i>₁  (<i>m</i>₁ ≤ <i>m</i>₀)  укладываем <i>a</i>₀ квадратов размера   <i>m</i>₁×<i>m</i>₁,  в оставшийся прямоугольник размерами  <i>m</i>₁×<i>m</i>₂  (<i>m</i>₂ ≤ <i>m</i>₁)  укладываем <i>a</i><sub>1...

Как связано разложение рационального числа в цепную дробь с алгоритмом Евклида?

Пусть   <img align="absMIDDLE" src="/storage/problem-media/60596/problem_60596_img_2.gif">   Чему равны <i>P_n</i> и <i>Q_n</i>?

Разложите в цепные дроби числа ¹⁴⁷/₁₃ и ¹²⁹/₁₁₁.

Пусть <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">   являются целыми числами.

<div align="CENTER"> <table cellpadding="3"> <tr><td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER">1</td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </td> <td align="CENTER"> </...

Пусть число <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>.

Рассмотрим алгоритм Евклида из задачи <a href="https://mirolimp.ru/tasks/160488">160488</a>, состоящий из <i>k</i> шагов.

Докажите, что начальные числа <i>m</i>₀ и <i>m</i>₁ должны удовлетворять неравенствам  <i>m</i>₁ ≥ <i>F</i>_<i>k</i>+1,  <i>m</i>₀ ≥ <i>F</i>_<i>k</i>+2.