Matematikos olimpiadinis uždavinys Nr. 14***

Sąlyga.

Raskite diofantinės lygties
[tex]41x+17y=2[/tex]
bendrąjį sprendinį.

[spoiler]

[tex]y=\frac{2-41x}{17}=-2x+\frac{2-7x}{17}[/tex].
Aišku, kad [tex]\frac{2-7x}{17}\in\mathbb{Z}[/tex].
[tex]\frac{2-7x}{17}=t_1(t_1\in\mathbb{Z})\Rightarrow x=\frac{2-17t_1}{7}=-2t_1+\frac{2-3t_1}{7}\\\frac{2-3t_1}{7}=t_2(t_2\in\mathbb{Z})\Rightarrow t_1=\frac{2-7t_2}{3}=-2t_2+\frac{2-t_2}{3}[/tex]
[tex]\frac{2-t_2}{3}=t(t\in\mathbb{Z})\Rightarrow t_2=2-3t[/tex].
Tada [tex]t_1=\frac{2-7(2-3t)}{3}=7t-4\\x=\frac{2-17(7t-4)}{7}=10-17t\\y=-24+41t[/tex]

Ats.: [tex]x=10-17t\\y=-24+41t[/tex]

Šį sprendimą mums pasiūlė mūsų forumo narys lukasm.
Ačiū Jam!

[/spoiler]

pradžioj patikrinam ar DBD lygus 1.

tada sudarom euklido algoritmą
[tex]\begin{pmatrix}
1 & 0  & 41\\
0 & 1 & 17
\end{pmatrix}[/tex] [tex]\begin{pmatrix}
1 & -2  & 7\\
0 & 1 & 17
\end{pmatrix}[/tex] [tex]\begin{pmatrix}
1 & -2  & 7\\
-2& 5 & 3
\end{pmatrix}[/tex]
[tex]\begin{pmatrix}
5 & -12  & 1\\
-2& 5 & 3
\end{pmatrix}[/tex]

[tex]5\cdot41-12\cdot17=1[/tex]

[tex](5\cdot2)\cdot41-(12\cdot2)\cdot17=1\cdot 2[/tex]

[tex]x=10[/tex] [tex]y=-24[/tex]

Trupmeną [tex]\frac{41}{17}[/tex] užrašom kaip grandininę:
[tex]\frac{41}{17}=2+\frac{7}{17}=2+\frac{1}{2+\frac{3}{7}}=2+\frac{1}{2+\frac{1}{2+\frac{1}{3}}[/tex].
Numeskim paskutinę jos grandį ir apskaičiuokim gautą trupmeną:
[tex]2+\frac{1}{2+\frac{1}{2}}=\frac{12}{5}\\\frac{41}{17}-\frac{12}{5}=\frac{1}{17\cdot5}\Rightarrow 41\cdot5+17\cdot(-12)=1\Rightarrow 41\cdot10+17\cdot(-24)=2[/tex].
Radom vieną sprendinį [tex](x_0;y_0)=(10;-24)[/tex].
Bendrasis sprendinys [tex]x=x_0-bt=10-17t\\y=y_0+at=-24+41t (t\in\mathbb{Z})[/tex].
Ats:[tex]x=10-17t\\y=-24+41t (t\in\mathbb{Z})[/tex]

P.S.: žinoma, iškleisti grandinine trupmena praktiškai yra tas pats, kas ir pritaikyti Euklido algoritmą.

Mirtise, tokios lygtys turi ne vieną sprendinį.

Kitas paprastas būdas spręsti diofantinėms lygtims:
[tex]y=\frac{2-41x}{17}=-2x+\frac{2-7x}{17}[/tex].
Aišku, kad [tex]\frac{2-7x}{17}\in\mathbb{Z}[/tex].
[tex]\frac{2-7x}{17}=t_1(t_1\in\mathbb{Z})\Rightarrow x=\frac{2-17t_1}{7}=-2t_1+\frac{2-3t_1}{7}\\\frac{2-3t_1}{7}=t_2(t_2\in\mathbb{Z})\Rightarrow t_1=\frac{2-7t_2}{3}=-2t_2+\frac{2-t_2}{3}[/tex]
[tex]\frac{2-t_2}{3}=t(t\in\mathbb{Z})\Rightarrow t_2=2-3t[/tex].
Tada [tex]t_1=\frac{2-7(2-3t)}{3}=7t-4\\x=\frac{2-17(7t-4)}{7}=10-17t\\y=-24+41t[/tex]

lukasm
Bendrasis sprendinys [tex]x=x_0-bt=10-17t\\y=y_0+at=-24+41t (t\in\mathbb{Z})[/tex].

Žinoma, olimpiadoje reikia spręsti su visais įrodymais. Tiesiog tame sprendime parodžiau sprendinio radimo būdą ir tiek. Juk spręsdami, pavyzdžiui, kvadratinę lygtį beveik niekd sprendime neišvedinėjam diskriminanto formulės. :D
Jei sprendžiant olimpiadoje, tai dar pirmiausia reikėjo parodyt, kad 41 ir 17 tarpusavy pirminiai. O jei kam įdomu, tai galiu parodyt dar vieną būdą, kaip įrodyt, kad [tex]x=x_0-bt[/tex] ir [tex]y=y_0+at[/tex].
Bendru atveju turim tokią lygtį:
[tex]ax+by=c[/tex],  ([tex]a,b,c\in\mathbb{Z}[/tex] ir [tex]DBD(a;b)=1[/tex]).
Jei sveikųjų skaičių pora [tex](x_0;y_0)[/tex] yra lygties sprendinys, tai [tex]ax_0+by_0=c[/tex].
[tex]ax+by-ax_0-by_0=-a(x_0-x)+b(y-y_0)=0\Rightarrow y-y_0=\frac{a(x_0-x)}{b}.[/tex]
Kadangi [tex]DBD(a;b)=1[/tex], tai [tex]x_0-x=bt\(t\in\mathbb{Z})[/tex].
Tada [tex]x=x_0-bt[/tex] ir [tex]y=y_0+at[/tex].

Na šiuo atveju tu nesi labai teisus dėl kvadratinės lygties. Matematikoje yra priimta neįrodinėti visiems žinomus dalykus arba jei faktas nežinomas, tai kažką pacituoti, kas tai padarė. Viskas gerai, žinių matosi, kad tau netrūksta, bet jei nori respublikinėje prizininku tapti, reikia pridėti truputį.