Алгоритм Евклида
Ошибка.
Попробуйте повторить позже
Какое наибольшее значение может иметь наибольший общий делитель чисел 
и 
для натуральных
Подсказка 1
Для удобства в этой задаче можно полагать, что в НОДе числа могут быть отрицательными, а сам он всегда положителен. Первый шаг алгоритма Евклида дает ((n+1)²+20,n²+20) = (2n+1, n²+20). Можно ли теперь по алгоритму Евклида сделать так, чтобы получившееся выражение превратилось в выражение вида (a+b,ab)?
Подсказка 2
Конечно! Вычтем n(2n+1) из второго аргумента. Тогда получится (2n+1,-n²-n+20). Это равно (2n+1, (n+5)(n-4)). Тогда (n+5) + (n-4) = 2n+1. Предположим, что наш НОД больше 1. Что можно сказать о простых числах, которые его делят?
Подсказка 3
Верно! Можно утверждать, что простые числа, делящие выражение вида (ab, a+b) делят оба числа a и b. Тогда, поскольку (n+5,n-4)=(9,n-4), то все простые делители такого НОДа равны 3. Что можно сказать об n?
Подсказка 4
Верно! Тогда n = 3s + 1. Подставляем и получаем, что наш НОД равен 3(3(s+2)(s-1), 2s+1). Поскольку 2s + 1 = (s+2) + (s-1), то можно снова применить утверждение о простых делителях выражений (ab,a+b) и получить, что наш новый простой делитель либо равен 3, либо делит оба числа s+2 и s-1. Чему тогда равен этот простой делитель?
Подсказка 5
Верно! Тогда этот простой делитель равен 3. Получаем, что s = 3k + 1. После подстановки получается 9(9k(k+1),2k+1). Числа k и k+1 взаимно просты, тогда из утверждения о выражениях (a+b,ab) получается, что k(k+1) и 2k+1 взаимно просты. Какое наибольшее значение может принимать наш НОД?
В задаче будем искать наибольший положительный НОД, но будем считать, что числа в алгоритме Евклида могут быть отрицательными. Тогда по алгоритму Евклида
Заметим, что 
Докажем небольшую лемму.
_________________________________________________________________________________________________________________________________________________________________________________
Лемма. Пусть 
— простое число. Тогда 
и 
и 
Доказательство. Действительно, пусть 
и 
Мы знаем, что 
или 
С другой стороны, тогда 
возможно в том и только в том случае, если 
и 
Все переходы равносильны, и лемма доказана.
_________________________________________________________________________________________________________________________________________________________________________________
Таким образом, если числа 
и 
имеют общий делитель 
то все простые числа 
являются делителями
чисел 
и 
Поскольку 
то все такие простые числа являются делителями 
Тогда, если простое число
делит и 
и 
то оно равно 
Таким образом, 
Получаем после подстановки в выражение для
НОД
Заметим, что 
Тогда по лемме простое число, делящее 
либо равно 
либо делит оба
числа 
и 
По алгоритму Евклида 
Таким образом, любое простое число, делящее
равно 
Следовательно, 
Снова подставляем!
Снова заметим, что 
однако числа 
и 
взаимно просты, поэтому общих делителей у 
и 
нет.
Это значит, что 
тогда 
Положим 
тогда 
и 
Так как 
получаем 
и 
Таким образом, мы получили и пример, и оценку.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
