Сегодня мы принесли вам непростую задачку! Решить её помогут посты о модульной арифметике
и малой теореме Ферма.

Напомним формулировку малой теоремы Ферма:
Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹-1 нацело делится на p.

Сегодняшняя задача: найдите остаток от деления числа 300³⁰⁰⁰–1 на 1001.

Эта задача отличается от задач из предыдущих постов на эту тему. Загвоздка в том, что 1001 — не простое число. Значит, сразу применить малую теорему Ферма не удастся. На этом мы замолкаем и предлагаем дальше вам порассуждать самостоятельно. Решения и ответы ждём традиционно под скрытым текстом.
Разбор опубликуем в понедельник.

Онлайн-день открытых дверей в Яндекс Практикуме

Привет!
29 августа, во вторник, в 15:00 по Москве эксперты в прямом эфире расскажут, чем отличаются профессии в сфере технологий, как сменить профессию на IT, чего ждут работодатели от кандидатов на разные вакансии, а также ответят на вопросы.

Мероприятие бесплатное, регистрация — по ссылке.
Приходите, будет содержательно, полезно и интересно!

Исходный анонс в телеграм-канале Яндекс Практикума.

Привет!
Разберём четверговую задачу — найдём остаток от деления числа 300³⁰⁰⁰–1 на 1001.

Для решения нам пригодятся три факта:
1) Малая теорема Ферма:
Если p — простое число и a — целое число, которое не делится на p, то aᵖ⁻¹-1 нацело делится на p.
2) Если два числа сравнимы по модулю третьего, то их натуральные степени также сравнимы. То есть если a ≡ b (mod c), то для любого натурального k верно, что aᵏ ≡ bᵏ (mod c).
3) Если a ≡ b (mod c), n ≡ m (mod c), то a*n ≡ b*m (mod c).

Решение

Число 1001 — составное, раскладывается на множители как 7*11*13. Эти множители простые — то, что нужно для применения теоремы.

Посмотрим, что с остатками от деления 300³⁰⁰⁰ на каждый из множителей.

Возьмём p=7. Теперь представим число 300³⁰⁰⁰ в таком виде, чтобы в степени было p-1=6. Для этого разложим степень на множители:
300³⁰⁰⁰ = (300⁵⁰⁰)⁶.
К такой записи уже можно применить теорему: p=7, a=300⁵⁰⁰,
и значит (300⁵⁰⁰)⁶ ≡ 1 (mod 7). 

Теперь возьмём p равным следующему множителю. Для p=11 имеем:
300³⁰⁰⁰ = (300³⁰⁰)¹⁰ ≡ 1 (mod 11).
Для p=13 будет:
300³⁰⁰⁰ = (300²⁵⁰)¹² ≡ 1 (mod 13).

Получается, что число 300³⁰⁰⁰ сравнимо с 1 по всем трём модулям: и по 7, и по 11, и по 13.
Отсюда 300³⁰⁰⁰ ≡ 1 (mod 7*11*13). Такое верно только при если модули были взаимно просты: у нас 7, 11 и 13 как раз такие.
И тогда 300³⁰⁰⁰ – 1  ≡ 0 (mod 1001), то есть это число делится на 1001 нацело!

Ответ: 0.

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

Привет!

Напоминаем, что через час начнётся онлайн-день открытых дверей в Яндекс Практикуме.

Чтобы попасть, зарегистрируйтесь.

Подробный анонс в телеграм-канале Яндекс Практикума

Есть в математике тема, которая по каким-то причинам никого не оставляет равнодушными — это комплексные числа. И даже ударение в термине — повод для обсуждения. Мы ставим ударение на е: компле́ксные.
Эти числа позволяют делать запретное — извлекать корни из отрицательных чисел и решать уравнения, у которых как будто не должно быть корней.

Мы ещё ни разу не говорили о них в нашем канале и хотим, чтобы первое знакомство запомнилось.
Поэтому представляем вам сайт, который объединил лучшее — комплексные числа и красивые картинки с фракталами. Ему уже больше пяти лет, а он всё ещё занимает особое место в нашем сердечке. Картинка к этому посту — как раз оттуда.

