Советская олимпиадная задача

Мой канал в VK - yellow.school
Докажи, что 777⁷⁷⁷-1 делится на 776 без остатка.

[@Hobbitangle]

Это частный случай утверждения что 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 нацело.

[@antongoncharsky2827]

Толково и эффектно и без суммы геометрической прогрессии...

[@user-vn1wj3qq1j]

777 ⁷⁷⁷ = (776 + 1)⁷⁷⁷. По формуле *бинома Ньютона* представляем данную степень в виде многочлена. Последний член такого многочлена будет равен 1⁷⁷⁷ = 1, остальные члены -есть некие степени числа 776, помноженные на коэфициент, являющийся целым числом (вычисляется как число сочетаний). Итак, 777 ⁷⁷⁷ - 1 = (776 + 1)⁷⁷⁷ - 1, Здесь -1 и 1, получаемая в результате применения формулы бинома Ньютона, взаимно уничтожаются; остается выражение из степеней 776, очевидно, которое делится на 776 без остатка.

[@RUMACTEP]

у меня получилось тоже такое же решение

[@MaximusU76]

Самое простое доаазательство. 10 секунд на решение.

[@Ansinon777]

@@MaximusU76 если школьник знает формулу бинома Ньютона))

[@user-et7hf3cu1r]

Любая разность степеней первой скобкой содержит a-b, a2-b2=(a-b) *(a+b), a3-b3=(a-b) *(...), также и далее a4-b4=(a-b) *(a+b) *(a2+b2), a5-b5= также даст (a-b) *(...), следовательно вышли на первую теорему в решении.

[@roden2208]

Ну, есть такая формула сокращённого умножения, где А в степени Н минус Б в степени Н раскладывается, как (А-Б) умноженное на сумму раличных коэффициентов. Для А2-Б2 это (А-Б)(А+Б). То есть, исходя из этого в первой скобке находится для нашего примера как раз 777-1=776 и оно само на себя делится. Но вот как это доказать другим способом и как эта формула получается - я не знаю )

[@user-bf3ko7ts5e]

Сумма там будет как раз не "различных" коэффициентов, а единиц.

[@roden2208]

@@user-bf3ko7ts5e почему "единиц"? Для различной степени Н во второй скобке различный набор коээфициентов, умноженных на комбинации А и Б. Или мы говорим о разных вещах?

[@user-bf3ko7ts5e]

​@@roden2208 , смотрите, есть общая формула: x^n - y^n = (x - y)(x^[n-1] + x^[n-2]y +...+ y^[n-2]x + y[n-1]) По идее легко доказывается непосредственным умножением. То есть все "различные коэффициенты" получаются равными 1 (для суммы непарных степеней будут знаки чередоваться).

[@andreykolobikhin]

777^2=(776+1)^2 два члена кратны 776 по перемножению и единица в конце, которая вычитается в исходном выражении. Остаются кратные 776. При повышении степени каждый из членов будет иметь среди множителей 776 и единицу в конце как результат перемножения 1 на 1 из всех скобок. Все остальные комбинации множителей будут содержать 776. К чему такие усложнения и обходные пути? А! Кайф использования готовых формул с подставлением? ;-)

[@andreykolobikhin]

Прошу вас, не надо усложнять. В итоге это не советская олимпиада, а задача для пятиклашек, возможно со звёздочкой. Не нужно общих формул - достаточно выделить достаточный признак, множитель. Ах да, автор может справедливо спросить - в чём сложность и почему такие примитивные решения не видели? - Дело в том что не только советская математика изначально используется как перенос с одной стороны равенства в другую с упрощением, что рассматривается часто как решение. Поэтому операции дискретизации с выделением признака без переноса не свойственны мозгу, ограничивая математический аппарат и его развитие. Другими словами - у вас есть дурные математические привычки. Чтобы стать лучшим математиком в мире, к чему стремятся многие, их надо лишиться. Понимая что есть нераскрытый математический потенциал на примитивном уровне. И крайне серьёзный. Это же и причина отсутствия нахождения частных признаков Масков. Где приходится пояснять ему, как и росавиакосмосу, что дискретизация трубы с выделением и усилением таких признаков - тоже самое. А они переносят оттудава сюдой целыми кусками и ждут чуда, ходя по золоту и грубо используя лишь некоторые свойства. По сути проектирование вариативного трубопровода, с проявлением плазменных эффектов, это то чего лишается решение при рассмотрении уравнений мощности с характеристиками трубопровода при вот таких цельных переносах при расчётах скорости подачи топлива, выходной мощи, без понимания что каждый элемент, часть трубопровода является ракетным двигателем с некоторыми вырожденными характеристиками, из которых лепится большой трубопровод с агрегированными характеристиками, эффектами и движущей силой соответствующей по характеристикам. Так сложна и любая математическая часть в уравнении, при морфировании ведущая к морфированию уравнения в целом с проявлением других эффектов. Но вместо этого, при рассмотрении дискретной части, можно выделить одинаковый признак, как множитель здесь. Уйдя от морфирования после рассмотрения, что приводит к нахождению других математических уравнений и эффектов.

[@AlexeyEvpalov]

Метод математической индукции: 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.

[@user-vn1wj3qq1j]

Формула бинома Ньютона доказывается методом матем. индукции, поэтому более рационально (и проще) воспользоваться готовой формулой.

[@user-xv9fe4eo1b]

