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

Алгоритм Евклида

В этой статье я считаю, что читатель знаком с понятием НОД и НОК и выполнял в своей жизни их нахождение разложением чисел на простые множители. Тогда очевидно, что разложение на множители в случае больших целых чисел делает процедуру поиска НОД длинной и трудоёмкой. Алгоритм Евклида значительно улучшает картину. Рассмотрим два числа 2112 и 312. Проиллюстрируем алгоритм Евклида, найдя их НОД.

• Поделим 2112 на 312. Результат запишем в виде
• Делим теперь 312 на 249. Результат запишем в виде
• Делим 249 на 63. Результат запишем в виде
• Делим 63 на 60. Результат запишем в виде
• Делим 60 на 20. Результат запишем в виде 

Тогда НОД(2112,312)=3

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

Диофантовы уравнения

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

 , где  -целые числа. Корни напомню, мы тоже будем искать целые.

Рассмотрим следующие случаи. НОД(a,b) не делится на c.  Очевидно, что тогда целого решения нет. Если же НОД(a,b)  делится на c. Тогда решений бесконечно много. Выберем одно из них, тогда остальные будут иметь вид

                                                                         (*)

где  d=НОД(a,b), -целый параметр

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

                                                                                              (**)

Если c=0, тогда все решения мы можем записать в  виде

Если . Умножим уравнение (**) на  тогда получим

В итоге все целые решения нашего уравнения будут иметь вид (*)

Иллюстрацию теории на конкретных примерах можно найти на форуме www.forum.ya-repetitor.ru

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

 Всем Удачи!!!

С уважением, Артём Александрович Рогов,

репетитор по математике и физике,

www.ya-repetitor.ru-  сообщество профессиональных репетиторов

P.S. все замечания и комментарии отправляйте,пожалуйста, по системе обратной связи сайта www.ya-repetitor.ru