📝 НОД И НОК. АЛГОРИТМ ЕВКЛИДА
В теории чисел часто возникает понятие НОД и НОК - наибольший общий делитель и наименьшее общее кратное соответственно.
Наибольший общий делитель чисел a и b: НОД(a,b) - это максимальное число, являющееся делителем a и b (т.е. на него одновременно делятся a и b).
Наименьшее общее кратное чисел a и b: НОК(a,b) - это минимальное число, делителями которого являются a и b (т.е. оно одновременно делится на a и b).
Давайте рассмотрим степень вхождения какого-либо простого числа p в числа a и b. Пусть a ⁝ p^n, b ⁝ p^m. Какая степень числа p пойдёт в НОД? Очевидно, та, которая меньше - min(m,n), ведь оба числа кратны НОД. Логично, что в НОК пойдёт наибольшая из двух степеней - max(m,n). Тогда если мы перемножим НОД(a,b) И НОК(a,b), то получим p^(n+m) - такую же степень, что и при перемножении a и b. Очевидно, что это справедливо для любого простого числа в разложении a и b. Только что мы вывели один симпатичный факт:

Произведение НОД и НОК двух чисел равно произведению самих этих чисел: НОД(a,b)•НОК(a,b) = ab

Хорошо, а теперь обратимся конкретно к НОД. Пусть a>b. Рассмотрим НОД(a,b) и НОД(a-b,b). Пусть НОД(a,b) ⁝ c => a⁝c, b⁝c => (a-b)⁝c => НОД(a-b,b) ⁝ c. Если же наоборот, НОД(a-b,b) ⁝ c, то (a-b)⁝c, b⁝c, => a⁝c => НОД(a,b) ⁝ c. Обобщая эти рассуждения, мы понимаем, что НОД(a,b) и НОД(a-b,b) делятся друг на друга, но это возможно тогда и только тогда, когда они равны. Поздравляю с открытием вещи под названием..

Алгоритм Евклида: НОД(a,b) = НОД(a-b,b), где a>b

Таким образом, в любом НОД из большего числа можно вычесть меньшее и заменить его на эту разность. Такое действие можно совершать, пока в одном из аргументов не получится ноль, а мы знаем, что НОД(x,0) = x.
Кроме того, можно не делать такое вычитание миллиард раз, а сразу заменить a на его остаток по модулю b: a ≡ r (mod b) => НОД(a,b) = НОД (r,b). Но более подробно об арифметике остатков мы поговорим позднее.
#уроки@mathbotva

Ну в целом ладно, лом слит, жаль не в том смысле как хотелось бы

🤔 ЛИРИЧЕСКОЕ ОТСТУПЛЕНИЕ
Вот и приближается к концу учебный год, у многих на горизонте уже ощутимо маячат экзамены. Кто-то готовился целый год, а может, и больше; кто-то только начинает (пупупу), а кто-то в состоянии варёного овоща после олимпиадного сезона, и хорошо если с дипломом, иначе овощ ещё и суицидальный.. Но не будем о грустном. Так или иначе, очень многие уже прошли долгий и непростой путь, и сейчас главное - не сдаться перед самым финишем. Вспомните, сколько всего вы уже сделали, похвалите себя, в конце концов - вы это заслужили. Вот ты, да, именно ты, послушай меня. Ты молодец, я это знаю. Твоя жизнь только начинается, и все эти егэ, всеросы, сессии ты будешь вспоминать с ностальгической улыбкой. Главное - не паникуй, всё хорошо. Выйди прогуляйся, посмотри на природу. Не забывай, конечно, про пункты из этого поста - они сейчас актуальны как никогда. Чем бы ты не занимался - продолжай в том же духе, всё у тебя получится. Спасибо за внимание.
#послушай@mathbotva

