✓ Малая теорема Ферма или задачка про бусы | Ботай со мной
Вставка
- Опубліковано 15 бер 2017
- Сколько существует различных бус из p бусинок (p -- простое), каждая из которых одного из n цветов?
#БотайСоМной #013
Малая теорема Ферма или задачка про бусы
Книжка от Трушина: trushinbv.ru/book
Как поддержать канал: • Как помочь развитию ка...
Разовая помощь (Яндекс.Деньги): money.yandex.ru/to/4100110176...
Разовая помощь (PayPal): paypal.me/trushinbv
Разовая помощь (Donation Alerts): www.donationalerts.com/r/bori...
Регулярная помощь (UA-cam): / @trushinbv
Регулярная помощь (Patreon): / trushinbv
Онлайн-курсы по математике с Борисом Трушиным:
10 класс. Подготовка к ЕГЭ: trushinbv.ru/ege10
11 класс. Подготовка к ЕГЭ (задания 13-19): trushinbv.ru/ege11c
10-11 классы. Подготовка к Перечневым олимпиадам: trushinbv.ru/olymp
Кроме этого, можно купить мои прошлогодние курсы в записи:
Подготовка к ОГЭ: trushinbv.ru/oge9
Подготовка к ЕГЭ. Задания 1-12: trushinbv.ru/ege11b
Подготовка к ЕГЭ. Задания 13 и 15: trushinbv.ru/ege1315
Подготовка к ЕГЭ. Задание 14: trushinbv.ru/ege14
Подготовка к ЕГЭ. Задание 16: trushinbv.ru/ege16
Подготовка к ЕГЭ. Задание 17: trushinbv.ru/ege17
Подготовка к ЕГЭ. Задание 18: trushinbv.ru/ege18
Подготовка к ЕГЭ. Задание 19: trushinbv.ru/ege19
Другие курсы Фоксфорда: trushinbv.ru/courses
Репетиторы Фоксфорда: trushinbv.ru/coach
Личный сайт: TrushinBV.ru
Группа "Олимпиады, ЕГЭ и ОГЭ по математике": ege_trushin
Группа "TrushinBV.ru": trushinbvru
Личная страница: trushinbv
Группа "TrushinBV.ru": / trushinbv
Личная страница: / boris.trushin
Инстаграм: / trushinbv
TikTok: / trushinbv
Telegram: t.me/trushinbv
Twitter: / trushinbv
UA-cam-канал: / trushinbv
Учителя: есть такая сложная теорема Ферма, сейчас мы будем её доказывать.
Трушин: есть простенькая задачка про бусы, давайте её решим ... о, мы доказали теорему Ферма, круто.
Теперь великая теорема Ферма ждет объяснения на пальцах...
Её формулировка на пальцах, но доказательство 💀
нереальный сюжетный поворот. Вам надо фильмы про матан снимать
Это мой первый комментарий на UA-cam. Борис, вы его заслужили. Очень люблю ваши видео, смотрю просто для души. Спасибо вам!
Класс！👍
да, интересно привести к количеству бус - разрезов, но интереснее то,что разрезы между бус делаются, и первый разрез добавляем для всех последующих +1 цепочку, а получается так, потому что мы не делим, а отделяем от основы. К примеру, делим на 3 кучи, а движений нужно 2, и из этого принципа всякие задачи создали, к примеру.с расположением по периметру и операцией присоединения
Отличное видео!
Огонь!
Прикольно, спасибо, интересный видос
Вау!! Ну и красота
Привет спасибо за ролик. Надеюсь я поступлю.
Если коротко про доказательство той штуки с цепочками из бус с разными цветами. Тут хорошо бы знать некие азы теории групп и в частности про циклические перестановки и сдвиги, но можно предоставить более упрощенную аналогию используя просто числа. Цифры, как порядок бусинок.
Для простоты рассмотрим для p=5.
Будем нумеровать бусы, как цифрами от 1 до 5. Разрезая круг по-разному будем получать: 12345, 23451, 34512, 45123, 51234. То есть происходит как бы сдвиг. Факт, что все циферки сдвигаются важен, а так же - это аксиома, хотя бы в силу существования группы перестановок в теории групп.
Пока что мы никак не оговаривали, что элементы на разных позициях равны или различны, нас интересовал просто их порядок в цепочке.
Теперь как раз полезная аналогия с числами. Представьте себе число 12341. Как получить равное? Первую и пятую цифру поменять местами, а 2, 3, 4 не трогать. Если обобщить, то надо менять местами равные цифры, а отличающиеся оставлять на местах.
Однако вспоминаем, что у нас циклическая перестановка и все позиции меняются местами в любых двух разных цепочках. Значит, чтобы результат остался неизменным, они все должны быть равны между собой. Только тогда при перемене мест всех будет получаться равная цепочка. Если же есть пара (m, n) разных цветов один на i месте, другой на j, то в другой получится n на i и m на j. То есть уже отличие в цепочках. Отсюда и имеем p разных цепочек при любой разноцветности, тк любые 2 попарно не равны друг другу.
Пожалуй, все доказательство стоит свести к 5и строкам. Про цикличность и что что в любых двух разных цепах позиции i и j меняются. Дальше, что в любой разноцветности всегда найдется пара бус (m, n), которая при транспозиции в (n, m) уже образует новую уникальную цепу, не важны остальные точки. И так делаем попарно для любых двух, все они попарно неравны. А значит и все они различны. Вот и все.
Чтобы лучше понять, лучше порисовать все это дело.
Вот к МТФ добрались :) ня. Спасибо, БВ!
Отсюда следует, что n(n-1) всегда делится на 2 (это очевидно), n(n^2-1) всегда делится на 3, то есть либо n делится на 3, либо n^2-1 делится на 3.
Для 4 степени не работает; интереснее с высокими степенями: получается, что большинство выражений вида n^4-1 делится на 5, например. Не знаю, где это можно использовать, но интересно )
Впервые вижу, чтобы коментариев было настолько больше дизлайков.
В то время дизлайков у этих роликов вообще не было )
Спасибо за теорему Ферма.
А будут уроки для тех, кто начал Вас смотреть в пятом классе?))
Кто понял, как доказать, что невозможно разрезать ожерелье из разноцветных бусинок на две одинаковые цепочки, если количество бусинок простое?
Попробую объяснить на примере с 7 бусами.
Пускай есть цепочка abcdefg. Если бусы можно где-то ещё разрезать, то остальные цепочки это:
bcdefg_a
cdefg_ab
defg_abc
efg_abcd
fg_abcde
g_abcdef
Пускай, например, исходная цепочка совпадает с defgabc.
Тогда
d=a, e=b, f=c, g=d, a=e, b=f, c=g
Отсюда следует, что d=a=e=b=f=c=g=d. А значит, они все одного цвета.
В общем случае, мы говорим, что если исходная цепочка совпадает с другой (у которой смещение на k), то первая бусина (цвета a) совпадает с k+1й бусиной (цвета “d” в примере сверху). И вообще m-ая бусина совпадает с бусиной через k позиций, то есть с (m+k)-й бусиной.
А следовательно, 1-я совпадает с k+1-й, которая совпадает с 2k+1-й, которая совпадает с 3k+1-й, и т.д.
Положим бусы на окружность так чтобы первая была справа (угол 0 градусов от оси X). Если бы исходная цепочка совпадала с цепочкой после поворота на k бусинок, то бусы совпали бы с бусами повернутыми на k/7 окружности.
Заметим, что в повернутых бусах первая теперь лежит под углом (2π)k/7.
Если поворот на (2π)k/7 не поменял бусы, то можно снова повернуть и ничего не поменяется. Значит, первая бусина перейдёт в (2π)2k/7, потом в (2π)3k/7 и т.д. и когда-нибудь она вернётся обратно (не больше чем через 7 поворотов). А так как мы сказали, что бусы не менялись при каждом повороте, то все точки образующие углы 0, (2π)k/7, (2π)2k/7, (2π)3k/7 и т.д. должны быть одного цвета (такого же как и цвет первой бусинки).
Заметим, что они должны образовывать углы правильного многоугольника (или звезды) так как все углы равны.
А у правильного t-угольника точки должны образовывать углы от центра (2π)/t между соседними вершинами.
Значит в нашем многоугольнике какие-то две точки образуют угол (2π)/t.
То есть (2π)/t +(2π)u = (2π)xk/7 - (2π)yk/7, где x и y определяют две соседние вершины нашей «звезды», а (2π)u это несколько полных поворотов, так как от полных поворотов угол не меняется.
Тогда получаем 1/t + u = xk/7 - yk/7.
7/t +u = k(x-y)
7/t = k(x-y) + u.
Справа целое число, значит 7/t тоже целое. От сюда следует, что 7 делится на t. А так как 7 простое, то t может быть либо 1 либо 7.
Вот и получается, что у нас все места, где побывала первая бусина это либо 1-угольник (она никуда не двигалась), либо 7-угольник (она посетила место каждой бусины).
Следовательно, исходные бусы либо невозможно разрезать по разному и получить ту же цепочку; либо каждая бусина совпадает с первой (это и был наш одноцветный 7-угольник).
@@fullfungo спасибо, попозже прочту. В видео было сказано, что это легко доказать, по комментарию это как-то незаметно 🤣. Искал в интернете решение, там вообще какая-то теорема Пойа из высшей математики используется.
@@vasyapupkin997 Вообще доказательства элементарное, если использовать арифметику по модулю простого числа.
Тогда все рассуждения о бусинках сводятся к уравнению вида kx≡0 (mod p).
Отсюда следует, что kx=np, а значит одно из чисел делится на p.
Но мне не хотелось предполагать, что вы знакомы с арифметикой остатков, так что я привела аналогичное рассуждение с помощью углов (там 360=0, так что это тоже своеобразная арифметика остатков).
@@fullfungo А можно поподробнее? С арифметикой остатков знаком, а суть не улавливаю)
Ааа, всё, дошло :). В общем, "цепочки" мы получаем разрезанием ожерелья перед какой-то бусинкой. Если разрезанием перед бусинкой "1" и "2" мы получаем одну и ту же цепочку, то, во-первых, "1" и "2" совпадают по цвету(очевидно) , а во-вторых, посмотрим на бусинки между "1" и "2". Пусть их k штук. Несложно понять, что если мы отступим от бусинки "2" на k (только не обратно, а то мы опять попадём перед "1"), то попадём в место такое, что разрезанием получим такую же цепочку как и разрезанием перед "1" или "2". Пусть мы попали в место перед бусинкой "3". "1", "2" и "3" - бусинки одного и того же цвета. Получается, что бусинки одного и того же цвета повторяются с каким-то шагом k. Хорошо, а давайте теперь поймём вот что: пусть мы выбрали какую-то бусинку и начали двигаться в одну сторону шагами по k (в одну сторону значит, что обратно, например, из "2" в "1", нельзя).
Вопрос: сможем ли мы попасть целым числом шагов по k обратно в ту бусинку, с которой начали? Пусть x - число шагов, k - сам шаг. Тогда, если мы попадём в "первую" бусинку, то все наше "путешествие" представляется как некоторое число "полных оборотов" n по p (кол-во бусинок всего в бусах). Т.е:
kx = np. Важно отметить, что числа k и p взаимнопростые (т.е. их НОД = 1), потому что p - простое и k < p (объясняю неравенство: k не может быть равно p, т.к. тогда мы всегда попадали бы в "первую" бусинку).
Тогда если мы разделим обе части на p, то т.к. справа целое, то и слева должно быть целое. Но т.к. k и p взаимнопросты, то "X ДЕЛИТСЯ НА P". Это значит, что мы можем попасть в "первую" бусинку ТОГДА И ТОЛЬКО ТОГДА когда мы сделаем КАК МИНИМУМ p шагов. Ок разобрались, осталось совсем немного.
Итак, берём бусинку "1". Затем берём такую другую "2", что их цепочки совпадают. Измеряем количество бусинок между ними. Пусть их k. Тогда k - шаг. Пусть всего бусинок p штук(простое число). Возвращаемся в бусинку "1".
Теперь делаем шаг 1-ый, попадаем в "2". Важно понять, что "1" и "2" не совпадают(т.к. чтобы попасть в "1" нужно как минимум p шагов, а число 1 - не простое).Теперь делаем с бусинки "2" 2-ой шаг. Тут уже мы можем попасть в "1", если p = 2. Но пусть это не так, тогда попадём в "3". Заметим, что относительно бусинки "2" мы сделали не два шага а всего один, т.е. мы не сможем прийти в "2", если мы до этого не приходили в "1".С бусинки "3" делаем 3-ий шаг и попадаем в "4". Тут опять же p не равно 3, а значит в "1", "2", "3" попасть не можем. И так далее, и так далее. Потом мы делаем (p-1)-ый шаг. Если мы сделаем p-ый шаг, то попадём в "1", (p+1)-ый - попадём в "2" и т.д. Смотрите, мы сделали (p-1) шаг. Т.е. У нас (p-1) РАЗЛИЧНЫХ БУСИНОК ОДНОГО ЦВЕТА С "1",но всего-то их p! ЗНАЧИТ ВСЕ БУСИНКИ ОДНОГО ЦВЕТА, что и требовалось доказать!
Теория Пойа вам в помощь
2020 кто тут? =)
щас 2021 ващет
@@user-kx6qi6xm9s эм, разве не 4001?
@@paperwhite3853 нет щс 2021 год а он пишет 2020 кто тут
@@user-kx6qi6xm9s ну ладно, видимо я в датах запутался. С кем не бывает.
это год рождения или окончания школы?
Кто из 2007?)
Год рождения?)
@@whatromawants4681 а, я думала год просмотра видео) +2007
@@user-tq1vy3cf1g школа, ты не шаришь
Не совсем понял следующее… Почему если длинна бус равна простому числу, то разрезая бусы в разных местах, одинаковая цепочка возможна только если все бусинки одноцветны. Ведь даже в вами нарисованном примере при p=3 и n=2, те бусы у которых две бусинки одного цвета а одна другого можно разрезать в двух разных местах так, чтобы получающиеся цепочки были одинаковыми.
Нам порядок важен
Ну она ж неспроста там появилась. Значит задача изоморфна МТФ.
А значит можно создать решение опирающееся на МТФ.
ничё непонятно...
Не для любого. Есть числа - лжецы Ферма.
Что именно "не для любого"?
@@trushinbv я профан в математике, сразу говорю, однако 2 в степени 341 минус 2 проходит тест, однако 341 - непростое число. И таких чисел достаточно много.
@@trushinbv единственный известный на данный момент универсальный (то есть применимый ко всем числам) тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены:
ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%90%D0%B3%D1%80%D0%B0%D0%B2%D0%B0%D0%BB%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%8F%D0%BB%D0%B0_%E2%80%94_%D0%A1%D0%B0%D0%BA%D1%81%D0%B5%D0%BD%D1%8B
Любое простое число подчиняется малой теореме Ферма, но не любое непростое число не подчиняется ей.