Пересечение множеств

[maxmatem]

iifat
Хорошо, попробую.

[maxmatem]

У меня вопрос, а какой способ для школьников наиболее доступный для нахождения частного решения в линейных диафантовых уравнениях с двумя переменными?

Ну кроме угадывания?

Просто думаю через разложения НОД через соотношения Безу трудновато будет...

[gris]

Вот, если позволите, простенькая задача из профильного ЕГЭ: сколько чисел, каждое из которых равно $14$ или$13$, выписано на доске, если их сумма равна $239$? (Условие приведено к нормальному виду). Почему-то школьники начинают решать именно диафантово уравнение. И притягивать соображения делимости и проч.

[iifat]

maxmatem в сообщении #1143651 писал(а):

какой способ для школьников наиболее доступный для нахождения частного решения в линейных диафантовых уравнениях с двумя переменными?

Если вы про аналогичные вашему — расширенный алгоритм Евклида.

[maxmatem]

iifat
Спасибо, но расширенный алгоритм Евклида как раз (если чего не путаю) и позволяет найти те самые коэффициенты Безу.

Вот скажем тоже уравнение $3x-5y=3$

Частное решение $(1;0)$ видно, а если мы не хотим его принципиально видеть, а хотим аналитикой?

в данном случаи $ax+by=c$ и $(a;b)=1$

По расширенному алгоритму я должен $a$ на $b $ делить с остатком, но тут же $a<b$

[iifat]

maxmatem в сообщении #1143662 писал(а):

По расширенному алгоритму я должен $a$ на $b $ делить с остатком, но тут же $a<b$

И, стесняюсь спросить, чо?

-- 12.08.2016, 23:54 --

Если у вас вызывает трудности необходимость поделить 3 на 5 с остатком — перечтите учебники. Очень советую.

[maxmatem]

да с этим проблем то нет

$3=0\cdot 5+3$

тогда я не понимаю как расширенный тут применять.

Я поясню в чем проблема.

Вот имеем мы уравнение $ax+by=c$, где $(a;b)=1$

Я хочу найти решение через соотношения безу.

смотрю как это написанно в https://ru.wikipedia.org/wiki/%D0%94%D0 ... 0%B8%D0%B5

Но пока не понятно, как частное решение находить

[iifat]

maxmatem в сообщении #1143678 писал(а):

Я поясню в чем проблема

Проблема, судя по вашим словам, в том, что на полэкране текста описаны два способа нахождения решения вашего уравнения. Так что же вам непонятно-то, таинственный вы наш?

[maxmatem]

Мне не понятно, как находить соотношение безу ,когда $a<b$

[iifat]

Аналогично

[maxmatem]

iifat
Имеем по расширенному алгоритму.

$a=3$ $b=5$

1) $3=0\cdot 5+3$
2)$5=1\cdot 3+2$
3)$3=1\cdot 2 +1$
4)$2=1\cdot 1+0$

Тогда из (3) следует $1=3-1\cdot 2$ (3.1)
ИЗ (2) следует $2=5-1 \cdot 3$ (2.1)
из (1) следует $3=3-0 \cdot 5$(1.1)


Подставляя (2.1) и (1.1) в (3.1) имеем

$1=2\cdot3+(-1)\cdot 5$

Теперь получается что частное решение $(x_0;y_0)=(6;-3)$

НО это не частное решение.....чего я не так сделал?

[iifat]

maxmatem в сообщении #1143696 писал(а):

Тогда из (3)

Вообще-то, расширенный алгоритм Евклида не состоит из прямого и обратного проходов, как у вас. Ну да ладно.

maxmatem в сообщении #1143696 писал(а):

Теперь получается что частное решение $(x_0;y_0)=(c_1\cdot 2;c_1 \cdot(-1))$

$c_1$ у вас чему равно? Вы, по-моему, в знаках путаетесь. $ax+by$ или $ax-by$?

-- 13.08.2016, 02:05 --

Вот всё ж таки правка — это зло (кроме опечаток). Итак, если я правильно вас понял, $3\times6+5\times(-3)\ne3$?

[maxmatem]

Я подставлял решение в уравнение $3x-5y=3$
Ведь я его частное решение искал, и тогда не выходит....

чего я не так делаю
?

-- Пт авг 12, 2016 20:22:05 --

Но коэффициенты Безу как я понял я нашел верно или нет?

Цитата:

Вы, по-моему, в знаках путаетесь. $ax+by$ или $ax-by$?

А это что такое?

[ewert]

maxmatem в сообщении #1143651 писал(а):

а какой способ для школьников наиболее доступный для нахождения частного решения в линейных диафантовых уравнениях с двумя переменными?

Самый простой для запоминания -- это цепные дроби. В этом случае надо запоминать лишь само понятия цепной дроби, но оно и само по себе полезно. Ну и ещё помнить тот факт, что оно здесь помогает.

Пример: $178x+41y=1$.

Раскладываем: $\frac{178}{41}=4+\frac{14}{41}=4+\frac1{2+\frac{13}{14}}=4+\frac1{2+\frac1{1+\frac1{13}}}$.

Отбрасываем последнее и сворачиваем обратно: $4+\frac1{2+\frac1{1}}=4+\frac13=\frac{13}3$.

Т.е. то ли $x=\pm13,\ y=\pm3$, то ли наоборот. Формально говоря, следовало бы вызубрить, какой из восьми вариантов верен, практически же -- не надо: беглая прикидка в уме мгновенно даёт, что правильным может быть только $x=3,\ y=-13$.

Конечно, это и есть алгоритм Евклида. Но в такой форме он не требует запоминания никаких технических деталей.

[iifat]

maxmatem в сообщении #1143699 писал(а):

А это что такое?

Первое — уравнение, которое решает расширенный алгоритм Евклида. Второе — уравнение, в которое вы, похоже, упорно пытаетесь подставить результат.

ewert в сообщении #1143772 писал(а):

Самый простой для запоминания -- это цепные дроби

Не то чтоб я спорил. Но цепные дроби ­— вполне нехилый шмат теории. Очень интересный и полезный, да. Вы его знаете и вам никаких технических деталей не надо; советовать другим — ну, оставляю на вашей совести

ewert в сообщении #1143772 писал(а):

Т.е. то ли $x=\pm13,\ y=\pm3$, то ли наоборот

Странный совет. Как раз основное в теории цепных дробей $\frac{178}{41}-\frac{13}3=\frac1{123}$ из подсчёта чётности безо всяких прикидок.