V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм
|
| УДК 511 В.А. Мешков, канд. техн. наук (ОИР Украины, г. Евпатория) V.A. Meschkoff КЛАССИФИКАЦИЯ ПРОСТЫХ ЧИСЕЛ С ПОМОЩЬЮ ЛИНЕЙНЫХ И КВАДРАТИЧНЫХ ФОРМ PRIME NUMBERS CLASSIFICATION WITH LINEAR AND QUADRATIC FORMS Показано, что квадратичные формы простых чисел исчерпываются соотношением  . На этой основе рассмотрены варианты классификации простых чисел. Найдено восемь непересекающихся подмножеств простых чисел, соответствующих классам эквивалентности по модулю 24. Рассмотрены приложения классификации к числам Мерсенна, Ферма и составным числамIt is demonstrated, that all prime numbers quadratic forms consist of . On these grounds it is examination for variants of prime numbers classification. It is discovered eight unintersecting subsets of prime numbers, in conformity with equivalence classes for modulus 24. There are applications of classification for Mersenne and Fermat numbers and composite numbers.^ Предлагаемая классификация основывается на давних исследованиях, начатых Жираром и Ферма, подробно анализируемых в 1,§1.7. Было найдено, что только простые числа вида  имеют единственное представление в виде суммы двух квадратов. Также оказалось, что только простые числа вида  или  имеют единственное представление в виде  , и только простые числа вида  имеют единственное представление в виде  Эти свойства являются исключительными, т.к.  есть сумма двух квадратов, а числа  подчиняются другим закономерностям. Поэтому представляется естественным классифицировать простые числа как представимые в виде  и все остальные, не имеющие такого представления.Эти остальные простые числа, как нетрудно проверить, имеют вид  . Поскольку функция Эйлера  , то асимптотически доля этих простых чисел в множестве всех простых чисел составляет  Несложно также установить, что простые числа  поэтому оказывается, что для простых чисел  достаточно простой подобной квадратичной формы не существует.Однако  и из элементарной теории чисел известно, что в этом случае существует квадратичный вычет  Из этого следует, что имеется представление в виде квадратичной формы  Например,  . Обнаруживается связь с диофантовыми уравнениями  (1)Такие уравнения имеют конечное число бесконечных последовательностей решений 1, стр.404, которые в случае простых  сводятся к двум последовательностям. Имеется наименьшее (начальное) решение последовательностей, а все последующие решения определяются этим начальным и последовательностью решений уравнения Пелля  Для однозначности примем, что простые числа  . Последовательность таких квадратичных форм бесконечна, однако однозначно определяется начальным решением. Теорема. Любое простое число  , где  являются начальными решениями диофантова уравнения  Доказательство. Число  , поэтому имеет квадратичный вычет  . Это соответствует диофантову уравнению  . Левая часть этого уравнения имеет вид  , и выполняется условие  , т.е. эти числа взаимно простые. Поскольку p простое, то p и  являются делителями левой части уравнения. Но из элементарной теории чисел известно (см.[1], гл.2 и упр. 2.4.4), что эти числа тогда должны иметь представление в виде  . Поэтому должны иметь решения соответствующие диофантовы уравнения. Последовательность решений первого из уравнений имеет начальное решение . Теорема доказана.Изложенное позволяет предложить простую и наглядную классификацию простых чисел, разбивающихся на четыре частично пересекающиеся множества круговых, эллиптических (два множества) и гиперболических простых чисел. Табл.1
Следует отметить, что в этой классификации не представлена в явном виде линейная форма  Происходит это потому, что простые числа этого вида распадаются на два непересекающихся множества в зависимости от значения вычета  При  приходим к множеству гиперболических простых чисел. При  простые числа принадлежат множеству 2 эллиптических простых чисел. А при  имеем последовательность составных чисел, кратных 3.Также необходимо различать пересекающиеся или частично пересекающиеся множества простых чисел, и вследствие этого имеющие несколько возможных квадратичных форм, и случаи, когда непересекающиеся множества имеют одинаковые квадратичные формы. Например, простые числа  и простые числа имеют представление в виде квадратичной формы  , однако относятся к непересекающимся множествам, т.к.  .С другой стороны круговое простое число 97 имеет все квадратичные формы представления, т.к.  , но пересекается только с множеством Эллиптические-2.Предлагаемые ранее перечисления множеств простых чисел, например [2,стр. 188], не являются классификацией, т.к. не основываются на общем признаке. Предлагаемая классификация имеет в своей основе такой признак, а именно: любое произведение простых чисел, имеющих одинаковую квадратичную форму из Табл.1, имеет представление в виде такой же квадратичной формы. Отсюда следует, что произведение простых чисел, принадлежащих к одному из множеств Табл.1, имеет представление в виде основной квадратичной формы этого множества. Таким образом, основой для классификации простых чисел является известная формула для частных случаев композиции квадратичных форм[1, стр.396]  (2) где  .Упомянутое выше перечисление в [2,стр. 188], таким свойством не обладает, т.к. содержит простые числа, имеющие квадратичные формы  .На этой основе возможно усовершенствовать и упростить классификацию, представленную в Табл.1, используя только непересекающиеся множества простых чисел. Табл.2
В классификации Табл.2 все же имеются множества, содержащие частично пересекающиеся подмножества. Их можно выделить, если за основу взять непересекающиеся подмножества, соответствующие непересекающимся классам эквивалентности по модулю 24. Будем обозначать квадратичные формы как  — круговая,  — эллиптические 1 и 2,  — гиперболическая.Табл.3 Классификация простых чисел  с помощью непересекающихся множеств
Полученную классификацию применим для анализа различных задач теории чисел. Рассмотрим вначале, к какому множеству относятся простые числа Мерсенна  . Нетрудно непосредственно проверить, что при нечетном  единственно возможная линейная форма относится к Эллиптическим2 и имеет вид  . Таким образом все простые числа  относятся к Эллиптическим2 и имеют кроме  еще квадратичную форму представления . Заметим, что при нечетном показателе любое число  имеет квадратичные формы  . Если такое число составное, то его делителями могут быть только простые и простые круговые  . Только они имеют квадратичные формы , как это следует из классификации Табл.3. Окончательный вывод: Составное число может иметь нечетное число простых делителей и любое число простых делителей . Простые числа  относятся к классу .Аналогично рассмотрим числа Ферма  которые, как нетрудно видеть, имеют квадратичные формы  . Несложный анализ с помощью классификации Табл.3 приводит к выводу: Простые числа относятся к классу  . Составное число  может иметь нечетное число простых делителей и любое число простых делителей .В общем случае для произвольных чисел классификация может быть произведена с помощью компьютеров с соответствующими программами. Автором использовалась программа Mathematica, работающая с задачами теории чисел. В качестве примера рассмотрим число  . Вначале определяем, простое число или составное, для этого имеются стандартные подпрограммы.Если число простое, то далее вычисляем  , и классифицируем его согласно Табл.3. Но для данного примера получаем, что число составное.Поскольку оно имеет квадратичную форму , то и все составляющие его простые имеют такую же форму. Но хотя  , простых в числе составляющих нет. Определить это можно, произведя факторизацию числа, т.е. найдя  . Для этого также имеются стандартные подпрограммы, результат обычно представляется в виде .Для классификации этот вектор легко преобразовать в вектор  и применить к нему функцию вычисления сравнений по модулю 24. В результате получим вектор, дающий классификацию простых, образующих произведение: .По отношению к рассматриваемому числу имеем  .Т.о. данное число есть произведение 12 простых круговых чисел, из них одно  , четыре , семь  .Для такого составного числа рассмотрим задачу определения подмножеств простых, имеющих одинаковые квадратичные формы, и нахождения всех таких квадратичных форм. Для произведения круговых простых чисел это эквивалентно нахождению всех решений уравнения  . Такая задача может быть решена с помощью подпрограммы OrderedSumOfSquaresRepresentations. Однако оказалось, что для решения задачи компьютер работает несколько часов, и при этом не хватает виртуальной памяти. Это было неожиданным и для разработчика подпрограммы Стэна Вейгона (Stan Wagon), одного из авторов руководства [3], к которому обратился автор.Недели через две Вейгон сообщил, что Д. Лихтблау (Daniel Lichtblau) на основе своих новых улучшений алгоритма «HalfGCD» [4] усовершенствовал подпрограмму, и теперь она решает задачу за 0,3 сек. Однако к этому времени автором была разработана подпрограмма, впоследствии по предложению Вейгона названная QRM (QuadraticRepresentationsMeshkoff). Она использует только соотношение (1) и стандартные функции Mathematica: 1) факторизация числа; 2) QuadraticRepresentations (представление простого числа в виде суммы двух квадратов). Для той же задачи подпрограмма QRM на компьютере Вейгона показала время 0,32 сек. Дальнейшие сравнения для различных чисел показали, что на компьютере Вейгона QRM несколько уступает по скорости. Однако на компьютере автора время решения было 0,15-0,16 сек., а подпрограмма DL не работала, поскольку основывалась на внутренних кодах фирмы «Mathematica». Кроме того, QRM решала задачу и для четных значений N, а также для случаев, когда N является произведением простых чисел, часть которых не круговые. Эти числа исключаются из произведения, и задача решается для произведения оставшихся круговых простых чисел. Подобным образом могут быть построены подпрограммы для остальных трех квадратичных представлений. Тогда для рассматриваемой задачи вначале находим  различных представлений числа в виде  .Далее исключаем из N число 5, и для числа N/5 получаем  квадратичных представлений вида  . Кроме этого, еще имеется по  квадратичных представлений вида  произведения четырех простых чисел . Этим исчерпываются возможности составного числа относительно его делителей, имеющих общие квадратичные представления.Подобные задачи было бы гораздо труднее решать, не имея предложенной выше классификации. Литература. 1. Эдвардс Г. Последняя теорема Ферма. Генетическое введение в алгебраическую теорию чисел. — М.: Мир, 1980. 2. Nagell T. "Diophantine Equations of the Second Degree." Ch. 6 in Introduction to Number Theory. New York: Wiley, pp. 188-226, 1951. 3. 3. David Bressoud, Stan Wagon. "Prime Imaginaries and Imaginary Primes." Ch. 9 in A Course in Computational Number Theory. Key College Publishing, San Francisco, 2000. 367 pp. . 4. Daniel Lichtblau. HalfGCD and Fast Rational Recovery. ISSAC’05, July 24–27, 2005, Beijing, China. |
Похожие:
 | Урок по математике 1 класс (1-4) апрель 2006г. Тема. Разностное сравнение чисел Прочитайте тему сегодняшнего урока. Как понимаете название темы? (Сравнение чисел с помощью разности) | | Документы 1. /Аппроксимация/1/lab5.doc 2. /Аппроксимация/2/CHM5.DOC |
