Непознато състезание по математика в BG/ продължава

[Knowledge Greedy]

11.3. a) Разложете [tex]x^5+x+1[/tex] на два множителя, всеки от които да е полином с цели коефициенти.
б) Решете уравнението [tex]x^5+x+1=y^3[/tex], където [tex]x[/tex] и [tex]y[/tex] са цели числа.

[peyo]

За а) решението е:
[tex](-x^3 + x^2 -1)(-x^2 -x -1)[/tex]

Как го намерих:

Търсим решение от вида:

(a*x^3 + b*x^2 + c*x +d)*(e*x^2 + f*x + g) = x^5 + x + 1

a*x^3 * (e*x^2 + f*x + g) + b*x^2 *(e*x^2 + f*x + g) + c*x *(e*x^2 + f*x + g) +d *(e*x^2 + f*x + g)

a*x^3 * e*x^2 + a*x^3 * f*x + a*x^3 * g
+ b*x^2 * e*x^2 + b*x^2 * f*x + b*x^2 * g
+ c*x * e*x^2 + c*x * f*x + c*x * g
+d * e*x^2 + d * f*x + d * g

a*e*x^5 + a*f*x^4 + a*g*x^3
+ b*e*x^4 + b*f*x^3 + b*g*x^2
+ c*e*x^3 + c*f*x^2 + c*g*x
+d*e*x^2 + d*f*x + d*g

a*e*x^5
+ a*f*x^4 + b*e*x^4
+ a*g*x^3 + b*f*x^3 + c*e*x^3
+ b*g*x^2 + c*f*x^2 + d*e*x^2
+ c*g*x + d*f*x
+ d*g

a*e*x^5
+ (a*f+ b*e ) * x^4
+ (a*g + b*f + c*e)*x^3
+ (b*g + c*f + d*e)*x^2
+ (c*g + d*f)*x
+ d*g

x^5 = a*e*x^5
0 = (a*f+ b*e ) * x^4
0 = (a*g + b*f + c*e)*x^3
0 = (b*g + c*f + d*e)*x^2
x = (c*g + d*f)*x
1 = d*g

Чудесно дотук. Сега едно решение е:
a = 1, e = 1
d = 1, g = 1

Давидим дали можем да опростим:
0 = f+ b
0 = 1 + b*f + c
0 = b + c*f + 1
1 = c + f

Хм, нещо не мога да отгатна лесен отговор. Да проверим с другото множество от решения дали няма да ни е по-лесно:
a = -1, e = -1
d = -1, g = -1

0 = -f - b
0 = 1 + b*f - c
0 = -b + c*f + 1
1 = -c -f

Да, много по-добре, от втория път отгатвам, че тези са решения:
f = -1, b = 1, c = 0

да проверим:
0 = 1 + 1*-1 - c
0 = -1 + 0*f + 1
1 = -0 --1

Точно!

Ок, финална проверка дали не сме сгрешили някой знак или нещо друго:
(-1*x^3 + 1*x^2 + 0*x +-1)*(-1*x^2 + -1*x + -1) = x^5 + x + 1

(-x^3 + x^2 -1)*(-x^2 -x -1) = x^5 + x + 1

-x^3 * -x^2 -x^3 * -x -x^3 *-1 + x^2 * -x^2 + x^2 *-x + x^2 *-1 -1*-x^2 -1*-x -1*-1=

x^5 +x^4 + x^3 -x^4 -x^3 -x^2 + x^2 +x + 1 =

x^5 + x + 1
^^^^^^^^^
Тадааааам! Което и търсим...

[Davids]

$x^5 + x + 1 =$
$= x^5 + x^2 - x^2 + x + 1 =$
$= x^2(x^3 - 1) + x^2 + x + 1 =$
$= x^2(x - 1)(x^2 + x + 1) + x^2 + x + 1 =$
$= (x^3 - x^2 + 1)(x^2 + x + 1)$

[pal702004]

Да, добре е да се знае, че ако $a,b,c$ образуват пълна група по модул 3, то полинома $x^a+x^b+x^c$ се дели на $x^2+x+1$ (може да се докаже с индукция).

