Четность и нечетность

Соображения четности (нечетности) часто используются при решении математических задач (и элементарных, и весьма «продвинутых»). В данной статье рассматриваются подходы к решению подобных задач.

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

Четные и нечетные числа. Начальные сведения

Сумма, произведение, частное четных (нечетных) чисел

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

А почему, собственно, мы рассматриваем только два числа. Давайте мыслить шире!

Так, сумма 2+4+6+. +1022+1024 четна, поскольку все слагаемые четны. Сумма 1+3+5+7+9 нечетна, т. к. содержит 5 нечетных слагаемых. Произведение 2*3*4*. *1001*1002 четно уже хотя бы по той причине, что первый сомножитель является четным.

И вновь о сумме и произведении

Решение. Обозначим исходные числа A и B. Очевидно, возможно 4 варианта:

Во всех случаях (кроме первого) получаем нечетный результат!

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

Сознаю, что первая часть статьи может показаться читателю довольно утомительной и однообразной. К сожалению, обойтись без этих «скучных» базовых понятий нельзя. Обещаю, что дальше будет гораздо интереснее.

Источник

Закономерности в распределении простых чисел

Введение

Простое число — это натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Такие числа представляют огромный интерес. Дело в том, что никто так и не смог полностью понять и описать закономерность по которой простые числа располагаются в ряду натуральных чисел.

Ещё до нашей эры Евклид сформулировал и доказал первые теоремы о простых числах. С тех пор математики, среди них Гаусс, Ферма, Риман, Эйлер, продолжали исследования и надо отдать им должное заметно продвинулись. Было обнаружено много интересных свойств простых чисел, выдвинуто много предположений, некоторые из которых были доказаны. Однако много гипотез связанных с простыми числами до сих пор остаются необоснованными.

Распределение простых чисел

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

Получить рекуррентную формулу для очередного простого числа

Существует родственная ей задача о количестве простых чисел, не превосходящих заданной величины:

Найти функцию p(x), значение которой в точке x равно числу простых чисел на отрезке [1, x]. Где x – любое действительное число не меньшее единицы.

Функция называется функцией распределения простых чисел.

К решению вышеуказанных задач существует множество подходов. Рассмотрим некоторые из них.

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

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

Первое простое число p₁ =2. Значит все последующие простые числа должны не делится на 2, то есть иметь вид 2k+1, где k – натуральное. То есть все простые числа начиная со второго — нечётные.

Второе простое число p₂ = 3. Значит все последующие простые числа должны иметь вид 3m+1, либо 3m+2, где m – целое. Это равносильно утверждению о том, что все простые числа начиная с третьего не делятся на три. Однако при этом числа ещё должны не делится на два, то есть иметь вид 2k+1.

Решая диофантовы уравнения

найдём k и m и получим, что все простые числа начиная с p₃ обязательно представимы в виде , либо в виде , где t – целое.

И правда, какое бы простое число мы ни взяли оно представимо таким образом:

Однако обратное неверно, то есть любое натуральное число вида 6t+1 или 6t+5 не обязательно простое. Например, .

Третье простое число p₃ = 5. И если по аналогии учесть, что любое простое число, начиная с четвёртого не делится на 5, также не делится на p₁ = 2 и на p₂ = 3, то получим, что все простые числа начиная с p₄ обязательно имеют одно из представлений

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

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

Итак, как же найти функцию F(x)? Сначала рассмотрим множество всех натуральных чисел. Какова доля чисел, которые не делятся ни на одно из простых p₁, p₂, …, p_n?

Каждое второе число делится на p₁ = 2. Значит, часть всех чисел делится на p₁.

Каждое третье число делится на 3. Значит, всех чисел делится на p₂. При этом надо учесть, что каждое шестое число делится и на 2 и на 3 одновременно.

Значит, доля чисел не делящихся ни на 2, ни на 3 равна

Если преобразовать выражение, то оно примет вид:

Опять же можно представить выражение в виде

Будем обозначать такое произведение P(n). Кстати, если учесть все простые числа (n→∞), то мы получим обратную величину от так называемого произведения Эйлера.

Почему так происходит? Когда мы получали формулу (1), мы пользовались рассуждениями, что среди всех натуральных чисел доля, делящихся на p_n, равна . Но нельзя сделать такое утверждение о конечном наборе последовательных натуральных чисел. Например, возьмём набор 1,2, 3,4,5,6,7,8,9. Здесь 4 числа из 9 делятся на два. И несложно заметить, что отличается от . То есть, при применении к конечному набору чисел, данный метод даёт результат с некоторой погрешностью.