| ІІ. Многообразие организационных форм в индустриальной экономике Мы хотим с помощью теоретических методов обнаружить то, что скрыто в реальной экономике от обыденного взгляда, то есть сущность или... | | Тема: Решение систем линейных уравнений с параметрами Определение. Системой линейных уравнений с двумя переменными называется два линейных уравнения, рассматриваемых совместно |
| Разложение чисел на простые множители В разложении числа 2-4 простых делителей не более 11 и одно простой делитель не более 100 | | Наибольший общий делитель. Цели урока Ввести определение наибольшего общего делителя, определение взаимно простых чисел, показать запись |
| Сложное высказывание Если несколько простых высказываний объединены в одно с помощью логических операций, то такое высказывание называется сложным | | В одномерном массиве произвольных чисел найти количество нечётных элементов Из одномерного массива произвольных чисел целых чисел сформировать 2 массива: a массив четных чисел и b массив нечетных чисел |
| Интернет-урок «Системы линейных уравнений» Проверьте, является ли пара чисел: а x=3, y=1; б x=2, y=2 решением системы уравнений ? | | М. А. Приходовский применение многомерных матриц для исследования гиперкомплексных чисел и конечномерных алгебр В работе рассматривается метод описания конечномерных алгебр и систем гиперкомплексных чисел с помощью пространственных матриц. Многомерные... |