📝 ПОСЛЕДОВАТЕЛЬНОСТИ И ПРОГРЕССИИ
Сегодня обсудим более лайтовую тему. В общем случае последовательность - это набор каких-либо пронумерованных объектов. Зачастую рассматриваются именно числовые последовательности. Один из самых распространённых примеров последовательности - числа Фибоначчи, где два первых члена - единицы, а каждое последующее число определяется как сумма двух других.
🎯 Прогрессия - это вид последовательности, где каждый член находится в связи с предыдущим, причём связь эта едина для всей прогрессии. Прогрессии бывают арифметические, геометрические, арифметико-геометрические, гармонические и т.д., но в школе обычно затрагиваются только первые два вида, их и рассмотрим поподробнее.
🎯 Арифметическая прогрессия - это последовательность чисел, в которой каждый последующий член отличается от предыдущего на фиксированное число, называемое разностью арифм. прогресии (обычно обозначается буквой d, а сами члены - a с индексом их порядкового номера)
То есть общий вид арифметической прогресии: a, a+d, a+2d, a+3d, ... , a+(n-1)d
Последнее число, кстати, это формула n-ного члена арифм. прогрессии aₙ = a+(n-1)d. Например, a₁₀ = a+9d
Рассмотрим первые n членов арифм. прогрессии. Быстро становится понятно, что все числа разбиваются на пары с одинаковой суммой: a₁ c aₙ, a₂ c aₙ₋₁ и т.д. Тогда, посчитав количество таких пар, мы можем найти сумму всех n членов, умножив сумму пары на число пар. Если n чётно, то всё совсем очевидно - всё разбивается на пары, которых ровно n/2, и жизнь прекрасна. А если n нечётно? На самом деле всё то же самое, только центральное число находится как бы "в паре с самим собой", причём оно в точности равно сумме каждой из таких пар, а значит, ничего в наших рассуждениях не меняется. Мы получили формулу суммы первых n членов арифметической прогрессии: Sₙ = (a₁ + aₙ)•n/2
Не стоит также забывать про характеристическое свойство арифметической прогрессии, которое может служить её альтернативным определением (поэтому прогрессия и называется арифметической):

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

🎯 Геометрическая прогрессия - это последовательность чисел, в которой каждый последующий член отличается от предыдущего в какое-то фиксированное ненулевое число раз (знаменатель геом. прогрессии q; сами члены, кстати, обозначаются как b с индексом; b≠0; q≠0)
Общий вид геометрической прогрессии: b, bq, bq², bq³, ... , bqⁿ⁻¹
По очевидным причинам n-ный член геом. прогрессии bₙ = bqⁿ⁻¹
С суммой первых n членов геом. прогрессии всё чуть прозаичнее, но нужно кое-что знать про тождественные преобразования. Итак, Sₙ = b+bq+bq²+bq³+...+bqⁿ⁻¹ = b(1+q+q²+q³+...+qⁿ⁻¹).
Знатоки формул сокращенного умножения знают, что по разности n-ных степеней qⁿ-1 = (q-1)(qⁿ⁻¹+qⁿ⁻²+...+q³+q²+q+1). Но ведь вторая скобка - это ровно то, что нам нужно! Её можно выразить как (qⁿ-1)/(q-1), и тогда Sₙ = b•(qⁿ-1)/(q-1) = b•(1-qⁿ)/(1-q)
По аналогии с арифм. прогрессией, геометрическая получила своё название благодаря характеристическому свойству:

Модуль каждого члена геометрический прогрессии, кроме крайних, является средним геометрическим двух соседних с ним.

Здесь стоит быть осторожным со знакочередующимися прогрессиями - можно напороться на корень из отрицательного числа, чего не хотелось бы.
Отдельно стоит рассмотреть бесконечно убывающую геометрическую прогрессию. Если |q|<1 и n→∞, то qⁿ→0, тогда 1-qⁿ→1, а значит, Sₙ→b/(1-q).
Имеем сумму бесконечно убывающей геом. прогрессии: Sₙ = b/(1-q)
Разумеется, у этих прогрессий есть множество очень редких специфических свойств, которые мы здесь затрагивать не будем - все они элементарно выводятся из вышесказанного.
#уроки@mathbotva

А вообще вот вопрос: что ещё вы бы хотели видеть в этом канале? Мб какие-то постоянные рубрики или хотя бы иногда
Желательно конкретно, спасибо

А теперь 2^9, удвоились чуток
Спасибо!

Насчёт задачи дня.. Как я это вижу на данный момент: вероятно всего, каждый день в 12 часов я буду постить какую-то задачкс либо из каких-то источников, либо иногда и сам составлю, если потребуется то в комментах подсказку под спойлер закину, на следующий день решение и условие следующей, хз насколько это будет качественно но почему бы не попробовать, тем более что егэ скоро, но не ручаюсь что все они будут егэшные😉
Ах да, НЕ ЗАБЫВАЙТЕ ПИХАТЬ СВОИ МЫСЛИ ПОД СПОЙЛЕР‼️

Сегодня начнём с разминочной:
Задача дня №1

Натуральные числа от 1 до 200 разбили на 50 множеств. Докажите, что в одном из них найдутся три числа, являющиеся длинами сторон некоторого треугольника.

#задачадня@mathbotva