По-интересно ми е условие б. Понеже има решения $x=0,x=-1$ то противоречие по никакъв модул не може да има.

$(x^2+x+1)(x^3-x^2+1)=y^3$

Ако двата множителя вляво са взаимнопрости, стигаме до системата

$\begin{cases} x^2+x+1=u^3\\x^3-x^2+1=v^3\end{cases}$

Решенията на второто уравнение са ограничени. Лесно се показва, че при $|x|>1$

$x^3<x^3-x^2+1<(x-1)^3$

и $x^3-x^2+1$ не може да е куб.

Лошото е, че двата множителя в ляво могат да имат общ делител 7 (при $x\equiv 4 \pmod 7$), а в системата

$\begin{cases} x^2+x+1=7u^3\\x^3-x^2+1=49v^3\end{cases}$

(или размемени коефициенти 7-49) не виждам засега нищо добро...направо е подтискащо.

[Sup3rlum]

....

Не съм много в час с дискретната математика, някой да ме поправи ако пиша пълни глупости. Това което виждам на пръв поглед - както pal702004 каза $(x^3-x^2+1)$ не е точен куб за $|x|>1$, следователно единствените вариант за $y^3$ e

[tex]\begin{cases} x^3-x^2+1=z^2u^3 \\ x^2+x+1=zu^3 \end{cases}[/tex]

(или $z, z^2$ обратно)

Ако се предположи, че $|u|>1$ и $|z|>1$ и са взаимно прости и $z \ne u$ и $|u|<|y|$, $|z|<|y|$.

Тогава $x^3-x^2+1=z(x^2+x+1)$, но по лемета на Гаус $x^3-x^2+1$ е примитивна и $x^2+x+1$ е примитивна следователно $|z|=1$.

Получава се:

[tex]\begin{cases} x^3-x^2+1=u^3 \\ x^2+x+1=\pm u^3 \end{cases}[/tex]

$|u|=|y|$

От това следствие, по-горните ни допускания са в противоречие, следва единствено е възможно $|x| \le 1$, |y| = 1. Като имаме в предвид тези ограничение, лесно излизат отговорите $x=0, x=-1$

[Knowledge Greedy]

11.3.а) За първата част на задачата предлагам следния "детски" подход (а химиците го наричат вкарване на катализатор в реакцията).
Да умножим
[tex]P(x)=x^5+x+1[/tex]
с двучлена [tex](x-1)[/tex].

[tex](x-1)(x^5+x+1)=x^6+x^2+x-x^5-x-1[/tex]
След опростяване получаваме
[tex](x-1)P(x)=x^6-x^5+x^2-1[/tex]
Групираме
[tex](x^6-1)-(x^5-x^2)=(x^3-1)(x^3+1)-x^2(x^3-1)=(x^3-1)\left [ (x^3+1)-x^2 \right ][/tex]
Следователно
[tex](x-1)P(x)=(x-1)(x^2+x+1) (x^3-x^2+1)[/tex]
Окончателно - като съкратим [tex](x-1)[/tex], получаваме
[tex]P(x)=(x^2+x+1) (x^3-x^2+1)[/tex]

[georgi111]

Решенията на второто уравнение са ограничени. Лесно се показва, че при $|x|>1$

$x^3<x^3-x^2+1<(x-1)^3$

Сигурен ли си ? Защото [tex]x^3 < x^3 -x^2 + 1[/tex](първото) е еквивалентно на [tex]x^2 < 1[/tex] , което не е еквивалентно на [tex]|x| > 1[/tex]

[grav]

Решенията на второто уравнение са ограничени. Лесно се показва, че при $|x|>1$

$x^3<x^3-x^2+1<(x-1)^3$

Сигурен ли си ? Защото [tex]x^3 < x^3 -x^2 + 1[/tex](първото) е еквивалентно на [tex]x^2 < 1[/tex] , което не е еквивалентно на [tex]|x| > 1[/tex]

Печатна грешка, очевидно е имал предвид $x^3>x^3-x^2+1>(x-1)^3$.

[georgi111]

Печатна грешка, очевидно е имал предвид $x^3>x^3-x^2+1>(x-1)^3$.

Хммм пак не е вярно ако [tex]|x| > 1[/tex] . Второто е еквивалентно с [tex]2x^2 - 3x -2 > 0[/tex], а то от своя страна с [tex]x \in (-\infty, -1/2)\cup (2, +\infty)[/tex], което очевидно не е изпълнено винаги когато [tex]|x| > 1[/tex] (например за [tex]x \in (1,2)[/tex]) ...

[georgi111]

Моята идея е следната - просто не ползваме а) . Разлагаме до [tex]x(x^4 + 1) = (y-1)(y^2+ y + 1)[/tex] (*). Това означава три неща :
1) [tex]x[/tex] и [tex]y-1[/tex] имат еднакви знаци
2) [tex]gcd(x, x^4+1)=1[/tex]
3) [tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex]
... ... ...

[pal702004]

Моята идея е следната
1) [tex]x[/tex] и [tex]y-1[/tex] имат еднакви знаци
2) [tex]gcd(x, x^4+1)=1[/tex]
3) [tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex]
... ... ...

1. Не виждам откъде следва. Единственото, което е сигурно е, че $y$ е нечетно.
По-нататък? Идеята каква е?

Да, да вляза и аз в твоя тон:
[tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex] - Това не е вярно.
Вярно е
[tex]gcd(y-1, y^2+y+1) \in \{1,3\}[/tex]

[georgi111]

Сега гледаме 2 случая :
1 сл) [tex]gcd (y-1, y^2+y+1)=3[/tex] т.е. [tex]y=3k+1[/tex] ([tex]k[/tex]-цяло). Условието (*) става:
[tex]x(x^4+1)=3k.3.(3k^2+3k+1)[/tex] откъдето [tex]9 | x[/tex] (защо ?) т.е. [tex]x=9x_1[/tex]([tex]x_1[/tex]-цяло). (*) стана:
[tex]x_1(9^4.x_1^4+1)=k(3k^2+3k+1)[/tex], където :
[tex]gcd(x_1, 9^4.x_1^4 +1) = gcd(k,3k^2+3k+1)=1[/tex] и освен това :
[tex]x_1 < 9^4.x_1^4 + 1, k < 3k^2+3k+1[/tex], откъдето имаме 2 логически възможности:
1.1)[tex]\begin{array}{|l}x_1=k \\9^4.x_1^4+1=3k^2+3k+1 \end{array}[/tex]
откъдето : [tex]9^4.k^4 = 3k(k+1)[/tex] т.е. [tex]3^7.k^3=k+1[/tex], което е невъзможно.
1.2)[tex]\begin{array}{|l}x_1=3k^2+3k+1 \\9^4.x_1^4+1=k \end{array}[/tex] (само за положителни [tex]k,x_1[/tex])
откъдето имаме : [tex]x_1=3(9^4.x_1^4+1)+3(9^4.x_1^4+1)+1[/tex]. Дясната страна дава остаък 7 при делене на [tex]x_1[/tex], докато лявата дава 0. Оттук имаме , че [tex]x_1 | 7[/tex] т.е. [tex]x_1 \in (1,7)[/tex](Да не забравяме, че 1.2) се реализира само за положителни числа [tex]k,x_1[/tex]).
1.2.1) [tex]x_1=1 \rightarrow k=0(k>0)- невъзможно[/tex]
1.2.2) [tex]x_1=7 \rightarrow k^2+k-2=0 \rightarrow k=1(k>0)[/tex]. Но отново имаме противоречие от 2рото условие на 1.2) оттам при [tex]k=1[/tex] имаме [tex]x_1=0[/tex].
С това установихме , че е невъзможно [tex]gcd(y-1, y^2+y+1)=3[/tex]. Остава [tex]gcd(y-1, y^2+y+1)=1[/tex]
Сега от (*) лесно се убеждаваме, че [tex]\begin{array}{|l}x=y-1 \\x^4+1=y^2+y+1 \end{array}[/tex](**)(Не може [tex]\begin{array}{|l}x=y^2+y+1 \\x^4+1=y-1 \end{array}[/tex], защото тогава имаме: [tex]x=y^2+y+1 > y -1 = x^4 + 1[/tex], т.е. [tex]x>x^4+1[/tex]).Ползвайки 2те условия на (**) получаваме последователно : [tex](y-1)^4= (y-1)^2 + 3y - 1[/tex] или [tex](y-1)^4 - (y-1)^2 - 3(y - 1) -2 = 0[/tex]. Последното равенство за цяло [tex]y[/tex] означава, че [tex](y-1) | 2[/tex] т.е. [tex](y-1) \in (-1,1,2,-2)[/tex] или [tex]y \in (0,2,3,-1)[/tex] или [tex](x,y) \in ((-1,0),(1,2),(2,3),(-2,-1))[/tex], никои от които не са решения. Ако [tex]y=1 \rightarrow x=0[/tex], което е решение. Ако [tex]x=y[/tex], (*) става [tex](x+1)(x^4-x^3+1)=1[/tex], откъдето получаваме само [tex]x=y=-1[/tex]
Окончателно решенията са [tex](x,y) \in ((0,1),(-1,-1))[/tex]