Это будет мешать далее получать точные формулы. Но если оценить эту погрешность, то можно (например, приняв и используя приведённые выше рассуждения) получить оценку для p_n+1-го простого числа. Однако, получение таких оценок — это тема отдельной работы. И поэтому здесь я не буду на этом останавливаться, а приведу лишь некоторые результаты, полученные математиками.

Одна из оценок для простого числа с номером n:

оценка верна для всех n, начиная с 6.

А вот формула для функции распределения простых чисел:

Для функции Риман получил приближение, используя интегральный логарифм и нетривиальные нули дзета-функции Римана. Однако, это приближение верно, только если верна гипотеза Римана. Причём если гипотеза Римана верна, то оно является наилучшим.

Гипотеза Римана до сих пор не доказана и не опровергнута. Она, как мы могли видеть, тесно связана с простыми числами и, вообще, имеет огромное значение для теории чисел. Из-за своей важной роли в математике, гипотеза Римана была объявлена одной из семи задач тысячелетия.

Проблемы Ландау

Насчёт простых чисел выдвинуто очень много интересных гипотез. Среди них видное место занимают гипотезы Ландау (проблемы Ландау). Формулируются они так:

1. Гипотеза Гольдбаха

Можно ли любое целое чётное число, большее 2, записать в виде суммы двух простых?

2. Гипотеза о числах-близнецах

Бесконечно ли число простых p таких, что p + 2 тоже простое?

3. Гипотеза Лежандра

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

4. Гипотеза о почти квадратных простых числах

Существует ли бесконечно много простых чисел p вида .

Проблемы Ландау ни доказаны, ни опровергнуты по состоянию на 2020 год. Далее кратко расскажу про каждую из них.

1. Гипотеза Гольдбаха

Существуют две гипотезы Гольдбаха: слабая (тернарная) и сильная (бинарная).

Слабая гипотеза Гольдбаха: Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

Эту гипотезу доказал Харольд Гельфготт в 2013 году используя так называемые большие дуги. Финальная часть доказательства заняла 133 страницы.

Сильная гипотеза Гольдбаха: Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Надо заметить, что в обоих случаях гипотезы Гольдбаха простые числа не обязательно должны быть различными.

Заметьте, что в сильной гипотезе речь идёт только о чётных числах. Давайте покажем, что нечётное число не обязано быть представимо в виде суммы двух простых чисел. Просто приведём пример. Число 11 не представимо в виде суммы двух простых. Вроде бы несложно.

Но переформулируем проблему так: существует ли такое число, что любое нечётное, большее этого числа, представимо в виде суммы двух простых чисел? Давайте проверим. Пусть существует некоторое нечётное натуральное число N, такое, что любое нечётное число представимо в виде суммы двух простых чисел.

Возьмём произвольное нечётное . По предположению существуют такие простые p₁ и p₂, что . Если сумма двух натуральных чисел нечётна, то это значит, что одно из слагаемых чётно, а другое нет. Пусть для определённости p₁ – чётное. Единственное чётное простое число — это 2. Значит, . То есть, K-2 (предыдущее перед K нечётное число) является простым. Поскольку всё вышесказанное верно для любого нечётного большего N, то получается, что все нечётные числа, начиная с N-2, являются простыми. Это неверно. Если бы это было так, то при n→ ∞. Однако, как говорилось выше при n→ ∞.

Итак, не существует такого числа, начиная с которого все нечётные числа могут быть представлены в виде суммы двух простых.

А что же насчёт чётных? Гипотеза не была опровергнута, не было найдено ни одного контрпримера. Но это не значит, что их не существует. Доказать же гипотезу полностью пока никому не удалось.

2. Гипотеза о числах-близнецах

Бесконечно ли число простых чисел близнецов?

Для начала сформулируем определение. Два простых числа называются близнецами если отличаются друг от друга на 2.

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

3. Гипотеза Лежандра

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

Аналогичная гипотеза доказана для кубов, начиная с некоторого n. То есть, существует, по меньшей мере, одно простое число, лежащее между и для достаточно большого n. Для квадратов же, гипотеза Лежандра пока не доказана.

4. Почти квадратные простые числа

Заключение

Как мы видим, в этой области теории чисел существует очень много пробелов, а также недоказанных гипотез. Отдельно хочется сказать про численную проверку утверждений. Например, ни для одной из гипотез Ландау не был найден контрпример, даже с использованием значительных вычислительных мощностей в течение большого времени. Однако, в истории математики 20-го и 21-го века были случаи, когда контрпример, опровергающий гипотезу, был настолько огромным числом, что его не удавалось найти с помощью вычислительных машин.

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

Источник

Фрагмент занятия по математике по теме «Четность в олимпиадных задачах»

