Теория чисел

Свяжем игру «Взрывающиеся точки» с системой счисления — увидим, как механика «взрыва» воспроизводит правило переноса в двоичной записи.

Двоичная система — система счисления с основанием 2. Учимся переводить числа из десятичной в двоичную и обратно через два алгоритма: вычитание степеней двойки и деление на 2 с остатком.

Складываем и умножаем числа «в столбик» непосредственно в двоичной системе. Учимся правильно переносить разряды и используем удобные приёмы.

Связываем идеальные тасования карт (in/out) с двоичной записью числа: каждая последовательность тасований — это двоичная строка, кодирующая позицию карты в колоде.

Шестнадцатеричная система — основание 16. Учимся записывать числа цифрами 0–9 и буквами A–F, переводить между двоичной, десятичной и шестнадцатеричной системами. Открываем быстрый перевод из двоичной в шестнадцатеричную через группировку по 4 цифры.

Считаем в шестнадцатеричной системе: складываем, умножаем, возводим в квадрат — в столбик, без перевода в десятичную. Решаем «шестнадцатеричные криптограммы».

Какое основание наиболее эффективно для компьютера? Открываем, что это 3 (точнее e ≈ 2,72, но из целых — троичная). Знакомимся с уравновешенной троичной системой (-1, 0, 1) и её математическими удобствами.

Повторите свойства факториала: рекуррентное соотношение n! = n·(n−1)!, обоснование 0! = 1 и применение в комбинаторике.

Научитесь применять структурные закономерности в арифметике: зеркальные цифры, пирамида единиц, цепочки девяток, хвостовые нули.

Углублённое изучение цифровых корней: связь с остатком от деления на 9, свойства сложения и умножения, магический фокус.

Узнайте, когда дробь даёт конечную десятичную запись, и освойте критерий через простые множители знаменателя.

Научитесь распознавать периодические дроби и переводить их в обыкновенные методом сдвига.

Изучите теорию длин периодов: почему простые знаменатели дают длинные периоды и почему каждая рациональная дробь либо конечна, либо периодична.

Сложные задачи-синтез, объединяющие все приёмы из раздела десятичных разложений.

Изучите признаки делимости на 1, 2, 5 и 10 — и узнайте, как определить делимость, не выполняя деление.

Признаки делимости на 4 и 8, сумма остатков, первые криптограммы

Признаки делимости на 3, 6 и 9 через сумму цифр. Сводная таблица всех признаков.

Применяем признаки делимости на 3, 4 и 9 для решения криптограмм

Криптограммы со сложением в столбик: перенос, чётность, метод НОК

Финальный набор криптограмм: логика, теория чисел и алгебра в одном флаконе

Признаки делимости шестнадцатеричных чисел на 2, 4 и 8 — через последнюю цифру.

Признаки делимости шестнадцатеричных чисел через сумму цифр для 3, 5 и F. Репьюниты.

Признак делимости на 11₁₆ через знакочередующуюся сумму цифр. Репьюниты и синтез.

Обобщение трёх признаков делимости (по последней цифре, сумме цифр, знакочередующейся сумме) на любое основание.

Вычисляйте последние цифры шестнадцатеричных степеней с помощью теоремы Эйлера.

Вычисляйте последние цифры степеней в произвольных основаниях с помощью теоремы Эйлера и малой теоремы Ферма.

Два множества имеют одинаковую мощность, если между их элементами можно установить взаимно однозначное соответствие — и это работает даже для бесконечных множеств.

Окунитесь в безумный мир чисел, где живут бесконечно много бесконечностей — больших и маленьких.

Бесконечный отель всегда находит место — даже для бесконечно многих гостей. Исследуем арифметику счётной бесконечности ℵ₀.

Может ли игровая ставка иметь бесконечное матожидание выигрыша?

Достаточно ли посмотреть на последнюю цифру числа, чтобы понять, на что оно делится?

Разберитесь в признаках делимости на степени 2 и 5 через метод остатков по степеням 10.

Откройте, почему каждая степень числа 10 даёт остаток 1 при делении на 9 и на 3, и выведите из этого признаки делимости.

Научитесь находить последнюю цифру суммы, произведения и степени, не выполняя полного вычисления.

Узнайте, как остатки слагаемых и множителей определяют остаток результата — основа модульной арифметики.

Исследуйте удивительные закономерности при вычислении цифровых корней — и научитесь проверять арифметику без вычислений.

Научитесь строить деревья делителей и поймите, почему листья всегда простые — это основная теорема арифметики в действии.

Научитесь использовать разложение на простые как универсальный инструмент: делимость, полные степени, построение чисел.

Научитесь раскладывать факториалы на простые множители и считать хвостовые нули.

Научитесь быстро считать число делителей по разложению на простые множители.

Классическая головоломка о ста дверях и ста людях. Открытие связи между количеством делителей и состоянием двери в конце процесса.

