V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм icon

V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм



НазваниеV. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм
Дата конвертации27.06.2012
Размер120.2 Kb.
ТипДокументы


УДК 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



Эллиптические1





Эллиптические2



Эллиптические2





Круговые

Эллиптические1



гиперболические










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

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

С другой стороны круговое простое число 97 имеет все квадратичные формы представления, т.к. , но пересекается только с множеством Эллиптические-2.

Предлагаемые ранее перечисления множеств простых чисел, например [2,стр. 188], не являются классификацией, т.к. не основываются на общем признаке. Предлагаемая классификация имеет в своей основе такой признак, а именно: любое произведение простых чисел, имеющих одинаковую квадратичную форму из Табл.1, имеет представление в виде такой же квадратичной формы. Отсюда следует, что произведение простых чисел, принадлежащих к одному из множеств Табл.1, имеет представление в виде основной квадратичной формы этого множества.

Таким образом, основой для классификации простых чисел является известная формула для частных случаев композиции квадратичных форм[1, стр.396]

(2) где .

Упомянутое выше перечисление в [2,стр. 188], таким свойством не обладает, т.к. содержит простые числа, имеющие квадратичные формы .

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


Табл.2



^ Простые числа

Квадратичная форма

Линейная форма

Доля в общем множестве простых чисел

Другие возможные формы

представления

Круговые









Эллиптические1









Эллиптические2









гиперболические










В классификации Табл.2 все же имеются множества, содержащие частично пересекающиеся подмножества. Их можно выделить, если за основу взять непересекающиеся подмножества, соответствующие непересекающимся классам эквивалентности по модулю 24.

Будем обозначать квадратичные формы как круговая, эллиптические 1 и 2, гиперболическая.


Табл.3


Классификация простых чисел с помощью непересекающихся множеств


^ Простые числа

Основная квадратичная форма

Линейная форма

Доля в общем множестве простых чисел

Другие квадратичные формы

представления

Круговые









Круговые









Круговые









Круговые









Эллиптические1










Эллиптические1









Эллиптические2









Гиперболические










Полученную классификацию применим для анализа различных задач теории чисел. Рассмотрим вначале, к какому множеству относятся простые числа Мерсенна . Нетрудно непосредственно проверить, что при нечетном единственно возможная линейная форма относится к Эллиптическим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.




Похожие:

V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconУрок по математике 1 класс (1-4) апрель 2006г. Тема. Разностное сравнение чисел
Прочитайте тему сегодняшнего урока. Как понимаете название темы? (Сравнение чисел с помощью разности)
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconДокументы
1. /Аппроксимация/1/lab5.doc
2. /Аппроксимация/2/CHM5.DOC
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconІІ. Многообразие организационных форм в индустриальной экономике
Мы хотим с помощью теоретических методов обнаружить то, что скрыто в реальной экономике от обыденного взгляда, то есть сущность или...
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconТема: Решение систем линейных уравнений с параметрами
Определение. Системой линейных уравнений с двумя переменными называется два линейных уравнения, рассматриваемых совместно
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconРазложение чисел на простые множители
В разложении числа 2-4 простых делителей не более 11 и одно простой делитель не более 100
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconНаибольший общий делитель. Цели урока
Ввести определение наибольшего общего делителя, определение взаимно простых чисел, показать запись
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconСложное высказывание
Если несколько простых высказываний объединены в одно с помощью логических операций, то такое высказывание называется сложным
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconВ одномерном массиве произвольных чисел найти количество нечётных элементов
Из одномерного массива произвольных чисел целых чисел сформировать 2 массива: a массив четных чисел и b массив нечетных чисел
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconИнтернет-урок «Системы линейных уравнений»
Проверьте, является ли пара чисел: а x=3, y=1; б x=2, y=2 решением системы уравнений ?
V. A. Meschkoff классификация простых чисел с помощью линейных и квадратичных форм iconМ. А. Приходовский применение многомерных матриц для исследования гиперкомплексных чисел и конечномерных алгебр
В работе рассматривается метод описания конечномерных алгебр и систем гиперкомплексных чисел с помощью пространственных матриц. Многомерные...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов