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

В современных условиях при подготовки обучающихся к ЕГЭ по математике особое значение приобретает развитие не только базовых вычислительных навыков, но и математического мышления, включающего в себя способность к анализу, формализации задач и применению множества методов. Практика показывает, что задачи профильного уровня ЕГЭ по математике зачастую требуют от учащихся не только уверенного владения материалом школьной программы, но и применения методов углубленного уровня. Это обуславливает необходимость введения факультативных занятий , которые служат дополнением к обязательной учебной программе и направлены на углублённое изучение теоретического материала и формирование устойчивых навыков решения задач повышенного уровня сложности.

Одним из таких разделов, имеющих важное прикладное значение и регулярно фигурирующих в олимпиадной и экзаменационной практике, являются линейные диофантовы уравнения [1]. Эти уравнения имеют широкую сферу применения, начиная от теории чисел и криптографии и заканчивая практическими задачами на делимость, остатки и линейные зависимости.

С развитием и повсеместным распространением цифровых технологий образовательный процесс не остается в стороне. Цифровые технологии в образовании в настоящее время не просто являются дополнением, но и становятся необходимостью, так как они повышают вовлеченность и интерес учащихся к процессу обучения. Одним из мощных инструментов для повышения конверсии и улучшения взаимодействия с обучающимися являются мобильные приложения. Их использование в учебном процесс, в том числе и на факультативных занятиях по подготовке к ЕГЭ, позволяет оперативно проверять корректность решений, анализировать допущенные ошибки и совершенствовать применяемые методы. Такой подход способствует формированию устойчивых навыков в решении различных задач, повышает мотивацию к изучению предмета и обеспечивает более глубокое усвоение сложных тем. Процесс обучения становиться более наглядным и динамичным, повышается его эффективность, поэтому интерес со стороны специалистов-программистов в этой области только растет.

В настоящей работе остановимся на линейных диофантовых уравнениях с двумя неизвестными и на их алгоритмах решения в объеме более одного факультативного заня- тия по этой теме. Рассмотрим несколько методов (переборный, непрерывного спуска, с помощью сравнений или алгоритма Евклида) их решения, в которых требуется не просто нахождение решения, но и его обоснование. Предварительно обучающиеся должны познакомиться с сравнением по модулю целых чисел и алгоритмом Евклида [2]. Описанные методы решения будут подробно разобраны на решении практических задач.

В качестве вспомогательного инструмента учащимся предлагается проверить и закрепить приобретенные навыки на Калькуляторе диофантовых уравнений (далее Калькулятор). Речь идет о специально разработанном для этих целей мобильном приложении на основе метода Евклида. Приложение имеет понятный интерфейс и предоставляет возможность визуализации всего процесса работы алгоритма. Калькулятор не только дает окончательное решение, но и возможность просмотра его пошагово. Применение Калькулятора на занятиях позволит не только быстро проверить свое решение, но и своевременно обнаруживать арифметические и алгоритмические ошибки, делая процесс обучения более эффективным.

Теоретический материал занятий

Сначала на занятиях обучающимся предлагается изучить основные определения, утверждения и методы решения линейных диофантовых уравнений с двумя неизвестными (с краткими пояснениями). При этом акцент будет сделан на алгоритмы их решения, которые будут подробно изложены. Ниже подробно изложена теоретическая часть занятий.

Определение. Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида ах + by = с, где a,b,c Е Z и (a,b,c) = 1.

Определение. Решение линейного диофан-тового уравнения - упорядоченная пара целых чисел (х, у), которая удовлетворяет данному уравнению.

Теорема. Диофантово уравнение ах + by = с разрешимо в целых числах тогда и только тогда, когда (a, b) = 1.

Доказательство теоремы можно посмотреть в [3].

Остановимся на некоторых методах решения линейных диофантовых уравнений [3, 4]:

• -    метод перебора всех возможных значений;

• -    метод решения с помощью сравнений;

• -    метод непрерывного спуска;

• -    метод решения с помощью алгоритма Евклида.

Метод перебора всех возможных значений.

Применим для уравнений с ограниченным множеством возможных решений.

Алгоритм:

• 1.    Проверить уравнение на разрешимость.

• 2.    Перебрать всевозможные целые значения х, у, исходя из ограничений.

Метод решения с помощью сравнений.

Метод основан на сравнении по модулю целых чисел и их свойствах [3].

Алгоритм:

• 1.    Проверить уравнение на разрешимость.

• 2.    Выразить переменную х через у:

• 3.    Найти у₀ Е [0, а — 1]:с = by₀ (mod а) и записать у = ак + у₀, к Е Z.

• 4.    Выразить переменную х через k и найти (х,y), перебирая к.

х = ^С а ^У и выделить условие делимости:

с — by =0 (mod а) или с = by (mod а).

Метод непрерывного спуска.

Этот метод основан на последовательном выделении целой части у переменных х, y и преобразовании их дробных частей.

• 1.    Проверить уравнение на разрешимость.

• 2.    Если |а| > |b|, то выразить переменную х через y: х = —^~- (Случай |а| > |b| аналогичен).

• 3.    Выделим целую часть ^С~^, найдя целые и дробные части дробей ~’ - ^' Дробную часть обозначим m, m Е Z.

• 4.    Выразим переменную y через m и выделим целую часть. Если дробная часть равна нулю, то процесс прекращаем, иначе выполняем действия как в шаге 3, вводя другую переменную в обозначение дробной части.

• 5.    Находим решение исходного уравнения, выражая х, y путём обратной подстановки по цепочке равенств.

Метод решения с помощью алгоритма Евклида.

Реализуем сначала прямой и обратный ход алгоритма Евклида для нахождения НОД(а, b). Решение (х,у) ищем в виде:

х = b • к + х₀,у = —a • к + у₀, к € Z, где (х₀,у₀) —  частное решение ax + by = с

(см. [3]).

Алгоритм:

• 1.    Проверить уравнение на разрешимость.

• 2.    Записать прямой и обратный ход алгоритма Евклида для нахождения НОД(а, b).

• 3.    Выразить 1 через аи b: 1 = а • s + b • г.

• 4.    Найти х₀ и y₀, умножив равенство 1 = а • s + b т на с: х₀ = s • с, у₀ = г • с.

• 5.    Найти все решения уравнения: х = b • к + х₀, у = —а • к + у₀, к € Z.

Практическая часть занятий

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

Задача. На столе лежат 4 камня по 5 кг и 13 камней по 14 кг. Их разделили на две кучки.

• а)    Может ли разность масс двух этих кучек камней быть равна 6 кг?

• б)    Могут ли массы этих кучек быть равными?

• в)    Какая наименьшая положительная разность масс может быть у двух этих кучек камней?

Решение. Пусть в первой кучке было х камней по 5 кг и у камней по 14 кг. Тогда во второй кучке 4 — х камней по 5 кг и 13 — у камней по 14 кг. Общая масса всех камней: 20 + 182 = 202 кг. Масса первой кучки: 5х + 14у. Масса второй кучки: 202 — 5х — 14у.

• а)    Запишем уравнение

  |(5х + 14у) — (202 — 5х — 14у)| = 6, 110х + 28у — 2021 = 6.

Составленное уравнение равносильно двум уравнениям 10х + 28у — 202 = ±6. Остановимся на решении уравнения 10х + 28у = 196, т.к. второе уравнение решается аналогично. Сначала разделим его    н а

НОД(10,28) = 2:

5х + 14у = 98.

Полученное уравнение является диофантовым и разрешимым, так как (а, b) = (5,14) = 1. Решим его всеми предложенными способами.

Метод перебора всех возможных значений:

Перебираем все допустимые значения (х,у), учитывая 0 < х < 4,0 < у < 13. Нахо дим пару значений (0,7), которая удовлетворяет равенству 5х + 14у = 98. Значит разность масс двух кучек камней может равняться 6.

Метод решения с помощью сравнений:

Выразим переменную х через у:

х = ^{98 14у} . Так как х € Z,w 5                                  ,

98 — 14у = 0 (mod 5) или 98 = 14у (mod 5).

Из    равенства     98 = 14 • 2 (mod 5)

получаем у₀ = 2 и у = 5к + 2, к € Z. Тогда х = 14 — 14к, к € Z. Учитывая что 0 < х < 4, находим -<к<1, т.е. к = 1. Таким образом, при к = 1 решение уравнения (0,7), следовательно, ответ положительный.

Метод выделения целой части.

Найдем выражение переменной х через у: х = 29^,т.к.5<14. Выделим целую часть х = 19 — 2у + - — 4у.

5 S' 3~4у Обозначим m = —-— и выразим у = —-—’ m € Z. Выделим целую часть у = 0 — m + - — 1m.

Обозначим к = —^, к € Z и выразим m = 3 — 4к, к € Z. Далее находим решение исходного уравнения:   у = 5к — 3, х = 28 —