[georgi111]

Моята идея е следната
1) [tex]x[/tex] и [tex]y-1[/tex] имат еднакви знаци
2) [tex]gcd(x, x^4+1)=1[/tex]
3) [tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex]
... ... ...

1. Не виждам откъде следва. Единственото, което е сигурно е, че $y$ е нечетно.
По-нататък? Идеята каква е?

Да, да вляза и аз в твоя тон:
[tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex] - Това не е вярно.
Вярно е
[tex]gcd(y-1, y^2+y+1) \in \{1,3\}[/tex]

Да де това съм искал да кажа , но съм го написал латексово като интервал съжалявам

[georgi111]

Печатна грешка, очевидно е имал предвид $x^3>x^3-x^2+1>(x-1)^3$.

Хммм пак не е вярно ако [tex]|x| > 1[/tex] . Второто е еквивалентно с [tex]2x^2 - 3x -2 > 0[/tex], а то от своя страна с [tex]x \in (-\infty, -1/2)\cup (2, +\infty)[/tex], което очевидно не е изпълнено винаги когато [tex]|x| > 1[/tex] (например за [tex]x \in (1,2)[/tex]) ...

То x е цяло и тогава съм съгласен - очевидно вярно е ...

[pal702004]

И аз по т.1 се извинявам. Кой знае защо съм прочел "еднакви знаци" като "еднаква четност". Да, с еднакви знаци са. Но нататък....аз лично не виждам никаква перспектива.

[georgi111]

Третия пост по-горе е идеята ми

[pal702004]

откъдето имаме 2 логически възможности:

georgi1, допускаш, за съжаление, доста често срещана грешка - че решенията на уравнението
$A\cdot B=C\cdot D$ са само $A=C, B=D$ ( или разменени). Всъщност решенията в най-общ вид са:

$A=pq,B=rs,C=pr,D=qs$

в случая $p,q,r,s$ трябва да са взаимнопрости - и що да не са?
Няма хляб тука.

[ptj]

За б.) отоговорите са [tex](0;1)[/tex] и (-1;-1). Интересно ми е дали с тяхна помощ някой може да напише решение.

[ptj]

Моята идея е следната - просто не ползваме а) . Разлагаме до [tex]x(x^4 + 1) = (y-1)(y^2+ y + 1)[/tex] (*). Това означава три неща :
1) [tex]x[/tex] и [tex]y-1[/tex] имат еднакви знаци
2) [tex]gcd(x, x^4+1)=1[/tex]
3) [tex]gcd(y-1, y^2+y+1) \in (1,3)[/tex]
... ... ...

Случая когато делителя от 3.) е 1-ца е лесен.

1.) Десните множители и от двете страни са положителни,
сл. наличие на нулев множител ни дава директно решението (0;1)

