целочислено уравнение с 3 неизвестни

[turtlefox]

[tex]12x^2 + y^2 = 2019^n \\
x, y, n \in \mathbb{N}[/tex]

Аз успях да изведа само някой тривиални неща като делимостта на отделните променливи, но така и не можах да намеря интервали за тях.
Предполагам, че при малко y, x и n ще трябва да са доста големи, и обратното.

[Добромир Глухаров]

Метод на безкрайното спускане:

Да предположим, че уравнението $12x^2+y^2=2019^n$ има решение в естествени x,y,n.

$2019=3.673$

$y=3y_1$ -> $12x^2+9y_1^2=3^n.673^n$

$4x^2+3y_1^2=3^{n-1}.673^n$

$n=1$ -> $4x^2+3y^2=673$ или $n>1\to x=3x_1$

$36x_1^2+3y_1^2=3^{n-1}.673^n$
$12x_1^2+y_1^2=3^{n-2}.673^n$

Значи, ако изходното уравнение има решение, решение трябва да има поне едно от уравненията $4x^2+3y^2=673\cup12x^2+y^2=673^2$.

Проверявайки краен брой двойки $(x\in\mathbb{N},y\in\mathbb{N})$, виждаме, че не съществува решение.

[pal702004]

Първото уравнение $4x^2+3y^2=673^n$ (при нечетно $n$) действително няма решения, защото лявата част е $3 \pmod 4$, а $673\equiv 1 \pmod 4$, но второто - при четни $n$ има решения, дори взаимнопрости $(x,y)$ за всяко четно $n$

Уравнението $u^2+3v^2=a$ има решения във взаимнопрости $(u,v)$ тогава и само тогава, когато всички прости делители на $a$ са $1\pmod 3$, в случая е така. Уравнението $12x^2+y^2=673^2$ има решение $x=100,y=577$
Малко по-късно ще продължа...работа.

[Добромир Глухаров]

Всъщност греша: като проверих двойките $(x,y)$, намерих решение $12.300^2+1731^2=2019^2$ и логиката на доказателството рухва, т.е. може да има решение и за по-големи $n$.

[Illuzion]

Следната задача е давана на областния кръг на националната олимпиада по математика през 2019г. Сигурен/на ли сте, че във вашата задача не се търсят всички $n,$ за които съществуват такива $x, y$?

[pal702004]

Решенията на горното уравнение е пряко свързано с уравнението $u^2+3v^2=673^k$, където u e нечетно, а v - четно. Решенията са:
$\\x=3^kuv\\\\y=3^k|u^2-3v^2|\\\\n=2k$

За $k=1$ имаме $u=25,v=4$

И за всяко следващо $k$, понеже $(25^2+3\cdot 4^2)(u^2+3v^2)=(25u \pm 12v)^2+3(25v \mp 4u)^2$ имаме:

$u_{k+1}=25u-12v,\;v_{k+1}=25v+4u$. Или $u_2=577,v_2=200,x_2=1038600,y_2=1916361$

Тук формулата с обърнатите знаци ще даде $v=x=0$, което си решение, разбира се, но тривиално.
При $k=3$ вече работят и двете рекурентни формули:

$u_{3.1}=16825,v_{3.1}=2692,x_3=1222908300,y_3=7056180891$

както и

$u_{3.2}=12025,v_{3.2}=7308,x_3=2372724900,y_3=421739109$

и т.н. Тук разглеждам само взаимнпопрости решения на уравнението $u^2+3v^2=673^k$ (по две за всяко k от $k=3$ включително нагоре). Разбира се, има решения и когата $u,v$ сa кратни на $673$

Така че не знам какво очакват авторите на задачата....рекурентна формула има, може разбира се да се напише и в аналитичен вид - две формули трябва да има. Може, разбира се, но едва ли е за олимпиада.

[pal702004]

Сега видях горния пост - има голяма разлика между $12x^2+y^2$ и $12x^2-y^2$

[Illuzion]

Сега видях горния пост - има голяма разлика между $12x^2+y^2$ и $12x^2-y^2$

Предположих, че задачата е за олимпиада, и затова попитах дали не е объркано условието.

[turtlefox]

Сега видях горния пост - има голяма разлика между $12x^2+y^2$ и $12x^2-y^2$

Предположих, че задачата е за олимпиада, и затова попитах дали не е объркано условието.

Да, действително съм я объркал когато съм я преписал оригинално. Много се извинявам, но ако може някой да обясни вярната версия ще е от много помощ.

[Illuzion]

Решение на вярната версия:

Търсят се всички числа $n,$ за които даденото уравнение има решение в естествени числа $x$ и $y,$ тоест за всяко $n$ е достатъчно да намерим само една такава двойка или да покажем, че няма нито една.