В комментариях правильно пишут про метод индукции. Проще всего доказать в общем случае, что для любых натуральных x и n, остаток от деления x^n на (x-1) будет равен единице. Альтернативный вариант - показать, что это естественное свойство кольца вычетов по x, но этому в школе точно не учат 😂

[@andreykolobikhin]

Зачем индукция? Тут очевидно всё и раскрыто при возведении в степень. (x+1)^n =x*(...) +1

[@user-xv9fe4eo1b]

@@andreykolobikhin соглашусь, так проще

[@vasiapupkin6516]

Можно проще. 777=3*259. И степень 777 можно представить в виде куба. И у нас получиться разность кубов. Раскладываем её и один из сомножителей будет 777-1=776.

[@AlexeyEvpalov]

Один из сомножителей будет 777^259-1, а не 776.

[@maynustv2646]

777^777 - 1 = (mod. 776) 1 ^ 777 - 1 = 0; то есть выражение по модулю 776 имеет такой же остаток при делении как и 0, следовательно оно делится

[@user-zv7dh4vh3d]

Можно просто сказать,что 777 сравнимо с единицей по модулю 776.и все,задача решена

[@andreykolobikhin]

В любом случае придётся привести доказательство остатка в 1 при возведении в степень.

[@88coolv]

@@andreykolobikhin это сразу следует из корректности операции умножения по модулю: ((a mod c) * (b mod c)) mod c = a*b mod c

[@larisamedovaya9097]

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

[@volsyb]

Доказывается моментально с помощью модульной арифметики.

[@andreykolobikhin]

И доказательством остатка в единицу при возведении.

[@strodion2105]

777 mod 776 = 1, 1^777 - 1 = 1 - 1 = 0, 0 делится на 776. В смысле этому не учат в школе и в смысле олимпиадная задачка?

[@B.Anthony]

Как в том анекдоте: -умом понимаю, что четвертушка и четвертушка вместе будет пол литра, а математически выразить не могу. Теперь, пожалуйста, последнюю минуту рассуждений запишите в математических символах.

[@nomad7966]

Чесслово делится, отвечаю! Зуб даю

[@diez4005]

в точку 🤣

[@user-zv5ln1er7b]

Ничего сложного, и доказывается в две строчки по известной формуле а в степени эн минус б в степени н. Устно!

[@femalesworld2]

😢😢😢

[@zhansharkhanov4087]

очевидно что x^n-1 делится на x-1, но можно было через модули еще х дает остаток 1 по мод(х-1) значит х^n дает остаток 1, а значит х^n-1 делится на x-1, у автора задачи 6-7 класса, а он утверждает что ее не решили советские школьники

[@zhorzhhz]

А можно ли 777 корень из этого выражения взять? Получится 777-1=776

[@alexalex7543]

Лайк за видео и два лайка за комментарии.

[@shvlad1]

Доказывается через разность кубов

[@user-qn5nw3ve4t]

Как доказать через разность кубов? Не подскажите?

[@diez4005]

Ну на олимпиаде нужно не словами говорить. Где математические выкладки выражение в предикатной логике? )

[@user-uw7mb7fo5y]

777 в любой целой степени больше нуля с вычитанием единицы делится на 776

[@user-so5lf1yu6r]

Проще доказывается методом математической индукции

[@egon8345]

А лучше переменным током с индуктивной проводимостью

[@ILYA1991RUS_Socratus]

Раздели на 777-1. 0:21

[@user-ls4cc6op5r]

ЧИСЛИТЕЛЬ 777^777-1=А-1 ,ЗНАМЕНАТЕЛЬ А-1 А-1/А-1=1

[@Mike-hp3fh]

Здесь не нужно никаких формул: 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

[@starmgu]

А зачем так сложно? Вообще в вопросах делимости мы работать с остатками можем точно так же как и с числами 777 сравнимо с 1 по модулю 776. Ну и все у нас 1^777 -1=0. Я даже запарился посмотрел сравнение по модулю в школе проходят в 10 классе. Сумму геометрической прогрессии в 9. Бином ньютона в 11 классе. Автор очень странно говорит, вот типа первый способ плохой, школьники этого не знают. Формулы сокращенного умножения проходят в 7 классе, а сумму геометрической прогрессии в 9. Т.е. это как, они не знают программу 7 класса, но знают 9? Объективно для 7 класса эта задача со *, для 10 устная. Олимпиадной она может быть для 5, 6 класса. Когда школьники ничего не знают, а скорее на пальцах это доказывают. и вообще если олимпиадная задача сложна отсутствием знаний у школьника это плохая задача.

[@-wx-78-]

Задача довольно простая, на ней можно проиллюстрировать принцип построения множителя 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ⁿ⁻¹) для нечётных.

[@egon8345]

Тебе не лень было набирать?

[@user-uh6hz7zo3u]

Первый вариант интереснее. Правда???

[@Joseph052]

устная задача

[@user-xs8dj5jl2i]

(776+1)^777. Бином Ньютона. sapienti sat

[@andreykolobikhin]

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

[@user-vn1wj3qq1j]

@@andreykolobikhin Вычислять множители (коэффициенты при степенях 776-ти) не понадобится: достаточно убедиться (а это следует автоматически из определения для числа сочетаний), что все они - числа целые.

[@andreykolobikhin]

@@user-vn1wj3qq1j Кратные 776? ...