14к, к € Z. Так как 0 < х < 4, то (0, 7) решение исходного уравнения (к = 2). Вывод со- храняется.

Метод решения с помощью алгоритма Евклида.

Запишем прямой ход алгоритма Евклида для нахождения НОД(5,14):

15 = 2-5 + 4, 5 = 1-4+1

и обратный

1 = 3 • 5 — 14.                      (*)

Умножим (*) на 98: 98 = 294 • 5 — 98 • 14 и         найдем          у₀ = —98, х₀ =

294 ((294, —98) —частное решение). Тогда х = 294 + 14к,у = —98 — 5к,к€ Z.

Учитывая ограничения, (0,7) – решение ис- ходного уравнения.

• б)    Каждая кучка будет весить 202 = 101, а

• следовательно, надо решить уравнение

5х + 14у = 101. Решим его, например, 2ым методом. Выразим переменную х через у: х = ^{101 14у} . Так как х € Z,то

• 5 ,

101 — 14у = 0 (mod 5) или

101 e 14у (mod 5).

Из равенства    101 н 14 • 4 (mod 5)

имеем у₀ = 4 и у = 5k + 4, к € Z. Тогда x = 9 — 18k, к € Z. Учитывая, что 0 < х < 4, находим ^ < к < ^. Таким образом, решений нет и массы двух кучек не могут быть равными.

• в)    Запишем выражение разности масс |10x + 28у — 202| = 2|5x + 14у — 101|.

Нужно найти минимальное положительное четное значение для этого выражения, т.е. надо доказать разрешимость уравнений 5х + 14у — 101 = ±1. Полученные уравнения являются диофантовыми и разрешимыми, т.к. (а, Ь) = (5,14) = 1.

Задачи для самостоятельного решения.

Решить диофантовы уравнения разными способами, проверяя на разрешимость:

• 1.  35х + 21у = 14. Ответ: (—2 + 3к;4 —

• 2.    4х + 11у = 17. Ответ:         (51 +

• 3.  18х — 24у = 6. Ответ:    (—4к; —1 —

• 4.  45х — 28у = 7. Ответ:         (14 —

5к), к € Z.

11к; —17 — 4к), к € Z.

3к), к € Z.

28к;35 — 45к), к € Z.

Проверка решений с использованием

разработанного мобильного приложения

Для проверки правильности решения линейных диофантовых уравнений с двумя переменными в качестве вспомогательного ресурса на факультативных занятиях или для индивидуальной подготовки учеников разработано мобильное приложение, выполняющее функции обучающего калькулятора и сопровождающего тренажёра. Калькулятор диофантовых уравнений прост в использовании и дает возможность быстро проверить ход решения, ответ и найти арифметические ошибки. Приложение предназначено для наглядного решения уравнений методом Евклида (авторский выбор) и содержит теоретическую справку. Калькулятор реализован с использованием языка Dart [4] и фреймворка Flutter [6] и может быть установлен на любое современное мобильное устройство.

Алгоритм работы с приложением:

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

ФУНКЦИЯ _getEuclideanSteps(a, b): {Инициализация строки с шагами} steps ← "Прямой ход (нахождение НОД):" {Список для хранения данных деления} divisions ← пустой список r1 ← a r2 ← b

ПОКА r2 ≠ 0:

{Целая часть от деления} q ← r1 DIV r2

{Остаток от деления} r ← r1 MOD r2

ДОБАВИТЬ (r1, q, r2, r) В divisions steps += "{r1} = {q} * {r2} + {r}" r1 ← r2 r2 ← r

{Записываем найденный НОД} steps += "НОД(a, b) = r1"

steps += "Обратный ход (нахождение коэффициентов):"

x1 ← 1, y1 ← 0

x2 ← 0, y2 ← 1

ДЛЯ каждого элемента (r1, q, r2, r) В divisions:

x ← x1 - q * x2

y ← y1 - q * y2

x1 ← x2

y1 ← y2

x2 ← x y2 ← y

{Записываем линейную комбинацию НОД} steps += "1 = {a} * {x1} + {b} * {y1}" ВОЗВРАТ steps

Заключение

Изложенный в статье материал может служить подспорьем учителям для ведения факультативных занятий по решению линейных диофантовых уравнений с двумя переменными. Не все из предложенных методов их решения в работе были реализованы в мобильном приложении, это авторский выбор. Планируется в дальнейшем преобразовать программный продукт в полноценный цифровой учебный ресурс, расширяя его функционал другими методами решений диофантовых уравнений, рассмотренных в этой работе и не только.