Фрагмент занятия «Четность в олимпиадных задачах»

При решении задач на использование идеи четности необходимо опираться на следующие свойства:

сумма двух нечетных слагаемых – четная;

сумма двух четных слагаемых – четная;

сумма нечетного числа нечетных слагаемых – нечетная;

сумма четного числа нечетных слагаемых – четная;

сумма четных слагаемых – всегда четная;

произведение нечетного числа нечетных множителей – нечетное;

произведение четного числа нечетных множителей – четное;

произведение четных множителей – всегда четное.

Рассмотрим примеры решения задач по данной теме.

Страницы книги пронумерованы подряд от первой до последней. Хулиганы Петя и Миша вырвали из разных мест книги 27 листов и сложили номера вырванных страниц. У них получилось 1998. Когда об этом узнал Витя, он заявил, что мальчики ошиблись. Объясните, прав ли Витя.

Любой вырванный лист содержит две страницы. Номер одной из них – четное число, а номер другой – нечетное. Поэтому, если рассмотреть сумму номеров всех вырванных листов, то она содержит – 27 четных слагаемых и 27 нечетных слагаемых. Т.к. сумма двадцати семи четных слагаемых – число четное, а сумма двадцати семи нечетных слагаемых – число нечетное, то вся сумма будет нечетной. Следовательно, она не может равняться четному числу 1998. Значит, Витя оказался прав.

Можно ли представить число 2013! в виде суммы 2013 нечетных натуральных чисел?

Т.к. 2013! = 2013 ∙ 2012 ∙ 2011 ∙ … ∙ 3 ∙ 2 ∙ 1 – число четное, а сумма 2013 нечетных натуральных чисел – число нечетное, следовательно, число 2013! нельзя представить в виде суммы 2013 нечетных натуральных чисел.

Ответ: представить нельзя.

Сумма пяти чисел равна 350. Может ли их произведение не может оканчиваться на 2013?

Если произведение нечетное, т.к. оканчивается на 2013, то все пять множителей – нечетные, следовательно, их сумма также должна быть нечетной.

Т.к. по условию задачи сумма пяти чисел равна четному числу, то она обязательно содержит хотя бы одно четное слагаемое. Значит, произведение обязательно будет четным, следовательно, оно не может оканчиваться на 2013.

Ответ: произведение не может оканчиваться на 2013.

Два натуральных числа в сумме дают 2013. Коля увеличил каждое из них на 50 и перемножил полученные числа. Он получил, что произведение также оканчивается на 2013. Докажите, что Коля ошибся.

Так как сумма двух натуральных чисел равна 2013, то одно из них обязательно будет четным, а второе – нечетным. Если к четному числу прибавить 50, то получится четное число, а если к нечетному числу прибавить 50, то получится нечетное число. А так как произведение четного и нечетного числа является четным числом, то оно не может оканчиваться на 2013, следовательно, Коля ошибся.

Произведение трех натуральных чисел оканчивается на 2002. Докажите, что их сумма не может равняться 9999.

Сумма трех натуральных чисел равна нечетному числу 9999 только в двух случаях: если все три числа – нечетные, или среди них – два числа четные и одно число нечетное.

Если все три числа – нечетные, то их произведение оканчивается на нечетную цифру и, следовательно, не может оканчиваться на 2002.

Если два числа – четные и одно нечетное, то их произведение будет четным числом и должно обязательно делиться на 4. Так как число, оканчивающееся на 2002, на 4 не делится, то и сумма данных трех натуральных чисел не может равняться 9999.

Ответ: если произведение трех натуральных чисел оканчивается на 2002, то их сумма не может равняться 9999.

Вдоль дороги растут 2002 ели. Утром на каждой из них сидело по одной вороне. В полдень каждая ворона взлетела и перелетела на дерево, растущее через одно от того, с которого она взлетела. Могло ли так получиться, чтобы на каждой ели вновь сидело по одной вороне?

Пронумеруем ели по порядку от 1 до 2002. Согласно условию задачи, вороны перелетают с ели на ель через одну, т.е. вороны, сидевшие на елях с нечетными номерами, перелетают на ели с нечетными номерами, а вороны, сидевшие на елях с четными номерами, перелетят на ели с четными номерами. (1001 ель получит четный номер и 1001 ель получит нечетный номер.)

Рассмотрим ели с нечетными номерами. Покрасим их в два цвета – белый и черный.

При такой окраске ворона с «белой» ели перелетит на «черную» и наоборот. Но так как «черных» елей 500, а «белых» елей 501, то, по крайней мере, на одну из «белых» елей не сядет ни одной вороны.

Источник