Първо ще покажем, че $n$ трябва да е нечетно число. Разглеждайки уравнението по модул $4,$ виждаме, че $$y^2\equiv -2019^n\equiv -3^n\pmod 4$$ което е възможно само при $2\nmid y$ и $2\nmid n.$ Така получихме необходимо условие за $n$ - то трябва да е нечетно. Ще покажем, че това условие е и достатъчно.

Да забележим, че ако $12x^2-y^2=2019^n$ за някое нечетно $n,$ то като заменим $(x, y)$ с $(2019x, 2019y),$ получаваме решение за числото $n+2,$ което също е нечетно. Затова е достатъчно да намерим решение на уравнението $$12x^2-y^2=2019^1$$ и след това като умножаваме $x$ и $y$ по $2019$ (колкото искаме пъти), ще генерираме решения за всяко нечетно $n.$

Не е трудно да се съобрази, че $12\cdot 13^2-3^2=2019.$ Готови сме!

[turtlefox]

Решение на вярната версия:

Търсят се всички числа $n,$ за които даденото уравнение има решение в естествени числа $x$ и $y,$ тоест за всяко $n$ е достатъчно да намерим само една такава двойка или да покажем, че няма нито една.

Първо ще покажем, че $n$ трябва да е нечетно число. Разглеждайки уравнението по модул $4,$ виждаме, че $$y^2\equiv -2019^n\equiv -3^n\pmod 4$$ което е възможно само при $2\nmid y$ и $2\nmid n.$ Така получихме необходимо условие за $n$ - то трябва да е нечетно. Ще покажем, че това условие е и достатъчно.

Да забележим, че ако $12x^2-y^2=2019^n$ за някое нечетно $n,$ то като заменим $(x, y)$ с $(2019x, 2019y),$ получаваме решение за числото $n+2,$ което също е нечетно. Затова е достатъчно да намерим решение на уравнението $$12x^2-y^2=2019^1$$ и след това като умножаваме $x$ и $y$ по $2019$ (колкото искаме пъти), ще генерираме решения за всяко нечетно $n.$

Не е трудно да се съобрази, че $12\cdot 13^2-3^2=2019.$ Готови сме!

Как от $y^2 \equiv -3^n \pmod 4 \implies n = 2k + 1$? Също така, как можем да заменим $(x, y)$ с $(2019x, 2019y)$, позволено е да скалираме променливите така? Разбирам специфично какво става като се заменят с $2019x$ и $2019y$ (можем да разделим двете страни на $2019^2$), но самата логика чрез, която се стига до заместването не ми е много ясна. Надявам се въпросите ми да не са много тъпи :/ и да се окаже, че е нещо супер очевидно.

[ptj]

[tex]2019 \equiv 3 \pmod4[/tex]

[tex]-y^2 \equiv 2019^n \equiv 3 ^n \equiv (-1)^n \pmod 4[/tex]

[tex]y[/tex] e нечетно, защото при деление на 4 нечетните числа дават остатък 1, а четните 0.

Самото решение е непълно, защото не доказва единствеността на намерените решения.

Може да се направи спускане по модул 3 ( защото 2019=3.673) за да се намери базово (минимално) решение...

П.П. Ако не сте запознати с теорията на "сравнения по модул", ще ви трудно да разберете логиката на решението.

[turtlefox]

[tex]2019 \equiv 3 \pmod4[/tex]

[tex]-y^2 \equiv 2019^n \equiv 3 ^n \equiv (-1)^n \pmod 4[/tex]

[tex]y[/tex] e нечетно, защото при деление на 4 нечетните числа дават остатък 1, а четните 0.

Самото решение е непълно, защото не доказва единствеността на намерените решения.

Може да се направи спускане по модул 3 ( защото 2019=3.673) за да се намери базово (минимално) решение...

П.П. Ако не сте запознати с теорията на "сравнения по модул", ще ви трудно да разберете логиката на решението.

Защо $y$ е нечетно разбирам, въпроса беше за $n$.

[Illuzion]

[tex]2019 \equiv 3 \pmod4[/tex]

[tex]-y^2 \equiv 2019^n \equiv 3 ^n \equiv (-1)^n \pmod 4[/tex]

[tex]y[/tex] e нечетно, защото при деление на 4 нечетните числа дават остатък 1, а четните 0.

Самото решение е непълно, защото не доказва единствеността на намерените решения.

Може да се направи спускане по модул 3 ( защото 2019=3.673) за да се намери базово (минимално) решение...

П.П. Ако не сте запознати с теорията на "сравнения по модул", ще ви трудно да разберете логиката на решението.

Моля прочетете условието от снимката:

Да се намерят всички естествени числа $n,$ за които уравнението $12x^2-y^2=2019^n$ ИМА решение в естествени числа.

[Illuzion]

Решение на вярната версия:

Търсят се всички числа $n,$ за които даденото уравнение има решение в естествени числа $x$ и $y,$ тоест за всяко $n$ е достатъчно да намерим само една такава двойка или да покажем, че няма нито една.