Доказательство Евклида о бесконечности простых чисел через четыре шага рассуждения

Возвращение к головоломке про 100 дверей. На этот раз внимание не на финале, а на том, кто и сколько дверей трогает — и сколько дверей трогают двое одновременно. Скрытый мост к НОД/НОК.

Развивает интуицию о том, где встречается наименьшее общее кратное — как в абстрактных, так и в практических ситуациях.

Исследуйте, как путь шара, отскакивающего от бортов бильярдного стола, зависит от размеров стола — и как это связано с наименьшим общим кратным сторон.

Найдите наибольший общий делитель через разложения на простые множители и узнайте о взаимно простых числах.

Если нарисовать прямоугольный треугольник на сетке точек, через сколько точек пройдёт гипотенуза? Связь с НОД.

Когда правила прыжков по числовой прямой позволяют добраться до любого целого числа? Первый эпизод серии — приложение НОД.

Разрабатываем системный приём для нахождения наименьшего положительного числа, до которого можно «допрыгать» парой шагов.

Откройте главную теорему серии: наименьшее число, до которого можно дойти прыжками размеров a и b, равно НОД(a, b). Узнайте алгоритм Евклида.

Поймите связь между НОД и НОК через диаграмму Венна простых множителей и докажите ключевое тождество $\text{НОД}(a, b) \cdot \text{НОК}(a, b) = a \cdot b$.

Возвращение к бильярдной задаче: вычисляем долю клеток, которые шар проходит, и число отскоков от бортов — выводим обе формулы через НОК и НОД.

Применяем разбор по чётности и формулы числа отскоков, чтобы определить, в какую лузу попадёт шар на любом столе $a \times b$ — и доказываем, что нижне-левая луза недостижима.

Используйте короткие пути, чтобы найти последнюю цифру ответа — без полных вычислений!

Ищи закономерности, чтобы разгадывать зашифрованные сообщения с помощью шифра Цезаря, масонского шифра, числовых кодов и перестановки.

Исследуйте циклические раскраски чисел и откройте основы модулярной арифметики.

Время по часам или по календарю устроено модулярно — давайте с этого и начнём.

Что произойдёт, если намотать бесконечную числовую прямую на квадрат со стороной 1? Этот вопрос приводит нас к формальному определению сравнения по модулю — главного понятия модулярной арифметики.

Узнайте, как складывать и умножать сравнения, и примените это к вычислению остатков больших чисел.

Применим аппарат модулярной арифметики, чтобы вывести признак делимости на 11 — знакопеременную сумму цифр. По дороге обнаружим красивые следствия: палиндромы из чётного числа цифр всегда делятся на 11, а разность числа и его «перевёрнутой записи» — на 11, если цифр нечётное число.

Вы наверняка умеете рисовать пятиконечную звезду. А восьмиконечную? Двенадцатиконечную? Тридцатиконечную? В этом уроке мы разработаем универсальный способ — и увидим, как тут проявляется арифметика остатков.

Выведем общую формулу для числа лучей звезды — через наибольший общий делитель и модулярную арифметику.

Сколько разных звёзд можно нарисовать на окружности из 60 точек? А какие именно числа точек у этих звёзд бывают? И когда звезда оказывается «полной» — то есть в ней каждая точка становится лучом? Этим вопросам и посвящён финальный урок серии.

Задача — отмерить заданное количество жидкости, используя только определённые разрешённые ходы для двух сосудов фиксированного объёма.

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

Раскроем концепцию, незримо присутствующую как в построении звёзд, так и в задачах о переливаниях.

Могут ли обычные уравнения, не имеющие целочисленных решений, превратиться в сравнения, у которых решения есть? Этот вопрос приводит нас к понятию обратного элемента по модулю — фундаменту криптографии.

Что происходит со степенями в модулярной арифметике? Повторное умножение по модулю $m$ порождает циклы — разберёмся, когда они имеют одинаковую длину, и выведем теорему Эйлера.

Когда модуль — простое число, теорема Эйлера упрощается до $a^{p-1} \equiv 1 \pmod{p}$. Применим эту формулу к гигантским степеням и научимся тестировать числа на составность.

Это не грозная Великая теорема Ферма, но и она бьёт сильно — несмотря на скромный размер! В этом уроке формализуем функцию Эйлера φ(m) и научимся считать её через разложение на простые множители.

Применим теорему Эйлера, чтобы находить последние одну или две цифры колоссальных чисел вида $17^{17}$, $123^{123^{123}}$ и $3^{1000}$ — без полного вычисления.

Применим знание о функции Эйлера и теореме Эйлера, чтобы понять, через сколько идеальных тасований колода возвращается в исходный порядок.

Изучите разницу между аддитивными и позиционными системами счисления.

Научитесь записывать любое число с помощью только нулей и единиц.

Применяйте знания о двоичной системе в реальных задачах информатики.