Математическое и загадочное

[E.K.]

Непонятно, зачем нужно оперировать такими большими величинами?

"Во-первых, это красиво" (с) старый анекдот.

Во-вторых, некоторым очень нравится разминать свой мозг.

В-третьих, есть такая штука "криптография", которая очень любит большие и странные числа.

[E.K.]

Итак, текущая задачка звучит так: Решить в натуральных числах уравнение (1 + n^a)^b = 1 + n^c

 

Для разминки попробуем поиграться с 'b'... и сразу отсекаем "b=1", поскольку получается тривиальное равенство с бесконечным количеством решений.

 

Пусть b=2. Тогда условие звучит так: (1 + n^a)² = 1 + n^c

Разворачиваем скобки..

 

(1 + n^a)² = 1 + 2*n^a + n^2a = 1 + n^c

2*n^a + n^2a = n^c

 

Делим на n^a и получается..

 

2 + n^a = n^(c-a)

 

или:

 

n^a * (n^(c-2a) - 1)  = 2 = 2*1 (или 1*2, но тогда n=1 и второй множитель = 0).

 

Отсюда сразу: n=2, a=1, b=2, c=3 - первое решение.

[E.K.]

Лучший (по мне) способ искать правильный метод решения подобных задачек - потренироваться "на кошечках". С квадратом решили. Посмотрим что с кубом и четвёртой степенью.

 

Куб. b=3  =>

 

(1 + n^a)³ = 1 + n^c

1 + 3n^a  + 3n^2a + n^3a = 1 + n^c

n^a * (3 + 3n^a + n^2a ) = n^c

3 + 3n^a + n^2a = n^(c-a)

3 = n^a * (n^(c-2a) - n^a - 3)

 

3=3*1. Получаем n=3, a=1, всё на этом. Правая часть произведения никак не может быть единицей (3 в степени никак не станет семёркой, чтобы внутри скобок получилась единица). Не сходится, решений нет.

 

Далее. b=4  =>

 

(1 + n^a)⁴ = 1 + n^c

1 + 4n^a + 6n^2a + 4n^3a + n^4a  = 1 + n^c

4 = n^a * (n^(c-2a) - 6 - 4n^a – n^2a)

 

4=4*1 => n=4, a=1, но тогда внутри скобок должна получиться единица. Но там же всё чётное. Нет, не работает.

4=2*2 => n=2, a=1, (n^(c-2a) - 6 - 4n^a – n^2a) = (2^(c-2) - 6 - 4*2 – 2²) = 2^(c-2) - 6 - 8 - 4 = 2^(c-2) - 18 = 2, то есть, 2^(c-2) = 20. Быть такого не может.

 

Для 4 решений тоже нет.

[E.K.]

А если на нашу штуку (1 + n^a)^b = 1 + n^c посмотреть вот таким образом:

 

(1 + n^a)^b - 1 = n^c

 

Пусть b чётное, то есть b=2d. Тогда:

 

(1 + n^a)^2d - 1 = n^c

 

Так оно на множители раскладывается:

 

((1 + n^a)^d – 1) * ((1 + n^a)^d + 1) = n^c

 

Хммм, пусть (1 + n^a)^d - 1 = x. Тогда

 

x*(x+2) = n^c

 

Вот смотрю я на эти красивые формулы.. Что-то замечательное в них просто явно скрывается. Но что-то я пока не вижу... Помогайте.

[E.K.]

Хорошо, можно тупо в лоб бахнуть Биномом Ньютона и биномиальными коэффициэнтами ->

 

(1 + n^a)^b = 1 + n^c

 

плюс-единицы сразу сокращаю, чтобы глаз не мозолили..

 

b*n^a + C₂*n^2a + C₃*n^3a + … + b*n^(b-1)a + n^ba = n^c ;

 

Где C_x - это биномиальные коэффициэнты по b (если кто забыл Бином Ньютона - тыкайте на Википедию по ссылкам выше).

И тут видно, что оно всё делится на n^a , можно сократить...
 

b + C₂*n^a + C₃*n^2a + … + b*n^(b-2)a + n^(b-1)a = n^c-a ;

 

Но тогда что получается. Степень (c-a) больше (b-1)*a , то есть, оно всё снова делится на n^a , то есть и b тоже делится на n^a , о как!

 

Ну, пусть тогда b=B₁*n^a , какой профит из этого можно выцепить? А вот какой. Заменяем b на B₁*n^a и сокращаем n^a ->

 

B₁*n^a + C₂*n^a + C₃*n^2a + … + b*n^(b-2)a + n^(b-1)a = n^c-a ;

B₁ + C₂ + C₃*n^a + … + b*n^(b-3)a + n^(b-2)a = n^c-2a ;

 

Далее аналогично B₁ + C₂ = B₂*n^a , пока не доползём до самого края:

 

B_(b-1) + n^a = n^c-ba ;

 

Тут наверняка можно разгуляться мыслью по древу, но что-то завтра вылет ранний.. Пора на временный покой.

[E.K.]

Не, а что на покой-то? Копать глубже! С нами же смелость, отвага и Бином Ньютона!

 

B_(b-1) + n^a = n^c-ba ;

 

А вам не кажется, это самое B-c-хвостиком делится на n ? При чём неоднократно.. Пусть B = q*n , тогда получаем:

 

q*n + n^a = n^c-ba

 

Если разделить на n , то есть два варианта:

 

q + n^a-1 = n^c-ba-1

q + n^a-1 = 1  (то есть, c-ba=1)

 

Ой, мы же работаем в натуральных числах, то есть, целых больше нуля. Второго варианта быть никак не может! То есть, этот q тоже делится на n ... до тех пор, пока не получится вот такая краказябра:

 

q + n = n^z  (z - уже неважно что).

 

То есть, два варианта: 1) q=n или 2) q=n*(p-1) , тогда:

 

1:       2n = n^z, что даёт n=2, z=2 и решение, которое было получено в самом начале.

 

2:       n*(p-1) + n = n^z , отсюда два варианта сокращения на n ->

 

2.1:    (p-1) + 1 = 1 , но такого в нашем множестве натуральных чисел быть не может никак.

2.2:    (p-1) + 1 = n^z-1

 

То есть, p = n^z-1  ... и что?

 

А пока ничего. Это значит, что это Чёрное море ещё не до конца докопано. Я пошёл думать спать...

[Fireman]

Можно попробовать такой подход:

 

для удобства заменю n на x

 

Требуется найти натуральные решения уравнения

 

(1 + x^a)^b = 1 + x^c

 

Для начала рассмотрим простые случаи, чтобы внести какие-то ограничения для x, a, b, c

 

1) пусть b = 1, тогда

 

x - любое натуральное число, a = c - любое натуральное число

 

поэтому в будущем будем рассматривать случаи, когда b > 1

 

2) пусть x = 1, тогда

 

(1 + 1^a)^b = 1 + 1^c

2^b=2

b=1

 

т.е. x = 1, a - любое натуральное число, b = 1, c - любое натуральное число

 

поэтому в будущем будем рассматривать случаи, когда x > 1

 

3) пусть x > 1, b > 1 и разберем этот случай

 