2.)[tex]x=y-1[/tex] и [tex]x^4=y^2+y[/tex]:
Понеже [tex](y;y+1)=1[/tex] от второто получаваме [tex]y(y+1)=0 \Leftrightarrow x=0[/tex], но то води до кандидат-решения (0;0) и (0;-1).
И двете не изпълняват първото уравнение, сл. няма решение.

3.) [tex]x=\pm (y^2+y+1)[/tex] и [tex]x^4=\pm y[/tex]

При [tex]|x|\ge 2[/tex] горното очевидно няма решение. От останалите случаи лесно се проверява ,че решение е (-1;-1).

---------------------------------------------------------------
Остава да излъжеш случая с общия делител 3.

[pal702004]

допускаш, за съжаление, доста често срещана грешка

Който има мерак, да реши в естествени числа уравнението
$x(2x+1)=y(y+1)$

[Genie_Almo]

допускаш, за съжаление, доста често срещана грешка

Който има мерак, да реши в естествени числа уравнението
$x(2x+1)=y(y+1)$

Ха.. Изглежда, че има някакъв алгоритъм за решаване на някои класове от този род проблеми.


https://www.wolframalpha.com/input/?i=x(2x%2B1)%3Dy(y%2B1)+positive+integer+solutions

[pal702004]

Ха.. Изглежда, че има някакъв алгоритъм за решаване на някои класове от този род проблеми.

Свежда се до класическото уравнение на Пел $(4x+1)^2-2(2y+1)^2=-1$
По-нагледно е рекурентното решение:

$x_0=0,x_1=10,x_n=34x_{n-1}-x_{n-2}+8$

$y_0=0,y_1=14,y_n=34y_{n-1}-y_{n-2}+16$

Дадох го просто като нагледен пример на това, че при този вид уравнения да се смята че решения може да има само при равни множители от двете страни е наивно.

[Illuzion]

Да разгледаме уравнението $$(x^2+x+1)(x^3-x^2+1)=y^3$$ над $\mathbb{Z}$. Нека означим $d=(x^2+x+1, x^3-x^2+1)$ - най-големият общ делител на двата множителя отляво. Ако $d=1$, както беше посочено по-горе, получаваме $x^3-x^2+1=b^3$ за някое $b\in \mathbb{Z}$, но с оценки лесно получаваме решенията $(x, y)=(0, 1), (-1, -1)$.

Нека видим какво става при $d>1$. Имаме последователно $$d\mid x(x^2+x+1)-(x^3-x^2+1)=2x^2+x-1$$ $$d\mid 2(x^2+x+1)-(2x^2+x-1)=x+3$$ $$d\mid x^2+3x-x^2-x-1=2x-1$$ $$d\mid 2x+6-(2x-1)=7.$$ Значи $d=7$ и в частност имаме $x=7k+4$, както и два случая.

Първи случай: $7\parallel x^2+x+1$

$$\Rightarrow \begin{array}{|l} x^2+x+1=7a^3 \\ x^3-x^2+1=49b^3 \end{array}$$ за някои $a, b\in \mathbb{Z}$. Заместваме $x$ във второто уравнение и получаваме $$49k^3+77k^2+40k+7=7b^3.$$ Така $7\mid k$. Но сега от първото уравнение имаме $$a^3=7k^2+9k+3\equiv 3\pmod 7,$$ откъдето $a^6\equiv 3^2\equiv 2 \pmod 7,$ но това е противоречие с теоремата на Ферма-Ойлер.




Втори случай: $7\parallel x^3-x^2+1$

$$\Rightarrow \begin{array}{|l} x^2+x+1=49a^3 \\ x^3-x^2+1=7b^3 \end{array}$$ за някои $a, b\in \mathbb{Z}$. Замествайки $x$ в първото уравнение, получаваме $$7k^2+9k+3=7a^3,$$ откъдето следва $k\equiv 2\pmod 7$. Но сега от второто уравнение имаме $$b^3=49k^3+77k^3+40k+7\equiv 5k\equiv 3\pmod 7,$$ като отново имаме противоречие с теоремата на Ойлер-Ферма $-> b^6\equiv 3^2\equiv 2 \pmod 7$.

[pal702004]

Illuzion, отлично решение.