Это частный случай утверждения что n^m-1 делится на n-1 без остатка. Доказывается путем разложения многочлена x^m-1 на множители. Корень уравнения x^m -1=0 очевидно x=1. Соответственно x^m-1 можно представить как(x-1)•P(x), где P(x) это некий полином с целыми коэффициентами. В нашем случае х = 777 т.е 777⁷⁷⁷-1=(777-1)•P(777)=776•P(777), соответственно выражение делится на 776 нацело.
777 ⁷⁷⁷ = (776 + 1)⁷⁷⁷. По формуле *бинома Ньютона* представляем данную степень в виде многочлена. Последний член такого многочлена будет равен 1⁷⁷⁷ = 1, остальные члены -есть некие степени числа 776, помноженные на коэфициент, являющийся целым числом (вычисляется как число сочетаний). Итак, 777 ⁷⁷⁷ - 1 = (776 + 1)⁷⁷⁷ - 1, Здесь -1 и 1, получаемая в результате применения формулы бинома Ньютона, взаимно уничтожаются; остается выражение из степеней 776, очевидно, которое делится на 776 без остатка.
Ну, есть такая формула сокращённого умножения, где А в степени Н минус Б в степени Н раскладывается, как (А-Б) умноженное на сумму раличных коэффициентов. Для А2-Б2 это (А-Б)(А+Б). То есть, исходя из этого в первой скобке находится для нашего примера как раз 777-1=776 и оно само на себя делится. Но вот как это доказать другим способом и как эта формула получается - я не знаю )
@@viktor-kolyadenko почему "единиц"? Для различной степени Н во второй скобке различный набор коээфициентов, умноженных на комбинации А и Б. Или мы говорим о разных вещах?
@@roden2208 , смотрите, есть общая формула: x^n - y^n = (x - y)(x^[n-1] + x^[n-2]y +...+ y^[n-2]x + y[n-1]) По идее легко доказывается непосредственным умножением. То есть все "различные коэффициенты" получаются равными 1 (для суммы непарных степеней будут знаки чередоваться).
Метод математической индукции: 1) при n=1, остаток от деления 777 на 776 равен 1. 2) Пусть при n=k, остаток от деления 777^k на 776 равен 1. 3) тогда при n=k+1, 777^(k+1)=777^k×(776+1)=777^k×776+777^k, первое слагаемое делится нацело, а остаток от деления 777^k на 776 равен 1, по пункту 2). То есть, от первой степени, добавляя каждый раз по 1, получим что остаток от деления 777^777 на 776 равен 1. Но если отнять этот остаток, число 777^777-1 делится на 776.
Любая разность степеней первой скобкой содержит a-b, a2-b2=(a-b) *(a+b), a3-b3=(a-b) *(...), также и далее a4-b4=(a-b) *(a+b) *(a2+b2), a5-b5= также даст (a-b) *(...), следовательно вышли на первую теорему в решении.
В комментариях правильно пишут про метод индукции. Проще всего доказать в общем случае, что для любых натуральных x и n, остаток от деления x^n на (x-1) будет равен единице. Альтернативный вариант - показать, что это естественное свойство кольца вычетов по x, но этому в школе точно не учат 😂
Можно проще. 777=3*259. И степень 777 можно представить в виде куба. И у нас получиться разность кубов. Раскладываем её и один из сомножителей будет 777-1=776.
777^2=(776+1)^2 два члена кратны 776 по перемножению и единица в конце, которая вычитается в исходном выражении. Остаются кратные 776. При повышении степени каждый из членов будет иметь среди множителей 776 и единицу в конце как результат перемножения 1 на 1 из всех скобок. Все остальные комбинации множителей будут содержать 776. К чему такие усложнения и обходные пути? А! Кайф использования готовых формул с подставлением? ;-)
Прошу вас, не надо усложнять. В итоге это не советская олимпиада, а задача для пятиклашек, возможно со звёздочкой. Не нужно общих формул - достаточно выделить достаточный признак, множитель. Ах да, автор может справедливо спросить - в чём сложность и почему такие примитивные решения не видели? - Дело в том что не только советская математика изначально используется как перенос с одной стороны равенства в другую с упрощением, что рассматривается часто как решение. Поэтому операции дискретизации с выделением признака без переноса не свойственны мозгу, ограничивая математический аппарат и его развитие. Другими словами - у вас есть дурные математические привычки. Чтобы стать лучшим математиком в мире, к чему стремятся многие, их надо лишиться. Понимая что есть нераскрытый математический потенциал на примитивном уровне. И крайне серьёзный. Это же и причина отсутствия нахождения частных признаков Масков. Где приходится пояснять ему, как и росавиакосмосу, что дискретизация трубы с выделением и усилением таких признаков - тоже самое. А они переносят оттудава сюдой целыми кусками и ждут чуда, ходя по золоту и грубо используя лишь некоторые свойства. По сути проектирование вариативного трубопровода, с проявлением плазменных эффектов, это то чего лишается решение при рассмотрении уравнений мощности с характеристиками трубопровода при вот таких цельных переносах при расчётах скорости подачи топлива, выходной мощи, без понимания что каждый элемент, часть трубопровода является ракетным двигателем с некоторыми вырожденными характеристиками, из которых лепится большой трубопровод с агрегированными характеристиками, эффектами и движущей силой соответствующей по характеристикам. Так сложна и любая математическая часть в уравнении, при морфировании ведущая к морфированию уравнения в целом с проявлением других эффектов. Но вместо этого, при рассмотрении дискретной части, можно выделить одинаковый признак, как множитель здесь. Уйдя от морфирования после рассмотрения, что приводит к нахождению других математических уравнений и эффектов.
Как в том анекдоте: -умом понимаю, что четвертушка и четвертушка вместе будет пол литра, а математически выразить не могу. Теперь, пожалуйста, последнюю минуту рассуждений запишите в математических символах.
очевидно что x^n-1 делится на x-1, но можно было через модули еще х дает остаток 1 по мод(х-1) значит х^n дает остаток 1, а значит х^n-1 делится на x-1, у автора задачи 6-7 класса, а он утверждает что ее не решили советские школьники
Binomial Expansion The binomial theorem is also known as the binomial expansion which gives the formula for the expansion of the exponential power of a binomial expression. Binomial expansion of (x + y)n by using the binomial theorem is as follows, (x+y)n = nC0 xny0 + nC1 xn-1y1 + nC2 xn-2 y2 + ... + nCn-1 x1yn-1 + nCn x0yn; (776+1); согласно формуле , каждая составляющая суммы имеет множителем 776, следовательно делится на 776; рассмотрим только nCn x0yn: 1*(776)^0*1^n=1, но у нас есть еще -1;+1-1=0, остается все, что имеет множителем 776, а это значит, 777^777-1 делится на 776
М-м-м... Нет, тут что-то не то. Форма A^m - B^m = (A - B)*k (k, m - натуральные) не выполняется, например, для A = 3, В = 2 и m = 2... Или я что-то неверно понял.
А зачем так сложно? Вообще в вопросах делимости мы работать с остатками можем точно так же как и с числами 777 сравнимо с 1 по модулю 776. Ну и все у нас 1^777 -1=0. Я даже запарился посмотрел сравнение по модулю в школе проходят в 10 классе. Сумму геометрической прогрессии в 9. Бином ньютона в 11 классе. Автор очень странно говорит, вот типа первый способ плохой, школьники этого не знают. Формулы сокращенного умножения проходят в 7 классе, а сумму геометрической прогрессии в 9. Т.е. это как, они не знают программу 7 класса, но знают 9? Объективно для 7 класса эта задача со *, для 10 устная. Олимпиадной она может быть для 5, 6 класса. Когда школьники ничего не знают, а скорее на пальцах это доказывают. и вообще если олимпиадная задача сложна отсутствием знаний у школьника это плохая задача.
@@andreykolobikhin Вычислять множители (коэффициенты при степенях 776-ти) не понадобится: достаточно убедиться (а это следует автоматически из определения для числа сочетаний), что все они - числа целые.
Задача довольно простая, на ней можно проиллюстрировать принцип построения множителя k. Рассмотрим многочлен aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹ и домножим его сначала на a, потом на b. a(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ+aⁿ⁻¹b+aⁿ⁻²b²+…+aⁿ⁻⁽ʲ⁻¹⁾bʲ⁻¹+…+a²bⁿ⁻²+abⁿ⁻¹, b(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ⁻¹b+aⁿ⁻²b²+aⁿ⁻³b³+…+aⁿ⁻⁽ʲ⁻¹⁾bʲ⁻¹+…+abⁿ⁻¹+bⁿ. Видно что разность этих произведений равна aⁿ−bⁿ, т. е. (a−b)(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ−bⁿ. Немного поменяв знаки, можно получить aⁿ−bⁿ = (a+b)(aⁿ⁻¹−aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲ(-b)ʲ⁻¹+…+abⁿ⁻²−bⁿ⁻¹) для чётных n и aⁿ+bⁿ = (a+b)(aⁿ⁻¹−aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲ(-b)ʲ⁻¹+…−abⁿ⁻²+bⁿ⁻¹) для нечётных.
Это частный случай утверждения что
n^m-1 делится на n-1 без остатка.
Доказывается путем разложения многочлена x^m-1 на множители.
Корень уравнения x^m -1=0 очевидно x=1.
Соответственно x^m-1 можно представить как(x-1)•P(x), где P(x) это некий полином с целыми коэффициентами.
В нашем случае
х = 777
т.е 777⁷⁷⁷-1=(777-1)•P(777)=776•P(777), соответственно выражение делится на 776 нацело.
Толково и эффектно и без суммы геометрической прогрессии...
777 ⁷⁷⁷ = (776 + 1)⁷⁷⁷. По формуле *бинома Ньютона* представляем данную степень в виде многочлена. Последний член такого многочлена будет равен 1⁷⁷⁷ = 1, остальные члены -есть некие степени числа 776, помноженные на коэфициент, являющийся целым числом (вычисляется как число сочетаний). Итак, 777 ⁷⁷⁷ - 1 = (776 + 1)⁷⁷⁷ - 1, Здесь -1 и 1, получаемая в результате применения формулы бинома Ньютона, взаимно уничтожаются; остается выражение из степеней 776, очевидно, которое делится на 776 без остатка.
у меня получилось тоже такое же решение
Самое простое доаазательство. 10 секунд на решение.
@@MaximusU76 если школьник знает формулу бинома Ньютона))
Ну, есть такая формула сокращённого умножения, где А в степени Н минус Б в степени Н раскладывается, как (А-Б) умноженное на сумму раличных коэффициентов. Для А2-Б2 это (А-Б)(А+Б). То есть, исходя из этого в первой скобке находится для нашего примера как раз 777-1=776 и оно само на себя делится. Но вот как это доказать другим способом и как эта формула получается - я не знаю )
Сумма там будет как раз не "различных" коэффициентов, а единиц.
@@viktor-kolyadenko почему "единиц"? Для различной степени Н во второй скобке различный набор коээфициентов, умноженных на комбинации А и Б. Или мы говорим о разных вещах?
@@roden2208 , смотрите, есть общая формула:
x^n - y^n = (x - y)(x^[n-1] + x^[n-2]y +...+ y^[n-2]x + y[n-1])
По идее легко доказывается непосредственным умножением. То есть все "различные коэффициенты" получаются равными 1 (для суммы непарных степеней будут знаки чередоваться).
Метод математической индукции: 1) при n=1, остаток от деления 777 на 776 равен 1. 2) Пусть при n=k, остаток от деления 777^k на 776 равен 1. 3) тогда при n=k+1, 777^(k+1)=777^k×(776+1)=777^k×776+777^k, первое слагаемое делится нацело, а остаток от деления 777^k на 776 равен 1, по пункту 2). То есть, от первой степени, добавляя каждый раз по 1, получим что остаток от деления 777^777 на 776 равен 1. Но если отнять этот остаток, число 777^777-1 делится на 776.
Формула бинома Ньютона доказывается методом матем. индукции, поэтому более рационально (и проще) воспользоваться готовой формулой.
Любая разность степеней первой скобкой содержит a-b, a2-b2=(a-b) *(a+b), a3-b3=(a-b) *(...), также и далее a4-b4=(a-b) *(a+b) *(a2+b2), a5-b5= также даст (a-b) *(...), следовательно вышли на первую теорему в решении.
В комментариях правильно пишут про метод индукции. Проще всего доказать в общем случае, что для любых натуральных x и n, остаток от деления x^n на (x-1) будет равен единице.
Альтернативный вариант - показать, что это естественное свойство кольца вычетов по x, но этому в школе точно не учат 😂
Зачем индукция? Тут очевидно всё и раскрыто при возведении в степень. (x+1)^n =x*(...) +1
@@andreykolobikhin соглашусь, так проще
Можно проще. 777=3*259. И степень 777 можно представить в виде куба. И у нас получиться разность кубов. Раскладываем её и один из сомножителей будет 777-1=776.
Один из сомножителей будет 777^259-1, а не 776.
777^2=(776+1)^2 два члена кратны 776 по перемножению и единица в конце, которая вычитается в исходном выражении. Остаются кратные 776. При повышении степени каждый из членов будет иметь среди множителей 776 и единицу в конце как результат перемножения 1 на 1 из всех скобок. Все остальные комбинации множителей будут содержать 776.
К чему такие усложнения и обходные пути? А! Кайф использования готовых формул с подставлением? ;-)
Прошу вас, не надо усложнять. В итоге это не советская олимпиада, а задача для пятиклашек, возможно со звёздочкой. Не нужно общих формул - достаточно выделить достаточный признак, множитель.
Ах да, автор может справедливо спросить - в чём сложность и почему такие примитивные решения не видели?
- Дело в том что не только советская математика изначально используется как перенос с одной стороны равенства в другую с упрощением, что рассматривается часто как решение. Поэтому операции дискретизации с выделением признака без переноса не свойственны мозгу, ограничивая математический аппарат и его развитие. Другими словами - у вас есть дурные математические привычки.
Чтобы стать лучшим математиком в мире, к чему стремятся многие, их надо лишиться. Понимая что есть нераскрытый математический потенциал на примитивном уровне.
И крайне серьёзный. Это же и причина отсутствия нахождения частных признаков Масков. Где приходится пояснять ему, как и росавиакосмосу, что дискретизация трубы с выделением и усилением таких признаков - тоже самое. А они переносят оттудава сюдой целыми кусками и ждут чуда, ходя по золоту и грубо используя лишь некоторые свойства. По сути проектирование вариативного трубопровода, с проявлением плазменных эффектов, это то чего лишается решение при рассмотрении уравнений мощности с характеристиками трубопровода при вот таких цельных переносах при расчётах скорости подачи топлива, выходной мощи, без понимания что каждый элемент, часть трубопровода является ракетным двигателем с некоторыми вырожденными характеристиками, из которых лепится большой трубопровод с агрегированными характеристиками, эффектами и движущей силой соответствующей по характеристикам.
Так сложна и любая математическая часть в уравнении, при морфировании ведущая к морфированию уравнения в целом с проявлением других эффектов. Но вместо этого, при рассмотрении дискретной части, можно выделить одинаковый признак, как множитель здесь. Уйдя от морфирования после рассмотрения, что приводит к нахождению других математических уравнений и эффектов.
Можно просто сказать,что 777 сравнимо с единицей по модулю 776.и все,задача решена
В любом случае придётся привести доказательство остатка в 1 при возведении в степень.
@@andreykolobikhin это сразу следует из корректности операции умножения по модулю: ((a mod c) * (b mod c)) mod c = a*b mod c
Доказывается моментально с помощью модульной арифметики.
И доказательством остатка в единицу при возведении.
Как в том анекдоте: -умом понимаю, что четвертушка и четвертушка вместе будет пол литра, а математически выразить не могу. Теперь, пожалуйста, последнюю минуту рассуждений запишите в математических символах.
777^777 - 1 = (mod. 776) 1 ^ 777 - 1 = 0; то есть выражение по модулю 776 имеет такой же остаток при делении как и 0, следовательно оно делится
очевидно что x^n-1 делится на x-1,
но можно было через модули еще
х дает остаток 1 по мод(х-1) значит х^n дает остаток 1, а значит х^n-1 делится на x-1, у автора задачи 6-7 класса, а он утверждает что ее не решили советские школьники
Binomial Expansion
The binomial theorem is also known as the binomial expansion which gives the formula for the expansion of the exponential power of a binomial expression. Binomial expansion of (x + y)n by using the binomial theorem is as follows,
(x+y)n = nC0 xny0 + nC1 xn-1y1 + nC2 xn-2 y2 + ... + nCn-1 x1yn-1 + nCn x0yn; (776+1); согласно формуле , каждая составляющая суммы имеет множителем 776, следовательно делится на 776; рассмотрим только nCn x0yn: 1*(776)^0*1^n=1, но у нас есть еще -1;+1-1=0, остается все, что имеет множителем 776, а это значит, 777^777-1 делится на 776
Доказывается через разность кубов
Как доказать через разность кубов? Не подскажите?
Чесслово делится, отвечаю! Зуб даю
в точку 🤣
777 mod 776 = 1, 1^777 - 1 = 1 - 1 = 0, 0 делится на 776. В смысле этому не учат в школе и в смысле олимпиадная задачка?
М-м-м... Нет, тут что-то не то.
Форма A^m - B^m = (A - B)*k (k, m - натуральные) не выполняется, например, для A = 3, В = 2 и m = 2...
Или я что-то неверно понял.
Раздели на 777-1.
0:21
А можно ли 777 корень из этого выражения взять? Получится 777-1=776
Ничего сложного, и доказывается в две строчки по известной формуле а в степени эн минус б в степени н. Устно!
ЧИСЛИТЕЛЬ 777^777-1=А-1 ,ЗНАМЕНАТЕЛЬ А-1 А-1/А-1=1
Проще доказывается методом математической индукции
А лучше переменным током с индуктивной проводимостью
Ну на олимпиаде нужно не словами говорить. Где математические выкладки выражение в предикатной логике? )
Лайк за видео и два лайка за комментарии.
Здесь не нужно никаких формул:
777 - 1 = 776
777 * 777 - 777 = 776 * 777
(777 ^ 2 - 777) mod 776 = 0
(777 ^ 2 - 1 - 776) mod 776 = 0
(777 ^ 2 - 1) mod 776 = 0
777 ^ 2 - 1 = 776 * A1
777 ^ 3 - 777 = 776 * A1
(777 ^ 3 - 1 - 776) mod 776 = 0
(777 ^ 3 - 1) mod 776 = 0
...
(777 ^ N - 1) mod 776 = 0
777 в любой целой степени больше нуля с вычитанием единицы делится на 776
777-1=776. Поэтому 776|(777⁷⁷⁷-1).
Первый вариант интереснее. Правда???
А зачем так сложно? Вообще в вопросах делимости мы работать с остатками можем точно так же как и с числами 777 сравнимо с 1 по модулю 776. Ну и все у нас 1^777 -1=0. Я даже запарился посмотрел сравнение по модулю в школе проходят в 10 классе. Сумму геометрической прогрессии в 9. Бином ньютона в 11 классе. Автор очень странно говорит, вот типа первый способ плохой, школьники этого не знают. Формулы сокращенного умножения проходят в 7 классе, а сумму геометрической прогрессии в 9. Т.е. это как, они не знают программу 7 класса, но знают 9? Объективно для 7 класса эта задача со *, для 10 устная. Олимпиадной она может быть для 5, 6 класса. Когда школьники ничего не знают, а скорее на пальцах это доказывают. и вообще если олимпиадная задача сложна отсутствием знаний у школьника это плохая задача.
Мой лайк 777-й )))
(776+1)^777. Бином Ньютона. sapienti sat
В доказательстве автора его эквивалентные вариации. И в любом случае потребуется рассмотрение множителей.
@@andreykolobikhin Вычислять множители (коэффициенты при степенях 776-ти) не понадобится: достаточно убедиться (а это следует автоматически из определения для числа сочетаний), что все они - числа целые.
@@КоляЕгоров-лимб Кратные 776? ...
устная задача
Задача довольно простая, на ней можно проиллюстрировать принцип построения множителя k. Рассмотрим многочлен
aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹ и домножим его сначала на a, потом на b.
a(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ+aⁿ⁻¹b+aⁿ⁻²b²+…+aⁿ⁻⁽ʲ⁻¹⁾bʲ⁻¹+…+a²bⁿ⁻²+abⁿ⁻¹,
b(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ⁻¹b+aⁿ⁻²b²+aⁿ⁻³b³+…+aⁿ⁻⁽ʲ⁻¹⁾bʲ⁻¹+…+abⁿ⁻¹+bⁿ.
Видно что разность этих произведений равна aⁿ−bⁿ, т. е.
(a−b)(aⁿ⁻¹+aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲbʲ⁻¹+…+abⁿ⁻²+bⁿ⁻¹) = aⁿ−bⁿ.
Немного поменяв знаки, можно получить
aⁿ−bⁿ = (a+b)(aⁿ⁻¹−aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲ(-b)ʲ⁻¹+…+abⁿ⁻²−bⁿ⁻¹) для чётных n и
aⁿ+bⁿ = (a+b)(aⁿ⁻¹−aⁿ⁻²b+aⁿ⁻³b²+…+aⁿ⁻ʲ(-b)ʲ⁻¹+…−abⁿ⁻²+bⁿ⁻¹) для нечётных.
Тебе не лень было набирать?