Для начала применим формулу бинома Ньютона к левой части уравнения: sum(b!/[(b-k)!k!]*(x^a)^k, k=0..

 

и вынесем некоторые коэффициенты за скобки, получим:

 

1 + bx^a(1 + z) + (x^a)^b = 1 + x^c

 

где

 

z = sum((b-1)!/[(b-k)!k!]*(x^a)^k-1, k=2..b-1) = (x^a) * g(x)

 

член разложения, который нам пока не понадобится

 

Упрощаем исходное уравнение и получаем:

 

b * (1 + (x^a) * g(x)) = x^ab-a * (x^c-ab - 1)

 

Видно, что (1 + (x^a) * g) не делится на x (будет всегда остаток 1), а это значит, что b делится на x и даже больше - b делится на x^ab-a.

 

Разложим теперь (x^c-ab - 1) на множители и получим известную формулу

 

(x^c-ab - 1) = (x - 1)(1 + x + x² + ... + x^c-ab-1)

 

b * (1 + (x^a) * g) = (x - 1)(1 + x + x² + ... + x^c-ab-1)

 

Если вспомнить чему равно (1 + (x^a) * g) - то это многочлен с (x^a) в разных степенях и что важно (!!!) с положительными коэффициентами, т.е. 

 

1 + (x^a) * g = 1 + p₁x^a + p₂x^2a + ... + p_nx^a(b-2)

 

где коэффициенты p_i - натуральные числа (старшие факториалы делить на младшие факториалы)

 

А поэтому (1 + (x^a) * g) НЕ ДЕЛИТСЯ на (x - 1)

 

Значит b длится на (x - 1)

 

Т.е. b можно записать как 

 

b = x^{ab-a _*} (x - 1) * r

 

где r - это член разложения (1 + x + x² + ... + x^c-ab-1) (если оно конечно раскладывается )

 

Рассмотрим минимально возможный вариант:

 

(1 + x + x² + ... + x^c-ab-1) не раскладывается на множители

 

Значит

 

b = x^ab-a _* (x - 1) 

 

(1 + (x^a) * g) = (1 + x + x² + ... + x^c-ab-1)

 

И надо решить эту систему из двух уравнений.

 

Помогает то, что x^b расчёт значительно быстрее b и поэтому найти коэффициенты (для натуральных чисел) можно обычным перебором, например:

 

пусть x = 2, тогда

 

b = 2^a(b-1)

 

даже если a будет минимальным (a = 1), то b = 2 и все, дальше слишком быстрый рост 2^a(b-1) обгонит линейный рост b и других коэффициентов не будет

 

в результате получаем решение x = 2, a = 1, b = 2, c = 3

 

пусть x = 3, тогда

 

b = 2 * 3^{a(b - 1)}

 

и уже ни при каких значениях b мы не сможем решить это уравнение, тоже касается тем более и для более высоких x

 

Описанный выше минимальный случай можно рассмотреть решая и второе уравнение:

 

(1 + (x^a) * g) = (1 + x + x² + ... + x^c-ab-1)

 

тут все просто - многочлены равны, значит они должны иметь одинаковые степени и коэффициенты.

 

 

Рассмотрим теперь случай, когда (1 + x + x² + ... + x^c-ab-1) все таки раскладывается на произведение многочленов, тогда получится

 

b = x^ab-a _* (x - 1) * f(x)

 

где

 

f(x) - многочлен некоторой степени x

 

И опять все "портит" x^ab-a - он слишком быстро расчет в отличии от b, и никаких других вариантов, чем те, что мы рассмотрели выше мы не получим

 

-------------------------

 

Немного дополнений:

 

Пусть

 

w = b / x^ab-a 

 

Тогда приведённое выше уравнение можно переписать в виде

 

w * (1 + (x^a) * g) = x^c-ab - 1

 

или перекинув члены направо и налево

 

w + w * (x^a) * g) = x^c-ab - 1

w + 1 = x^a * (x^c-ab-a - w * g)

 

откуда видно, что (w + 1) делится на x

 

Но получается, что 

 

w + 1 = b / x^ab-a + 1 

 

делится на x, а это возможно только когда b имеет следующий вид

 

b = x^ab-a * (p₁x + p₂x² + ... + p_nxⁿ - 1) 

 

И в описанном случае минимально было n = 1, p₁=1

[E.K.]

0. Приношу извинения за личные тормоза. График жизни как-то опять был беспросветно-непрерывный.

 

1. Решение вроде верное. Я тоже шёл по этой дороге (разложение, биномиалы и b "улетает в космос"), но когда "обдумывание свежим мозгом" случается только импульсами по 10-15-20 минут, то решение подобных задачек может занять месяц-два..

 

2. Крайняя запись в моих измышлениях такая:

 

C₁*( 1 + n^a(b-2) ) + C₂*n^a *( 1 + n^a(b-4) ) + C₃*n^2a * ( 1 + n^a(b-5) ) + … + C_[b/2]*n^{a ??? (b-2)} = n^c-a - n^a(b-1)

 

