Олимпиадные задачи из источника «параграф 6. Китайская теорема об остатках» для 11 класса - сложность 3 с решениями

Генерал хочет построить для парада своих солдат в одинаковые квадратные каре (конечно, в каре должно быть более одного человека), но он не знает сколько солдат (от 1 до 37) находится в лазарете. Докажите, что у генерала может быть такое количество солдат, что он, независимо от заполнения лазарета, сумеет выполнить свое намерение. Например войско из 9 человек можно поставить в виде квадрата 3×3, а если один человек болен, то в виде двух квадратов 2×2.

а) Трёхзначное число 625 обладает своеобразным свойством самовоспроизводимости, как то:  625² = 390625. БикЮ Сколько четырёхзначных чисел удовлетворяют уравнению  <i>x</i>² ≡ <i>x</i> (mod 10000)?

б) Докажите, что при любом <i>k</i> существует ровно четыре набора из <i>k</i> цифр – 0...0, 0...01 и ещё два, оканчивающиеся пятеркой и шестёркой, – обладающие таким свойством: если натуральное число оканчивается одним из этих наборов цифр, то его квадрат оканчивается тем же набором цифр.

Предположим, что числа <i>m</i>₁, ..., <i>m_n</i> попарно взаимно просты. Докажите, что любую правильную дробь вида   <img width="76" height="43" align="MIDDLE" border="0" src="/storage/problem-media/60833/problem_60833_img_2.gif">  можно представить в виде алгебраической суммы правильных дробей вида ^<i>n_i</i>/_{<i>m_i</i>}  (<i>i</i> = 1, ..., <i>n</i>).

Докажите, что число <i>x</i> является элементом приведённой системы вычетов тогда и только тогда, когда числа <i>a</i>₁, ..., <i>a_n</i>, определённые сравнениями

<i>x ≡ a</i>₁ (mod <i>m</i>₁),  ..., <i>x ≡ a_n</i> (mod <i>m_n</i>)  принадлежат приведённым системам вычетов по модулям <i>m</i>₁, ..., <i>m_n</i> соответственно. Выведите отсюда мультипликативность функции Эйлера.

Пусть натуральные числа <i>m</i>₁, <i>m</i>₂, ..., <i>m_n</i> попарно взаимно просты. Докажите, что если числа <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i> пробегают полные системы вычетов по модулям <i>m</i>₁, <i>m</i>₂, ..., <i>m_n</i> соответственно, то число  <i>x = x</i>₁<i>m</i>₂...<i>m_n + m</i>₁<i>x</i>₂<i>m</i&gt...

Укажите все целые числа <i>x</i>, удовлетворяющие системам:

  а)   <i>x</i> ≡ 3 (mod 5),

        <i>x</i> ≡ 7 (mod 17);

  б)   <i>x</i> ≡ 2 (mod 13),

        <i>x</i> ≡ 4 (mod 19).

Найдите остатки от деления:  а) 19¹⁰ на 6;   б) 19¹⁴ на 70;   в) 17⁹ на 48;   г) 14^14¹⁴ на 100.