(в связи с теоремой Ферма/Эйлера) как любителю "Изящной арифметики"
__________________________________ 300-летию Великого Леонарда Эйлера, посвящается
Привет!
И вновь я не получил от тебя какого-либо отклика и на моё предыдущее письменное сообщение, в котором я вывел для тебя, а точнее: ввёл, как мог, формулу "общего разложения" (представления в виде произведения с остатком) любого целого числа: b=q[b/q]+{b|q}; здесь q - соответственно, какое угодно натуральное число. Появление такого "разложения" непосредственно связано с понятиями: как целой части [b/q] от дроби b/q (нецелого частного), так и (натурального) остатка {b|q}<q от "неточного" деления на число q.
Теперь твоё молчание, я решил приписать слишком подробному и, главное, нудному(?) моему разжёвыванию многих, возможно очевидных для тебя, начальных сведений из арифметики как натуральных, так и целых чисел. Это тебя неприятно удивило?... Так удивиться может любой, хорошо знающий понятие целого числа и его простейшие свойства! Однако, мой друг, я попросту привёл отрывки из моего будущего учебника, о чём я уже сообщал тебе. Начальные сведения и понятия оттуда будут, как мне кажется, нужны и полезны твоим некоторым, скажем так, ровесникам. Ведь тому, кто что-нибудь да знает о целых числах, уже легче усваивать (воспринимать) всё то, что касается натуральных чисел уже как частного случая множества целых. Да! и более того, поскольку мои письма - открытые (для людей всего мира!), я уже получил один интересный отклик... (не от тебя ли?... под неизвестной мне маской...)
Однако мне ещё стало казаться, что тебе вовсе не интересно вникать в какие-либо доказательства Основного свойства простого числа: если p\ab (ab//p), тогда либо p\a (a//p), либо p\b (b//p). Такому свойству (любого) числа p я придумал название "альтернативная делимость": если p делит какое-нибудь составное число n=sm, то оно является делителем, по крайней мере, одного из сомножителей s,m данного числа. Такое число p будем называть "альтернативным делителем". Единица, в частности, является таким делителем! При этом, можно легко убедиться в том, что любой другой "альтернативный делитель" является простым числом. Если p не простое и больше единицы, то оно - составное p=sm, где s<p, m<p, и оно естественно не делит ни одного из этих своих же делителей. В связи с этим возникает иллюзия в том, что якобы также запросто можно доказать и обратное: простое число является альтернативным делителем! Кстати, вот тебе интересная задачка: будет ли "альтернативный делитель квадратов" - некое число q (q>1) со свойством: если q\nn, тогда q\n, - простым числом?... Если оно - не простое, то что за число тут такое?... (Прошу извинить за банальную рифму!)
Чтобы пробудить в тебе хотя бы малейший интерес к обоснованию этого свойства у простого числа, я отмечу следующее: любое простое число p не может быть делителем никакого составного числа вида sm, где числа s,m являются остатками делителя p (т.е. s,m - из семейства чисел {|p}; в первом письме вводилось такое обозначение в связи с понятием остатка от "неточного деления"). Это свойство (любого) числа будем называть "признаком простоты". Имеет место и обратное: числа с таким "признаком" (оказывается, они же и альтернативные делители!) являются простыми. Относительно этого утверждения, ты, возможно, скажешь: "Это тоже очевидный факт!" И в этом ты будешь прав: если некое число p>1 - не простое, тогда оно составное p=sm, и вновь мы видим s<p, m<p. В таком случае делимость sm//p противоречит "признаку простоты" для числа p, данному в нашем (обратном) утверждении, и поэтому мы всё-таки приходим к ожидаемому: p - простое. Однако доказать именно то, что любое простое число обладает признаком простоты, не каждому школьнику-отличнику под силу. Обосновать это, по существу, равнозначно доказательству наличия альтернативной делимости у простого числа! Оно требует особых рассуждений, хоть и простых, но не лежащих на поверхности. (Такое свойство "простоты," пожалуй, можно было бы назвать и "призРаком" простоты, учитывая то, что он появляется будто бы в виде некой "ауры" у некоторых простых чисел, в связи с чем и создаётся призрачная иллюзия в том, что можно легко и непосредственно убедиться в существовании этой "ауры" у любого простого числа!)
В любом случае, пожалуй, у тебя может возникнуть вопрос: к чему нам "признак простоты", присущий простому числу p?... Дело в том, что он как важное свойство простого числа, почти непосредственно используется для решения "задачки" Ферма/Эйлера, например, в качестве следующего утверждения.
Теорема (о полном семействе остатков делителя).
Пусть даны: простое число p и некое натуральное число x<p. Тогда остатки {x|p}, {2x|p}, ..., {(p-1)x|p} составляют семейство всех остатков делителя p: {|p} = {1,2,..., p-1}.
Справедливость теоремы для p=2 очевидна как тавтология, а при любом другом простом p в этом можно убедиться, используя признак простоты его. Если предположить, что какое-нибудь число как остаток делителя p отсутствует в данном наборе остатков от неточных делений: x/p, 2x/p,..., (p-1)x/p, тогда найдутся два различных числа y,z, удовлетворяющих условию y<z<p, но с одинаковыми остатками {yx|p}={zx|p}. В таком случае, используя формулу общего разложения целого числа в виде произведения с остатком, получим: zx-yx = p[zx/p]+{zx|p}-p[yx/p]-{yx|p} = p([zx/p]-[yx/p]). Здесь мы имеем: либо попросту некую нелепость zx={zx|p}={yx|p}=yx в том случае, когда соблюдаются соотношения yx<zx<p, либо делимость p\(z-y)x в другом случае, когда zx>p. Такая делимость не совместима с признаком простоты данного числа p. В итоге, мы полностью убеждаемся в справедливости этой теоремы.
Опираясь на эту, только что доказанную, теорему я могу легко убедить тебя в справедливости Теоремы Ферма/Эйлера моим методом в нескольких строках (для знатоков арифметики было бы достаточно половины стандартной страницы!). Прежде, чем приступить к решению этой Задачи, отметим ещё один факт как непосредственное применение понятия "остатка от неточного деления" с помощью предыдущей Теоремы, а точнее - очевидное и прямое
Следствие (из Теоремы о полном семействе остатков).
Пусть даны некоторые натуральные числа a<q, b<q, где q - простое. Тогда среди натуральных чисел a+b, 2a+b,..., (q-1)a+b, а также среди целых: a-b, 2a-b,..., (q-1)a-b, существуют (единственные) числа, которые делятся на q.
(Например: согласно очевидному неравенству b/a<q, в случае делимости a\b и только тогда во втором ряду разностей можно обнаружить нулевое число 0 =(b/a)a-b; оно и будет тем единственным, которое делится на число q).
Здесь достаточно непосредственно учесть вышедоказанную Теорему в связи с формулой:
ya=q[ya/q]+{ya|q} при разных y от 1 до q-1. (Не правда ли?!)
Теперь вновь обратимся к уже известной Лемме, о которой я тебе письменно сообщал ещё в прошлом году:
Лемма (к доказательству Теоремы Ферма/Эйлера). В семействе чисел N = {2,3,... p-2}, где p=4n+1 - простое, найдётся такое x, что p\(xx+1).
Предположим, что лемма не верна для какого-нибудь p>5, т.е. имеем p[\](xx+1) при любом x от 1 до p-1 (при этом ясно, почему числа 1 и p-1 заведомо не вошли в семейство N). Тут же заодно отметим и бесспорное: p[\](xx-1) при любом x из семейства N, в силу признака простоты числа p, поскольку мы имеем разложение на множители xx-1=(x-1)(x+1) и очевидные неравенства x-1<p, x+1<p.
Далее. В силу теоремы о полном семействе остатков, для каждого числа x<p найдётся одно и только одно некоторое y (y<p) - другое(!) число (по нашему предположению) с остатком {yx|p}=p-1 в соответствующем равенстве xy=p[xy/p]+p-1, согласно формуле общего разложения в виде произведения с остатком. В итоге, имеем p\(xy+1). Принимая обозначение x@y для такой пары чисел, будем называть её "приятельской". Например: 1@p-1 - приятельская пара, но она вне семейства N; другая приятельская пара 2@(p-1)/2 находится именно в семействе N.
Таким образом, имеем: 1) для каждого числа x найдётся "приятель" y и они, образуя вместе приятельскую пару x@y, могут быть "приятелями" только(!) друг другу; 2) количество чисел в семействе N равно 4n-2=(p-1)-2, и они составляют 2n-1 приятельских пар. Но при этом обнаруживается и то, что количество таких "парочек" должно быть чётным(!) числом. Ведь вместе с некоторой парой x@y из N другие числа p-x,p-y тоже находятся в семействе N и образуют приятельскую пару p-x@p-y. Действительно: 1<p-x<p-1 и 1<p-y<p-1, но такие совпадения p-x=x или p-x=y невозможны, так как: 2[\]p и, к тому же, p[\](p-x)x+1, поскольку имеет место равенство (p-x)x+1=px-(xx-1), где число xx-1 не делится на p (см. начало доказательства). Однако имеется делимость p\((p-x)(p-y)+1), в силу равенства (p-x)(p-y)+1 = xy+1+p(p-x-y).
Из такого противоречия возможен лишь один выход - а точнее, мы получаем вывод: имеет место (точная!) делимость p\(xx+1) при некотором x < p-1.
Лемма верна!
Теперь я с помощью своего метода могу показать классический так называемый "неопределённый спуск", который мы будем в нашем случае называть "монотонным спуском" и которым мы завершим, по существу, доказательство Теоремы Ферма/Эйлера.
Пусть некая сумма aa+bb (a,b - целые числа) удовлетворяет неравенствам p<aa+bb<pp и условию делимости p\(aa+bb). Тогда существуют такие целые c,d, что p\(cc+dd), и при этом: 0<cc+dd<aa+bb.
Поскольку число aa+bb - составное, имеем mp=aa+bb, где m - некий правильный (см. 1-ое письмо) делитель: p>m>1. Тогда, кроме числа p, есть другое простое число q (например, наименьший правильный делитель числа m, q<p) с делимостью q\(aa+bb). Если бы мы имели: q\a (а также: q\b), то целые числа c=a/q, d=b/q были бы искомыми. Остаётся рассмотреть случай: q[\]a и (как следствие) q[\]b. В таком случае, воспользуемся тем, что среди чисел: b, a-b, 2a-b, ... , (q-1)a-b, найдётся такое xa-b, которое делится на q: (ax-b)//q. В последнем можно убедиться, если привлечь два разложения на множители с остатками: a=q[a/q]+{a|q}, b=q[b/q]+{b|q}. В силу Следствия (из Теоремы о полном семействе остатков), при некотором x (x<q) имеет место делимость (x{a|q}-{b|q})//q. В итоге, согласно справедливому тождеству
(ax-b)(ax-b) + (a+bx)(a+bx) = (xx+1)(aa+bb),
вновь обнаруживаются искомые целые(!) числа c=(ax-b)/q и d=(a+bx)/q. Они, в связи с тем же тождеством и в силу неравенства xx+1 < qq, удовлетворяют требуемым соотношениям: 0 < cc+dd = (xx+1)(aa+bb)/qq < aa+bb < pp. При этом, очевидно, мы имеем: p\(cc+dd). Чтобы ничто не смущало, на всякий случай, отметим здесь: cc>0 и dd>0. Например, такой случай ax=b невозможен, поскольку иначе, когда c=(ax-b)/q=0, получилась бы очевидная нелепость: делимость dd//pp вместе с неравенством dd<pp.
В заключение, мой друг, я отмечу другую точку зрения, как на метод доказательства Леммы, так и на метод "монотонного спуска" в связи с завершением доказательства Теоремы Ферма/Эйлера.
Таким методом "спуска", в частности, легко обнаруживать и удалять (в первую очередь) простое число q другого вида q=4[q/4]+3, которое вдруг оказалось делителем какого-нибудь числа в виде суммы двух квадратов целых чисел. Поэтому такой метод можно называть и способом "удаления посторонних делителей", или методом "конечного спуска к абсурду", так как иногда после окончания "спуска" какое-нибудь число должно принять нелепый для него вид, например: q=4[q/4]+3 в виде суммы лишь двух(!) точных квадратов. К тому же, например, используя другое равенство (ax+7b)(ax+7b)+7(a-bx)(a-bx)=(xx+7)(aa+7bb) - вновь как частный случай тождества Фибоначчи! - можно получить и новый результат: если простое число p>4 делит число вида aa+7bb при условии p[\]ab, тогда имеем: p=cc+7dd, где a,b,c,d - некоторые целые числа.
Ну а метод доказательства Леммы можно применить, в частности, и к простым числам p=8[p/8]+1, p=8[p/8]+3 в связи с разложением их в "квадратичную форму" p=aa+2bb, а также и к таким простым: 20[p/20]+3, 20[p/20]+7, чтобы показать, что каждое из этих простых чисел является делителем некоторого числа вида xx+5yy, где x,y - натуральные взаимно простые числа (как завещал нам знаменитый Пьер Ферма!).
Оказалось, что имеются и такие конструкции, похожие на те, которые использованы для доказательства как Леммы, так и всей Теоремы Ферма/Эйлера, и легко применимые к обоснованию, например, такого утверждения (его можно было бы назвать леммой Эйлера/Лагранжа): любое простое число есть сумма не более четырёх квадратов (7=1+1+1+4).
В конце концов, можно по-другому и весьма просто доказать и Теорему Лагранжа о том, что любое натуральное число есть сумма не более четырёх квадратов.
К этой "ТАИНСТВЕННОЙ" стороне моих методов я вернусь с подробностями в каком-нибудь другом письме!
Всего доброго тебе!
P.S.:
Согласись, мой друг, с тем, что Шерлок Холмс о нашей доказанной Лемме сказал бы: "Это же элементарно, Ватсон!"
Вот, к примеру, пусть p=5 и предположим, что мы сразу не догадались о том, что 5=1+2·2, и подумали бы: 5[\](xx+1) для всех чисел x от 1 аж(!) до 5. Тогда, в силу теоремы о семействе остатков и в связи с остатком 4, мы имели бы: 5\(1·4+1), 5\(2·3+1)!? Единица может "дружить" только с Четвёркой: 5\(1·4+1), а Двойке и Тройке в своём семействе N={2,3} остаётся "дружить" только друг с другом по остатку 4. Вот и получилась НЕЛЕПОСТЬ: 5\(2·3+1). Однако, если бы нам было дано очень большое простое число p, мы случайно могли бы и не заметить такой нелепости (например, вычисляя последовательно произведение и деление, как-то незаметно умудрились бы сделать какую-нибудь ошибку, или мы вообще не имели бы возможности закончить большие вычисления).
Якобы не замечая нелепости, мы рассуждаем далее и находим в семействе N ещё(?) одну "дружную" пару чисел 5-2@5-3 - будто бы другую! Ведь не может быть 2=5-2 (правильно: 5-2=3). Но возможно ли такое 2=5-3? Теперь-то уж легко видеть: 5[\]((5-3)·3+1) = 5·3-(3·3-1). Пятёрка (справедливо!) не делит семёрку (опять ту же шестёрку с единицей). Более того, отсутствие делимости можно обнаружить проще, что и было отмечено в начале доказательства Леммы, т.е. без конкретных вычислений произведения двух чисел и, вслед за ним, ещё и деления одного на другое, - безошибочно, стало быть! Здесь, да и в других подобных случаях, результат арифметических действий вовсе не нужен, поскольку очевидно следующее: 3·3-1=(3-1)(3+1), 2<5 и 4<5. В силу признака простоты, получается: (2·4)[/]5 и, следовательно, (5·3-2·4)[/]5. Итак, оказывается, что числа 2,3 вовсе и не были "друзьями", и не могут соединяться в приятельскую пару.
Такое противоречие с тем, что в семействе N вообще лишь одна пара чисел, в конце концов, и вынуждает нас понять, что причина появления всех нелепостей находится в нашем предположении: 5[\](xx+1) для всех чисел x от 1 до 5. - Именно в том, чего мы якобы не заметили: Двойка и Тройка могут "дружить" по остатку 4 только сами с собой; оба квадрата 2·2, 3·3 дают остаток 4={2·2|5}={3·3|5}.
В итоге, получилось: Лемма для p=5 верна. Имеется, например, делимость 5\(3·3+1). И, более того, обнаружилось даже равенство 5=1·1+2·2 как самый очевидный частный случай к подтверждению Теоремы Ферма/Эйлера.
Что касается доказательства утверждения "о признаке простоты простого числа" (я опустил его, чтобы тебя пока не удручать "банальностями"), я обязательно напишу что-нибудь об этом, чтобы как-то чем-то тебя удивить: ведь моё доказательство, пожалуй, самое короткое среди всех тех, которые мне довелось когда-то увидеть и понять из других публикаций. Как "подсказку" я мог бы поместить своё обоснование "признака" простого числа в трёх(!) строках всего лишь.
Успехов тебе!
___________
POST FACTUM:
Обозначения {b"q},{"q} и {b./.q},{.../q} (для "остатка" и "семейства остатков") не будут применяться в дальнейшем - в некоторых письмах они уже заменены или будут заменяться на другие {b|q},{|q} (иногда, на такие {b:q},{:q}), по возможности.