Знакомьтесь: сайт «Медузы и жопы». 😁
Название вирусное, но в этом, кажется, и был успех.

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

Три лайфхака, которые помогают всё-таки выучить

Ни в школе, ни в институте не учат тому, как правильно изучать материал. Студенты в основном решают однообразные задачи, чтобы лучше сдать тест, но чаще всего это в итоге не дает реального знания. Зубрёжка быстро выветривается и не приносит пользы.
Вывод: учиться тоже нужно уметь.

Делимся тремя простыми техниками, которые помогут сделать обучение эффективным и захватывающим!

1) Вспоминайте материал в ванной и на прогулке. Подойдут и другие места — чем неожиданнее, тем лучше.
2) Рассказывайте материал друзьям. А ещё лучше — детям. Чтобы рассказать простыми словами, нужно глубоко понять тему.
3) Придумывайте вопросы по материалу. Если вы учитесь с преподавателем, задайте ему. Если вы учитесь самостоятельно, придумайте вопрос и ответьте на него — двойная польза.

Помните: чем больше усилий приходится тратить на создание нейронных связей, тем дольше они продержатся. Поэтому если сейчас у вас что-то трудно идёт, то когда всё-таки получится — знания будут глубже.

Попробовать применить техники можно вы знаете где! 😉

На курсах «Аналитик данных», «Специалист по Data Science» и «Системный аналитик» действует акция: если вы пройдёте бесплатную часть за неделю с момента подписки, то получите скидку 7% на оплату курса.

В комментариях предлагаем поделиться лайфхаками, которые помогают вам учиться быстрее и эффективнее. 🧠

Хинкальная задача

Математик Георгий приехал в Грузию и зашёл в местное кафе. Оно оказалось очень маленьким, в меню всего три позиции: хинкали по 3 лари за штуку, хачапури за 8 лари и лимонад за 5 лари.

Георгий задумался: а что будет, если он потратит все деньги на что-то одно? Согласно вычислениям у него останется:
• 1 лари, если он потратит всё на хинкали;
• 6 лари, если он потратит всё на хачапури;
• 4 лари, если он потратит всё на лимонады.

Сколько денег у Георгия, если эта сумма меньше 100 лари?

---

Ответы и решения присылайте под скрытым текстом.
Разбор задачи опубликуем в четверг.

Разберём недавнюю задачу про меню в грузинском ресторане.
Решить её можно несколькими способами.

1) Первый и самый «лобовой» из них — перебор. Для небольших чисел вполне сработает, в нашей случае он был бы долгим, но опишем его алгоритм.

В этой задаче есть ограничение — у Георгия было меньше 100 лари.
Все подходящие числа, дающие остаток 1 при делении на 3 можно записать как множество:
A = {1, 4, 7, 10, 13, 16, …, 94, 97}.
Те, что дают остаток 6 при делении на 8 можно записать как такое множество
B = {6, 14, 22, 30, 38, 46, …, 86, 94}.
Числа, имеющие остаток 4 при делении на 5:
С = {4, 9, 14, 19, 24, 29, …, 94, 99}.

Дальше нужно найти пересечение этих множеств. И хоть мы и не выписывали все множества целиком, уже видно, что все три содержат число 94. Оно и будет ответом! На самом деле в пересечении может быть несколько чисел, тогда нужно смотреть, какое из них подходит под условия задачи. Нам повезло: 94 — минимальное число, подходящее под эти условия, следующим будет только 214.
Но видно, что если бы мы действительно выписывали все элементы в каждом множестве, получилось бы ну очень не оптимально.

2) Поэтому здесь очень удобно воспользоваться признаками делимости!
Вот, например, отличное решение в комментариях к исходному посту. Оно построено на исключении неподходящих вариантов. В данной задаче мы рекомендуем именно такой способ.

3) Но существует ещё один метод, который позволяет решать похожие задачи для большего числа уравнений, для более громоздких чисел или в общем виде.
Он основан на Китайской теореме об остатках. По её условию у любой системы уравнений, в которых модули сравнения попарно взаимно просты, существует бесконечное количество решений, причем они отличаются на произведение модулей (например, тут они будут отличаться на 3*5*8 = 120). Именно поэтому после 94 следующим подходящим числом будет 94+120 = 214, а потом 334 и так далее.