То есть, я лишь чуть-чуть не дотянул до решения.. Увы.

 

3. Давайте решать задачки попроще. А то такие зубодробилки не всем доставляют удовольствие..

[E.K.]

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

 

Есть некоторая сумма факториалов 1! + 2! + 3! + ... + n!.

Доказать, что найдется такое n, что эта сумма будет иметь простой делитель, больше 2019²⁰¹⁹.

 

Пробуйте. Биномиалов и функций Эйлера не потребуется, обещаю!

 

UPD: Ой, что-то я погорячился.. Не 15 это минут. Просто утренний ум перепутал какая левая-правая часть равенства на какие простые делится..

[E.K.]

Что-то я опять пообещал простую задачку и опять всех обманул. Что-то пока не очень получается...

 

Кстати, однажды мы уже решали задачку про сумму факториалов, помните? Вот здесь она: https://forum.kasperskyclub.ru/index.php?showtopic=54210&p=839847

 

Новая задачка про факториалы значительно интереснее. Что-то не получается у меня сквозь неё пробиться. Вдруг у кого идеи возникнут?

 

Итак, есть некая сумма S(n) = 1! + 2! + 3! + ... + n!

Что мы про неё знаем?

 

1. S(n) всегда нечётна.

2. S(n) почти сразу делится на 3, а потом и на 9.

3. Можно раскрутить её на несколько шагов и увидеть, что один из простых делителей почти моментально улетает "в космос" в бесконечность:

 

n   n!        S(n)

1   1         = 1

2   2         = 3

3   6         = 9

4   33        = 3*11

5   153       = 9*17

6   873       = 9*97

7   5913      = 9*9*73

8   46233     = 9*11*467

9   409113    = 9*131*347

10  4037913   = 9*11*40787

 

Какая-то вот такая картинка. Сразу понятно откуда возникла задачка. Глядя на крайний правый делитель у настоящих криптографов сразу возникает желание максимально дёшево получать максимально большие простые числа Ведь S(n) считается "бесплатно": за два действия (умножение и сложение) получаем очередное значение последовательности. Это просто кладезь простых чисел!! .. Но я отвлёкся.

 

Конда условие задачки звучит "доказать, что в этой формуле будет всегда то-то или вот такое-то" - это означает, что решать задачку надо от обратного.То есть ->

 

Предположим, что в разложении всех S(n) есть максимальное простое число. То есть, набор всех простых делителей S(n) конечен. Пусть их будет... пять. Какая разница?   Это {p₁,p₂,p₃,p₄,p₅}. Соответственно, количество комбинаций разложения S(n) на простые множители (без учёта их степеней) тоже конечно.

 

Последовательность S(n) - бесконечна. Соответственно, существуют S(n) и S(n+k) из одного набора простых делителей (но с разными степенями). Причём количество вариантов {n,k} бесконечно для каждого набора простых делителей. То есть,

 

S(n+k) - S(n) = (n+1)! + (n+2)! + ... + (n+k)! = P*( a-b )

 

где P=наибольший общий делитель (НОД) S(n+k) и S(n), а ( a-b ) остатки от деления на НОД.

 

Попробуем сумму факториалов разложить на множители:

 

(n+1)! * ( 1 + (n+2) + ... + ((n+2)*...*(n+k)) )   = P*( a-b )

 

А вот далее я заткнулся. Логика дальнейшего доказательства мне кажется такой:

- левая часть очень быстро "улетает в космос".

- правая же ограничена конечным набором простых чисел, "уносить" правую часть "в космос" можно только их степенями.

 

 

Но как показать это математически... я пока теряюсь. Помощи от зала уже не жду, что-то опять запредельной сложности задачку мне подкинули..

[Fireman]

Что в решениях очень не хватает, так это математического редактора, чтобы можно было писать что нибудь типа [math]x^2 - y_1 = \frac{1}{2}[/math], а то смайлики побеждают.

 