Първо ще покажем, че $n$ трябва да е нечетно число. Разглеждайки уравнението по модул $4,$ виждаме, че $$y^2\equiv -2019^n\equiv -3^n\pmod 4$$ което е възможно само при $2\nmid y$ и $2\nmid n.$ Така получихме необходимо условие за $n$ - то трябва да е нечетно. Ще покажем, че това условие е и достатъчно.

Да забележим, че ако $12x^2-y^2=2019^n$ за някое нечетно $n,$ то като заменим $(x, y)$ с $(2019x, 2019y),$ получаваме решение за числото $n+2,$ което също е нечетно. Затова е достатъчно да намерим решение на уравнението $$12x^2-y^2=2019^1$$ и след това като умножаваме $x$ и $y$ по $2019$ (колкото искаме пъти), ще генерираме решения за всяко нечетно $n.$

Не е трудно да се съобрази, че $12\cdot 13^2-3^2=2019.$ Готови сме!

Как от $y^2 \equiv -3^n \pmod 4 \implies n = 2k + 1$? Също така, как можем да заменим $(x, y)$ с $(2019x, 2019y)$, позволено е да скалираме променливите така? Разбирам специфично какво става като се заменят с $2019x$ и $2019y$ (можем да разделим двете страни на $2019^2$), но самата логика чрез, която се стига до заместването не ми е много ясна. Надявам се въпросите ми да не са много тъпи :/ и да се окаже, че е нещо супер очевидно.

Имаме сравнението $y^2\equiv -3^n\pmod 4$. Виждате, че $y$ трябва да е нечетно число, защото в противен случай получаваме $0\equiv y^2\pmod 4$, докато $y^2\equiv -3^n\pmod 4$ и няма как $4$ да дели $-3^n$.

Щом $y$ е нечетно, можем да запишем $y=2y_1+1$ за някое цяло число $y_1$ и сега забелязваме, че $$y^2=4y_1^2+4y_1+1\equiv 1\pmod 4$$ Така от сравнението следва, че $-3^n\equiv y^2\equiv 1\pmod 4$, тоест $3^n\equiv -1\equiv 3\pmod 4.$ От тук получаваме, че $n$ е нечетно. Може първо да си съставите таблица, за да го видите: $$3^1\equiv 3\pmod 4$$ $$3^2=9\equiv 1\pmod 4$$ $$3^3=27\equiv 3\pmod 4$$ $$3^4=81\equiv 1\pmod 4$$ и т.н.

Сега ще докажем, че при нечетно $n$ е изпълнено $3^n\equiv 3\pmod 4$, а при четно $n$ е изпълнено $3^n\equiv 1\pmod 4$.

Нека $n=2k$ е четно. Имаме $$3^n=3^{2k}=9^k=(8+1)^k\equiv 1\pmod 4$$
Нека $n=2k+1$ е нечетно. Имаме $$3^n=3^{2k+1}=3\cdot 3^{2k}=3\cdot 9^k\equiv 3\cdot 1=3\pmod 4$$
Значи $3^n\equiv 3\pmod 4$ е възможно само за нечетно $n$.


По въпроса за замяната на променливите - решението може да се запише малко по-адекватно. Вече знаем, че двойката $$(x_1, y_1)=(13, 3)$$ е решение на уравнението $12x^2-y^2=2019$. Сега за произволно нечетно $n=2k-1$ аз твърдя, че уравнението $12x^2-y^2=2019^n$ има решение. Това е двойката $$(x_k, y_k)=(13\cdot 2019^{k-1}, 3\cdot 2019^{k-1})$$

[ptj]

Извинявам се, наистина не бях прочел внимателно условието.

[georgi111]

Подпбна идея доста често се появява в един или друг вид на националната олимпиада и на ПМС/ЗМС ... Пример 3ти кръг '96та година зад.1 - https://imomath.com/othercomp/Bul/BulMO396.pdf. Иначе задачката е добра ...

[pal702004]

Подпбна идея доста често се появява в един или друг вид на националната олимпиада и на ПМС/ЗМС ... Пример 3ти кръг '96та година зад.1 - https://imomath.com/othercomp/Bul/BulMO396.pdf. Иначе задачката е добра ...

1. Prove that for all positive integers $n \ge 3$ there exist odd positive integers $x_n,y_n$ such that $7x_n^2+y_n^2=2^n$

Симпатична. За $n=3$ имаме решение $x_3=y_3=1$

И при $x_n \equiv y_n \pmod 4$

$x_{n+1}=\dfrac{x_n+y_n}{2},\;y_{n+1}=\dfrac{|7x_n-y_n|}{2}$


а при $x_n \not \equiv y_n \pmod 4$

$x_{n+1}=\dfrac{|x_n-y_n|}{2},\;y_{n+1}=\dfrac{7x_n+y_n}{2}$

и $x_{n+1},y_{n+1}$ също са нечетни. Използва се факта $7(a\pm b)^2+(7a\mp b)^2=8(7a^2+b^2)$