Руст писал(а):
Объясню алгоритм проверки, ...
Ну, Вы пока не очень вошли в курс дела, поэтому я немного уточню то, что Вы пишете.
Я напомню, какие требования предъявляются к возможным контрпримерам. Предположим, что попарно взаимно простые натуральные числа
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
удовлетворяют уравнению
![$a^n+b^n=c^n$ $a^n+b^n=c^n$](https://dxdy-01.korotkov.co.uk/f/4/5/9/459b40d5928bd9ca56b6bd7505fdf73a82.png)
для некоторого простого
![$n>2$ $n>2$](https://dxdy-03.korotkov.co.uk/f/2/a/9/2a9dfa29692859379213db21d3f8a1f482.png)
. Тогда существуют такие натуральные числа
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
,
![$b_2$ $b_2$](https://dxdy-01.korotkov.co.uk/f/8/0/5/8050505667919156622832a0c9b5671c82.png)
,
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
,
![$c_2$ $c_2$](https://dxdy-03.korotkov.co.uk/f/e/3/5/e355414b8774603011922d600510b1df82.png)
, что
Заметим здесь, что число
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
(соответственно,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
) делится или не делится на
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
одновременно с числом
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
(соответственно,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
,
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
). Числа
![$a_2$ $a_2$](https://dxdy-03.korotkov.co.uk/f/2/c/a/2ca230a36892a5d996272ca45a782d1682.png)
,
![$b_2$ $b_2$](https://dxdy-01.korotkov.co.uk/f/8/0/5/8050505667919156622832a0c9b5671c82.png)
,
![$c_2$ $c_2$](https://dxdy-03.korotkov.co.uk/f/e/3/5/e355414b8774603011922d600510b1df82.png)
на
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
не делятся.
Эти формулы известны, кажется, лет двести. Я не знаю, существуют ли ещё какие-нибудь соотношения подобного рода.
Полезно также следующее утверждение:
если
, причём,
(и, естественно,
) делится на
при
, то ![$p^n\equiv q^n\pmod{n^{k-m+1+mn}}$ $p^n\equiv q^n\pmod{n^{k-m+1+mn}}$](https://dxdy-03.korotkov.co.uk/f/e/a/b/eab31f4e9a62a512aeaa49115352d9cc82.png)
.
Числа
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
можно выразить через
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
,
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
. Для удобства обозначим
Тогда
![$a=\frac{C+A-B}{2}$ $a=\frac{C+A-B}{2}$](https://dxdy-02.korotkov.co.uk/f/5/f/2/5f26ec90775f98586ae27bb9c37370c282.png)
,
![$b=\frac{C-A+B}{2}$ $b=\frac{C-A+B}{2}$](https://dxdy-02.korotkov.co.uk/f/1/1/1/111042f769b901919c2c6c2499d7548c82.png)
,
![$c=\frac{C+A+B}{2}$ $c=\frac{C+A+B}{2}$](https://dxdy-04.korotkov.co.uk/f/3/4/3/3438d038fb6c1d31e0adbb03d352798682.png)
.
Заметим ещё, что, если мы определили
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
младших
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
-ичных цифр чисел
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
и
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
, то это даёт нам
![$k+1$ $k+1$](https://dxdy-04.korotkov.co.uk/f/3/3/3/33359de825e43daa97171e27f6558ae982.png)
младших
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
-ичных цифр чисел
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
и
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
, которые должны удовлетворять соотношению
![$a^n+b^n\equiv c^n\pmod{n^{k+2}}$ $a^n+b^n\equiv c^n\pmod{n^{k+2}}$](https://dxdy-03.korotkov.co.uk/f/e/1/b/e1bc0a94852446a615803ba27d93b79582.png)
. Это немного усложняется в случае, когда одно из чисел
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
(и соответствующее число
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
,
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
) делится на
![$n^m$ $n^m$](https://dxdy-04.korotkov.co.uk/f/b/3/d/b3db50746c40ad6a469b8d60976ea45d82.png)
и не делится на
![$n^{m+1}$ $n^{m+1}$](https://dxdy-04.korotkov.co.uk/f/7/f/6/7f68e975ba8bf04a2555e4a005c4e4f282.png)
при
![$m>1$ $m>1$](https://dxdy-04.korotkov.co.uk/f/f/8/f/f8f3a61baf1d2600f63cbb4a5b99559082.png)
. Пусть, например,
![$b_1=b_0\cdot n^m$ $b_1=b_0\cdot n^m$](https://dxdy-04.korotkov.co.uk/f/f/4/0/f408b4db10b56f6b1a4e5276bb9676a382.png)
, где
![$mn<k+1$ $mn<k+1$](https://dxdy-04.korotkov.co.uk/f/f/7/3/f732a583e42544173e8aa9784e571cce82.png)
; тогда для числа
![$b_0$ $b_0$](https://dxdy-03.korotkov.co.uk/f/e/a/8/ea8adcd8cf746feb94319864409cdc7482.png)
нужно знать
![$k+1-mn$ $k+1-mn$](https://dxdy-04.korotkov.co.uk/f/f/a/3/fa35b81998a59f383e44a875a8a23ab682.png)
младших
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
-ичных цифр, а число
![$b_2$ $b_2$](https://dxdy-01.korotkov.co.uk/f/8/0/5/8050505667919156622832a0c9b5671c82.png)
определяется из условия
![$b_1b_2=b$ $b_1b_2=b$](https://dxdy-02.korotkov.co.uk/f/d/7/7/d7708dc80310bb0065b25adf0cc44b6282.png)
, или
![$b_0b_2=\frac{b}{n^m}$ $b_0b_2=\frac{b}{n^m}$](https://dxdy-04.korotkov.co.uk/f/b/4/f/b4fd1f4006eb6e04fcf353c8952aecd982.png)
. Это важно при последовательном подборе цифр чисел
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
и
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
, так как, если на каком-то шаге задать больше цифр числа
![$b_0$ $b_0$](https://dxdy-03.korotkov.co.uk/f/e/a/8/ea8adcd8cf746feb94319864409cdc7482.png)
, чем нужно, то легко попасть в тупик, когда продолжить число не удаётся.
Соотношения (1) - (6) следуют из основного уравнения
![$a^n+b^n=c^n$ $a^n+b^n=c^n$](https://dxdy-01.korotkov.co.uk/f/4/5/9/459b40d5928bd9ca56b6bd7505fdf73a82.png)
и учитываются Виктором Cорокиным в его рассуждениях. Если основное уравнение выполняется по модулю
![$n^{k+2}$ $n^{k+2}$](https://dxdy-03.korotkov.co.uk/f/a/d/0/ad0a51c3a7dbe9bf7e980a63de6c45a082.png)
, то соотношения (1) - (6) должны выполняться по модулю
![$n^{k+1}$ $n^{k+1}$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e45981a443b6c14f01bdbc5fc9b311b82.png)
; видимо, достаточно учитывать (1), (3) и (5), так как (2), (4) и (6) из них следуют. Поэтому построение контрпримера должно учитывать эти соотношения, и исходным является подбор чисел
![$a_1$ $a_1$](https://dxdy-01.korotkov.co.uk/f/8/e/8/8e830a5ab471143f1bb80e525c09bbaa82.png)
,
![$b_1$ $b_1$](https://dxdy-03.korotkov.co.uk/f/a/7/d/a7d0e0605a6acafe642d0b54226ac65082.png)
и
![$c_1$ $c_1$](https://dxdy-02.korotkov.co.uk/f/9/8/8/988584bba6844388f07ea45b7132f61c82.png)
(деление на
![$2$ $2$](https://dxdy-04.korotkov.co.uk/f/7/6/c/76c5792347bb90ef71cfbace628572cf82.png)
по модулю
![$n^{k+1}$ $n^{k+1}$](https://dxdy-02.korotkov.co.uk/f/1/e/4/1e45981a443b6c14f01bdbc5fc9b311b82.png)
, естественно, сводится к умножению на
![$\frac{n^{k+1}+1}{2}$ $\frac{n^{k+1}+1}{2}$](https://dxdy-01.korotkov.co.uk/f/8/1/f/81f88359400db930b8340977f3de2f6e82.png)
).
Уже простейший просчёт для
![$m=0$ $m=0$](https://dxdy-02.korotkov.co.uk/f/1/2/1/12162452d385d5b9e94588d07d95adca82.png)
и
![$k=1$ $k=1$](https://dxdy-04.korotkov.co.uk/f/7/e/b/7eb22be4bf74527b54b6d6093847814782.png)
показывает, что при
![$n\in\{3,5,11,17,23,29\}$ $n\in\{3,5,11,17,23,29\}$](https://dxdy-04.korotkov.co.uk/f/7/9/4/794b5cc0bba4930f717e0c2b2c3ec0b682.png)
не существует решений уравнения
![$a^n+b^n=c^n$ $a^n+b^n=c^n$](https://dxdy-01.korotkov.co.uk/f/4/5/9/459b40d5928bd9ca56b6bd7505fdf73a82.png)
, удовлетворяющих условиям (1), (3) и (5), если числа
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
все не делятся на
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
; кроме того, во всех найденных решениях
![$m\geqslant 2$ $m\geqslant 2$](https://dxdy-04.korotkov.co.uk/f/7/7/f/77f3dc1e7371a3989add75aa78d008c782.png)
, то есть, одно из чисел
![$a$ $a$](https://dxdy-01.korotkov.co.uk/f/4/4/b/44bc9d542a92714cac84e01cbbb7fd6182.png)
,
![$b$ $b$](https://dxdy-01.korotkov.co.uk/f/4/b/d/4bdc8d9bcfb35e1c9bfb51fc69687dfc82.png)
,
![$c$ $c$](https://dxdy-04.korotkov.co.uk/f/3/e/1/3e18a4a28fdee1744e5e3f79d13b9ff682.png)
должно делиться на
![$n^2$ $n^2$](https://dxdy-01.korotkov.co.uk/f/0/2/1/021273d50c6ff03efebda428e9e42d7782.png)
. Поэтому для этих значений
![$n$ $n$](https://dxdy-02.korotkov.co.uk/f/5/5/a/55a049b8f161ae7cfeb0197d75aff96782.png)
у Виктора Сорокина есть шанс доказать первый случай теоремы Ферма, а вот при
![$n\in\{7,13,19,31\}$ $n\in\{7,13,19,31\}$](https://dxdy-02.korotkov.co.uk/f/d/9/8/d98e5f64318de1089dc35c8b9773a4a182.png)
его идея точно не сработает. Значения
![$n>36$ $n>36$](https://dxdy-01.korotkov.co.uk/f/c/2/e/c2e23ec75db34a30395e18150ae7834082.png)
я не проверял.