Теорема достаточно сложна в ручном применении, для её использования нужно ловко жонглировать операциями в модульной арифметике. Зато она позволяет найти все подходящие числа!
Если у вас есть вопросы по этому алгоритму, можете задавать их в комментариях.


Как видите, хачапури — это лучший повод поговорить о чём угодно! 💪

Поможет ли «корочка» в работе?

В СССР был важен диплом. А Марк Цукерберг так и не закончил вуз, но стал миллиардером. Где же правда: наличие диплома — это стереотип или до сих пор важно? Можно долго размышлять, а можно обратиться к исследованиям.

ВШЭ исследовала влияние степени магистра на успехи. Результаты показали, что для таких специалистов:
• Выше вероятность трудоустроиться. Наличие диплома магистра увеличивает вероятность занятости на 3—8% среди мужчин и на 10—16% среди женщин.
• Выше заработная плата. Магистерская степень ассоциирована с зарплатной премией среди женщин в размере 5—21% и среди мужчин в размере 2—11%.

Получить степень магистра можно онлайн. Яндекс Практикум совместно с Томским государственным университетом организовал магистратуру «Дата-аналитика для бизнеса». Вы учитесь онлайн, а по окончании получаете диплом государственного образца и степень магистра.

Набор на этот год идёт до 18 сентября. Приходите за новыми возможностями! 🖖

Вебинар «Разбор задач с собеседований»

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

Ну а где математика, там и мы! 😎
Спикеркой вебинара была Диана Миронидис, одна из создательниц контента этого канала и математических курсов Практикума.
Мероприятие было закрытым, но мы подумали, что нашим замечательным подписчикам тема тоже может быть интересна. Поэтому Диана проведёт ещё один вебинар — специально для подписчиков этого канала.


Когда: четверг 14.09, в 19.00 по Москве.
Что будет: разберём алгоритмы решения задач.
Где: в зуме по этой ссылке, запись тоже сделаем.

Заносите в свои календари, и до встречи в четверг! 🥳

Пример задачи с собеседования

А пока предлагаем решить одну задачу с вебинара. Её решение разберём завтра в посте.

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

Известно, что сегодня все учащиеся находятся в школе. Если вы случайно встретите в коридоре школы студента мужского пола, какова вероятность того, что он учит эсперанто?

Ваши ответы и решения ждём в комментариях под скрытым текстом.

Решим вчерашнюю задачу про студентов в языковой школе.
Покажем два способа.

Первый способ — просто по количествам.
Посчитаем
мужчин, изучающих клингонский: 0.5*150 = 75,
мужчин, изучающих эсперанто: 0.6*100 = 60,
мужчин, изучающих синдарин: 0.3*50 = 15.
Итого мужчин-студентов: 75+60+15 = 150.
Если в коридоре встретили студента мужского пола, то вероятность того, что он изучает эсперанто равна 60/150 = 2/5 = 0.4.
Здесь в числителе количество интересующих нас студентов (мужчин, изучающих эсперанто), а в знаменателе — общее количество мужчин-студентов (ведь известно, что мы встретили именно мужчину).

Второй способ — через условную вероятность.
На самом деле в задаче нужно найти именно её, однако данный способ конкретно здесь будет более долгим, чем просто посчитать «в лоб».
В этом случае нам пригодится общее количество студентов: 150+100+50 = 300 человек.

Теперь введём события и посчитаем их вероятности:
Пусть B — «случайно встреченный/ая студент/ка изучает эсперанто».
Пусть M — «случайно встреченный в коридоре студент — мужского пола».

Нужно найти P(B|M). По определению условной вероятности
P(B|M) = P(B⋂M) / P(M). Вычислим обе нужные нам вероятности.
P(M) найти легко: (75+60+15) / 300 = 0.5.
B⋂M — это событие «случайно встреченный студент — мужского пола и изучает эсперанто». Значит, P(B⋂M) = (0.6*100) / 300 = 0.2.
Тогда по определению условной вероятности имеем
P(B|M) = P(B⋂M) / P(M) = 0.2 / 0.5 = 0.4.