Помощи от зала уже не жду

 

 

 

действительно, задачу удобно доказывать от противного и очень пригодятся делители для разных S(n)

 

и пригодится приведённый выше факт то, что числа S(n) и S(k) могут делиться не просто на какое-то простое число p, а на простое число, но с разными степенями (p^a и p^b)

 

 

Для удобства можно ввести функцию f_p(n) определения степени такого простого делителя p для числа S(n)

у этой функции f_p есть очевидное свойство, что  f_p(n+k) = min(f_p(n), f_p(k))

 

Для доказательство пригодится одна лемма (даже леммка, но из-за таких леммок доказательства и становятся большими и некрасивыми  )

 

Лемма:

 

Если f_p(S_n) < f_p((n+1)!) при некотором n, тогда f_p(S_n) =  f_p(S_k) при всех k >= n.

 

Доказательство: 

 

Для удобства обозначим a = f_p(S_n), b = f_p((n+1)!). Из условия следует, что b >= a + 1.

В сумме S_k = Sn + (n + 1)! + ... + k! все слагаемые кроме первого делятся на p^a+1, а вот первое по условию леммы делится только на p^a.

А значит и S_k делится только на p^a, но никак не на p^a+1.

 

Доказано.

 

А дальше можно рассматривать простые множители меньше искомого 2019²⁰¹⁹ , как верхней границы для некоторого числа S_n, и приходить к противоречию в рассуждениях.

Или если зайти с другого боку можно показать, что f_p(S_n) = f_p(n!) для любого n кратного p, предположить обратное и придти опять к противоречию.

Изменено 22 марта, 2019 пользователем Fireman

[E.K.]

Очень простая задачка! Честное слово! Я решил за несколько минут.

 

Найти все целые решения уравнения y^2 = x^3 + 1

[thyrex]

x₁ = -1, y₁ = 0
x₂ = 0, y₂ = -1
x₃ = 0, y₃ = 1

 

+ 

x₄ = 2, y₄ = -3
x₅ = 2, y₅ = 3

Изменено 23 марта, 2019 пользователем thyrex
коррекция

[E.K.]

Выкладки тоже приветствуются!

[E.K.]

Очень простая задачка! Честное слово! Я решил за несколько минут.

Найти все целые решения уравнения y^2 = x^3 + 1

 

Ой-ой, что-то я опять погорячился.. Не такая и тривиальная оказалась эта задачка в общем случае. Короче, дело на первый взгляд вот такое несложное:

 

y^2 = x^3 + 1

y^2 - 1 = x^3

(y + 1)*(y - 1) = x^3

 

=>

х=0, y={-1,1}

x!=0, то два варианта: { y+1=x² ; y-1=x } , { y+1=x ; y-1=x² }

 

Вычитаем второе из первого (в обоих вариантах) и помним, что работаем в целых числах, то есть, 2=1*2 или 2=(-1*-2) =>

 

1) 2 = x² - x = x*(x-1)  =>  {x=2, x-1=1} или {x=-2, x-1=-1 не сходится, быть не может такого} или {x=1, x-1=2 тоже мимо} или {x=-1, x-1=-2}

2) 2 = x - x² = x*(1-x)  =>  {x=2, 1-x=1 мимо} или {x=-2, 1-x=1 мимо} или {x=1, 1-x=2 мимо} или {x=-1, 1-x=2}

 

Итого, элементарные решения: {0, +-1}, {2,+-3}, {-1,0}

 

Вроде бы всё, но... есть нюанс... А кто сказал, что разложение на множители внутри скобок (y + 1)*(y - 1) = x^3 однозначно проецируется на (x^2)*(x) или на (x)*(x^2) ? А вдруг (y+1) и (y-1) раскладываются на хитрую комбинацию множителей, которые в результате дают куб какого-то другого целого числа?

 

Ага, сиё есть засада, доказательство которой есть не самая сложная, но и не самая тривиальная задачка.

 

Итак, надо доказать, что приведённые выше решения уравнения являются единственными. Для этого будем решать задачку немного другим способом.