Олимпиадные задачи из источника «глава 3. Алгоритм Евклида и основная теорема арифметики»
глава 3. Алгоритм Евклида и основная теорема арифметики
НазадДоказать, что остаток от деления простого числа на 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> и <sup>1</sup>/<sub><i>a</i></sub> + <sup>1</sup>/<sub><i>b</i></sub> + ... + <sup>1</sup>/<sub><i>k</i></sub> = <sup>1</sup>/<sub><i>s</i></sub> + <sup>1</sup>/<sub><i>t</i></sub> + ... + <sup>1</sup>/<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>u</i> = [<i>a</i>; <img width="25" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60626/problem_60626_img_2.gif">], то вторым корнем будет число <img align="absmiddle" src="/storage/problem-media/60626/problem_60626_img_3.gif">
Докажите, что если положительная квадратичная иррациональность α = <img width="66" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60625/problem_60625_img_2.gif"> разлагается в чисто периодическую цепную дробь, то сопряженная ей квадратичная иррациональность α' = <img width="66" height="58" align="MIDDLE" border="0" src="/storage/problem-media/60625/problem_60625_img_3.gif"> принадлежит интервалу (– 1, 0).
Докажите, что если квадратное уравнение с целыми коэффициентами имеет корень [<img width="26" height="36" align="MIDDLE" border="0" src="/storage/problem-media/60624/problem_60624_img_2.gif">], то вторым корнем служит число <img align="middle" src="/storage/problem-media/60624/problem_60624_img_3.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<sup>F<sub>k</sub></sup></i>; <i>a</i><sup><i>F</i><sub><i>k</i>–1</sub></sup>, ..., <i>a</i><sup><i>F</i><sub>0</sub></sup>], где {<i>F<sub>k</sub></i>} – последовательность чисел Фибоначчи.
Докажите, что для любых целых чисел <i>p</i> и <i>q</i> (<i>q</i> ≠ 0), справедливо неравенство <img align="MIDDLE" src="/storage/problem-media/60621/problem_60621_img_2.gif">
Докажите, что если <sup><i>P<sub>n</sub></i></sup>/<sub><i>Q<sub>n</sub></i></sub> (<i>n</i> ≥ 1) – подходящая дробь к числу α, то имеет место по крайней мере одно из неравенств <img align="absmiddle" src="/storage/problem-media/60620/problem_60620_img_2.gif"> или <img align="absmiddle" src="/storage/problem-media/60620/problem_60620_img_3.gif"> Получите отсюда <i>теорему Валена</i>: для любого α найдётся бесконечно много таких дробей <sup><i>p</i></sup>/<sub><i>q</i></sub>, что |α – <sup><i>p</i></sup>/<sub><i>q</i></sub>| < <sup&g...
Докажите, что если <img align="MIDDLE" src="/storage/problem-media/60619/problem_60619_img_2.gif"> то <sup><i>p</i></sup>/<sub><i>q</i></sub> – подходящая дробь к числу α.
Докажите равенство: [<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.
Докажите, что значение любой периодической цепной дроби – квадратичная иррациональность.
Найдите наименьшее натуральное <i>n</i>, для которого существует такое <i>m</i>, что <img align="absmiddle" src="/storage/problem-media/60615/problem_60615_img_2.gif">
Найдите наименьшее натуральное <i>n</i>, для которого существует такое <i>m</i>, что <img align="absmiddle" src="/storage/problem-media/60614/problem_60614_img_2.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">.
Вычислите следующие цепные дроби:
а) [5; (1, 2, 1, 10}]; б) [5; (1, 4, 1, 10}]; в) [2; (1, 1, 3}].
Наиболее точный календарь ввёл в Персии в 1079 году персидский астроном, математик и поэт Омар Альхайями. Восстановите этот календарный стиль, рассмотрев третью подходящую дробь [365; 4, 7, 1] к длительности астрономического года. За сколько лет в этом календаре накапливается ошибка в одни сутки?
Из астрономии известно, что год имеет 365,2420... = [365; 4, 7, 1, 3,...] так называемых "календарных суток". В Юлианском стиле каждый четвёртый год – високосный, то есть состоит из 366 дней. За сколько лет при таком календаре накапливается ошибка в одни сутки? На сколько дней отстает Юлианский календарь за 1000 лет? И вообще, почему он отстает, если юлианский год длиннее астрономического?
Последовательности {<i>a<sub>k</sub></i>} и {<i>b<sub>k</sub></i>} строятся по следующему закону: <i>a</i><sub>1</sub> = 1, <img align="absmiddle" src="/storage/problem-media/60609/problem_60609_img_2.gif"> <i>a</i><sub><i>n</i>+1</sub> = min(<i>a<sub>n</sub>, b<sub>n</sub></i>), <i>b</i><sub><i>n</i>+1</sub> = |<i>b<sub>n</sub> – a<sub>n</sub></i>| (<i>n</i> ≥ 1).
а) Докажите, что <i>a<sub>n</sub></i> ≠ 0 и <i>a<sub>n</sub></i> стремится к 0 при <i>n</i> → ∞.
б)...
Предположим, что число α задано бесконечной цепной дробью α = [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i>, ...]. Докажите, что <img align="absMIDDLE" src="/storage/problem-media/60608/problem_60608_img_2.gif"> где <i>Q<sub>k</sub></i> – знаменатели подходящих дробей.
Докажите, что для любой бесконечной цепной дроби [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a<sub>n</sub></i>, ...] существует предел её подходящих дробей – иррациональное число α. Объясните, почему если это число α разложить в бесконечную цепную дробь при помощи алгоритма задачи <a href="https://mirolimp.ru/tasks/160606">160606</a>, то получится бесконечная цепная дробь, равная исходной.
Докажите, что любое иррациональное число α допускает представление α = [<i>a</i><sub>0</sub>; <i>a</i><sub>1</sub>, ..., <i>a</i><sub><i>n</i>–1</sub>, α<sub><i>n</i></sub>], где <i>a</i><sub>0</sub> – целое, <i>a</i><sub>1</sub>, <i>a</i><sub>2</sub>, ..., <i>a</i><sub><i>n</i>–1</sub> – натуральные, α<sub><i>n</i></sub> > 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> год полностью согласован с...