Мы двумя способами получили один ответ — значит, он (скорее всего) правильный. 😁
В комментариях было много верных решений, это очень здорово!

Вебинар в 19:00 по Москве

Привет! Через два часа начнётся вебинар, на котором мы разберём решения задач с собеседований.

Где: в зуме по этой ссылке.
Запись будет, выложим в канал.

Приходите! Обещаем, что будет интересно, полезно и понятно 😇

Запись вебинара «Разбор задач с собеседований»

Спасибо всем, кто вчера присоединился к вебинару!

Для тех, кто не смог, прикладываем запись.
Презентация с задачами и решениями — в комментах.

Будет здорово, если после просмотра оставите обратную связь в форме.
В конце формы вас ждёт подарочек 🥰

Привет!
Сегодня предлагаем вам решить задачку. 🚕

В приложении «Бумер» для вызова такси у каждого водителя есть рейтинг. Он высчитывается как среднее арифметическое всех оценок водителю. Если в конце месяца рейтинг водителя составляет 4.6 или выше — он получает премию.

Сергей Владимирович — хороший водитель, клиенты всегда ставят ему 5 или 4. На сегодняшний день ему поставили 115 оценок, и его рейтинг равен 4.4. Какое минимальное количество пятёрок ему нужно заработать, чтобы получить премию в конце месяца?

Решения и ответы ждём в комментариях под скрытым текстом.

Разберём вчерашнюю задачу про таксиста Сергея Владимировича.

Сейчас у него 115 оценок. Умножим это количество на среднюю оценку 4.4, получим общую сумму оценок: 4.4*115 = 506.
Для премии нужна оценка 4.6 и выше. Обозначим дополнительное количество пятёрок, которые нужно получить, за n. Тогда всего будет 115+n оценок, а их общая сумма равна 506 + 5n.

Составим неравенство для подходящей средней оценки:
(506 + 5n) / (115 + n) ⩾ 4.6.
Домножим обе части на знаменатель и упростим:
506 + 5n ⩾ 529 + 4.6n;
0.4n ⩾ 23;
n ⩾ 57.5.
Количество пятёрок — это натуральное число, поэтому подойдёт ближайшее сверху: 58.
Ответ: 58

Интересный момент: для решения этой задачи не пригодилась информация о том, что до этого Сергей Владимирович получал только четвёрки и пятёрки. При желании можно вычислить их исходное количество, но это необязательно, в задаче про это не спрашивали.
Ответ остался бы таким же при любом исходном наборе оценок Сергея Владимировича: если их всё ещё 115, и при этом средняя оценка всё ещё 4.4, то ему по-прежнему нужно как минимум 58 дополнительных пятёрок, чтобы получить премию.

Как классифицировать числа на множества

Наверняка многие из вас узнают множества на верхней картинке: это множества натуральных, целых, действительных и комплексных чисел. Они расположены «матрёшкой» друг относительно друга, то есть одно множество целиком содержится в другом и так далее.

Этот способ классифицировать числа по множествам — привычный, но не единственный! Сегодня мы поговорим о другом подходе — с его помощью можно разделить числа на алгебраические и трансцендентные. Названия могут немного напугать, но мы сейчас всё аккуратно объясним.

Возьмём многочлен любой степени с целыми коэффициентами.
Какими будут его корни?
• Иногда целыми, например, для x-1=0.
• Иногда — рациональными, например, для 2x³-7x=0.
• Иногда — иррациональными: √2 — это корень уравнения x²-2=0.
• А иногда — комплексными, например, в x⁴+5=0.

Так вот: для корней уравнения с целыми (и даже рациональными) коэффициентами придумали специальное название. Одно из названий таких уравнений — алгебраическиие, и их корни называют алгебраическими числами.

Может показаться, что алгебраическим является любое число. Но нет — существуют доказательства того, что, например, известные всем числа π, e или lg5 не подойдут в качестве корня никакому алгебраическому уравнению. Такие числа называют трансцендентными.

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