Гипотеза Била

[MMZ]

mihaild в сообщении #1341314 писал(а):

Итого, определение, видимо, такое: пусть $R$ и $T$ взаимно просты. Тогда коэффициентом делимости для $T$ в системе основания $R$ называется число $D$, обратное $R$ по модулю $T$.

Кажется немного разобрался.

Пусть $A, B$ взаимно просты $\Leftrightarrow$ в системе счисления по основанию $B$ НОД $(B, A) = 1$

$\dfrac{10 \cdot b + k}{10} = b + \dfrac{k}{10}$

Согласно китайской теореме об остатках $A \cdot (-1)^{n-1} \cdot P_ {n-1} \equiv 1 \mod 10$. Следовательно, $-b$ обратно $A$ по модулю $B$ и является коэффициентом делимости.

[mihaild]

MMZ в сообщении #1341619 писал(а):

Тогда в системе счисления по основанию $B$ НОД $(10, A) = 1$

1. НОД от основания системы счисления не зависит.
2. $A = 10$ и $B = 7$ взаимно просты, но $\text{НОД}(10, A) \neq 1$.

MMZ в сообщении #1341619 писал(а):

Согласно китайской теореме об остатках $A \cdot (-1)^{n-1} \cdot P_ {n-1} \equiv 1 \mod 10$.

Непонятно, что такое $P_{n - 1}$. И китайская теорема об остатках говорит про системы, так что непонятно, причем она тут.

Давайте для начала рассмотрим систему счисления по основанию $10$. Возьмем число вида $10b + 1$. Хотим найти коэффициент делимости:
$10D \equiv 1 \mod 10b + 1$
$10D = 1 + k(10 b + 1)$ - это уже просто уравнение на $D, k$
Возьмем, например, $k = -1$ (не для всех $k$ уравнение обязано быть разрешимо относительно $D$, но может повезет). Получим $10D = 1 - 10b - 1 = -10b$, откуда $D = -b$.

[MMZ]

mihaild в сообщении #1341622 писал(а):

Непонятно, что такое $P_{n - 1}$

числитель предпоследней подходящей дроби для числа $\dfrac{A}{B}$ в системе счисления по основанию $B$.

mihaild в сообщении #1341622 писал(а):

И китайская теорема об остатках говорит про системы, так что непонятно, причем она тут.

Прочёл об этом тут (см. теорему 2).

[mihaild]

MMZ в сообщении #1341628 писал(а):

Прочёл об этом тут
(см. теорему 2).

Это уже не китайская теорема об остатках.

MMZ в сообщении #1341619 писал(а):

$A \cdot (-1)^{n-1} \cdot P_ {n-1} \equiv 1 \mod 10$. Следовательно, $-b$ обратно $A$ по модулю $B$

Нет, следовательно $-b$ обратно $10$ по модулю $B$. Т.к. когда вы пользуетесь выражением обратного через подходящие дроби, в знаменателе исходной дроби должно стоять число, обратное которому вы считаете (а в числителе - модуль; у вас не написано, что такое $b$ и $k$ - верно ли, что $B = 10b + k$?).

[MMZ]

mihaild в сообщении #1341633 писал(а):

Нет, следовательно $-b$ обратно $10$ по модулю $B$.

Но ведь $10_B = B_{10}$

-- 26.09.2018, 16:33 --

mihaild в сообщении #1341633 писал(а):

у вас не написано, что такое $b$ и $k$ - верно ли, что $B = 10b + k$

Видимо я задумался настолько, что начинаю "проглатывать" куски доказательств.
Да, верно.

[mihaild]

MMZ в сообщении #1341641 писал(а):

Но ведь $10_B = B_{10}$

А так у вас $10$ в записи - это $10_B$ на самом деле? Тогда да, всё верно. Но лучше такие вещи явно указывать.
В любом случае, я как-то пропустил - $b$ не обязательно является предпоследней подходящей дробью для $b + \frac{k}{10}$. Собственно никогда не является кроме случая $k = 1$.

[MMZ]

mihaild в сообщении #1341622 писал(а):

Давайте для начала рассмотрим систему счисления по основанию $10$. Возьмем число вида $10b + 1$. Хотим найти коэффициент делимости:
$10D \equiv 1 \mod 10b + 1$
$10D = 1 + k(10 b + 1)$ - это уже просто уравнение на $D, k$
Возьмем, например, $k = -1$ (не для всех $k$ уравнение обязано быть разрешимо относительно $D$, но может повезет). Получим $10D = 1 - 10b - 1 = -10b$, откуда $D = -b$.

Кажется разобрался в этом, понял как Л.Ф. Громова получила свои коэффициенты делимости. Найдём коэффициент делимости для числа, заканчивающегося в десятичной системе счисления на $3$:
$10D \equiv 1 \mod 10b + 3$
$10D = 1 + k(10 b + 3)$
При $k = 3$
$10D = 1 + 30b + 9 = 30b + 10$
$D = 3b + 1$
Совпало.

Следовательно, коэффициент делимости можно вывести в системе счисления по любому основанию $B$ для любого числа, последняя цифра $b_0$ которого не кратна $B$.
$B\cdot D \equiv 1 \mod B\cdot b + b_0$
$B\cdot D = 1 + k(B \cdot b + b_0)$
$B(D - k \cdot b) - k \cdot b_0 = 1$
$m \cdot B - k \cdot b_0 = 1$
Так как НОД $(B, b_0) = 1$, то это уравнение всегда имеет решения.

[mihaild]

Да, всё правильно. Все эти разговоры про коэффициент делимости - просто слегка замаскированная арифметика по соответствующим модулям.

[MMZ]

Значит для завершения доказательства осталось разобраться только в этом:

MMZ в сообщении #1341242 писал(а):

число $P$ делится на $T$, если число $P$ без $n$ последних цифр плюс $n$ последних цифр, умноженных на $D^n$ , делится на $T$

В какую сторону стоит начать думать, не подскажете?

[mihaild]

Для завершения доказательства чего? Гипотезы Била? Оно пока что даже не начато (не указано, про какую систему исчисления речь).

Основную идею я уже написал: если мы работаем в системе по основанию $R$, то обозначим "последние $n$ цифр" за $b$, а число без них - за $a$.
Тогда имеем $P = b + a R^n$, а число, про которое мы говорим - $D^n b + a$. И нужно из того, что $DR \equiv 1 \mod T$ и $D^n b + a \equiv 0 \mod T$ вывести $b + a R^n \equiv 0 \mod T$. Для этого достаточно того, что сравнения по модулю можно перемножать аналогично равенствам, и заменять в них какие-то величины на сравнимые с ними.

[MMZ]

Формулировка: если $A^x + B^y = C^z $, где $A, B, C, x, y, z $\in$ N$ и $x, y, z > 2$, то $A, B, C$ имеют общий простой делитель.
Доказательство: для доказательства введём понятие коэффициента делимости $D$.

Пусть B^y = b^{v_1}_1 \cdot b^{v_2}_2 \cdot ... \cdot b^{v_i}_i$ - каноническое разложение числа $B^y$ на множители, $r, s$ - соответственно последняя цифра и число десятков числа $\frac{B^y}{b^y_i}$ , записанного в системе счисления по основанию $b^y_i$, НОД $(b_i, r) = 1$, $k, d \in \mathbb{Z}$ тогда $D$ решением системы

$$\left\{ \begin{array}{rcl} -b^y_i < k < b^y_i \\ -b^y_i < d < b^y_i \\ D = k \cdot s + d \\ D \equiv 1 \mod b^y_i \\ \end{array} \right.$$

Лемма 1: В системе счисления, основанием которой является простое число, $D$ вычислим для любых чисел, оканчивающихся на отличную от ноля цифру.
Доказательство леммы 1: следует из того факта, что уравнение $a \cdot x + b \cdot y = 1$ всегда имеет решение.

Лемма 2: число $P$ делится на $T$, если число $P$ без $n$ последних цифр плюс $n$ последних цифр, умноженных на $D^n$ , делится на $T$.
Доказательство леммы 2: необходимо.

Не теряя общности, можем считать, что $A^x > B^y$, следовательно в системе счисления по основанию $b^y_i$ мы можем записать число $A^x$ как $a_1$ - $y$ последних его цифр, $a_0$ - остальные цифры. Тогда:

Если $D$ не вычислим, $A \vdots b_i$, иначе

$$\left\{ \begin{array}{rcl} a_0 + a_1 \cdot D^y = q \cdot A \\ a_0 \cdot 10^y + a_1 = A^x \\ \end{array} \right.$$

Домножим правые части, приравняем их и выразим $a_0$

$a_0 = \dfrac{a_1 \cdot (D^y \cdot A^{x-1} - q)}{10^y \cdot q - A^{x-1}}$

Если $A^{x-1}$ кратно $10^y$, то гипотеза доказана, иначе $a_0 = t \cdot a_1$

Следовательно, $A^x = a_1 \cdot t \cdot 10^y + a_1$

Разделив на $a_1$ и переведя в десятичную систему счисления, получим уравнение

$m \cdot A^{x-1} = B^y \cdot t +1$, которое в натуральных $A, B, t$ имеет единственное решение $m = 1, A = 3, x = 3, B = 2, y = 3, t = 1$, при котором $C^z = 3^3 + 2^3 = 35$ не является степенью натурального числа.

Доказано.

Литература:
Л.Ф. Громова "Признаки делимости чисел с окончаниями 1, 3, 7, 9", журнал научных публикаций аспирантов и докторантов.

[grizzly]

Прочитал пока последние 2 строчки:

MMZ в сообщении #1342031 писал(а):

$m \cdot A^{x-1} = B^y \cdot t +1$, которое в натуральных $A, B, t$ имеет единственное решение $m = 1, A = 3, x = 3, B = 2, y = 3, t = 1$

Берём первое, что пришло в голову: $A=3, x=5, m=1, t=10, B=2, y=3$. Вроде подходит.

[yk2ru]

MMZ в сообщении #1342031 писал(а):

$D \equiv 1 \mod b^y_i$

Коэффициента делимости $D$ должен давать остаток 1 при деление на основание системы счисления? Не заметил такого для коэффициентов делимости при основании 10, иногда разве что такое бывает.

[MMZ]

Формулировка: если $A^x + B^y = C^z $, где $A, B, C, x, y, z $\in$ N$ и $x, y, z > 2$, то $A, B, C$ имеют общий простой делитель.
Доказательство: для доказательства введём понятие коэффициента делимости $D$.

Пусть $B^y = b^{v_1}_1 b^{v_2}_2 ... b^{v_i}_i $- каноническое разложение числа $B^y$ на множители, $r, s$ - соответственно последняя цифра и число десятков числа $\frac{B^y}{b^{v_i}_i}$ , записанного в системе счисления по основанию $b^{v_i}_i$, $k, d \in \mathbb{N}$ тогда $D$ решением системы

$$\left\{ \begin{array}{rcl} 0 < k < 10 \\ 0 < d < 10 \\ D = k \cdot s + d \\ 10 \cdot D \equiv 1 \mod b^{v_1}_1 b^{v_2}_2 ... b^{v_{i-1}}_{i-1} \\ \end{array} \right.$$

Лемма 1: В системе счисления, основанием которой является простое число, $D$ вычислим для любых чисел, оканчивающихся на отличную от ноля цифру.
Доказательство леммы 1: следует из того факта, что уравнение $a \cdot x + b \cdot y = 1$ всегда имеет решение.

Лемма 2: число $P$ делится на $T$, если число $P$ без $n$ последних цифр плюс $n$ последних цифр, умноженных на $D^n$ , делится на $T$.
Доказательство леммы 2: необходимо.

Не теряя общности, можем считать, что $A^x > B^y$, следовательно в системе счисления по основанию $b^y_i$ мы можем записать число $A^x$ как $a_1$ - $y$ последних его цифр, $a_0$ - остальные цифры. Тогда:

Если $D$ не вычислим, $A \vdots b_i$, иначе

$$\left\{ \begin{array}{rcl} a_0 + a_1 D^y = q A \\ a_0 10^y + a_1 = A^x \\ 10^y D^y = 1 + p \cdot b^y_1 b^y_2 ... b^y_{i-1} = 1 + p t\\ \end{array} \right.$$

где $b^y_1 b^y_2 ... b^y_{i-1}$ разложение числа $\frac{B^y}{b^{v_i}_i}$ на множители.

$a_1 = A^x - a_0 10^y = A^x - 10^y (q A - a_1 D^y) = A^x - 10^y q A + a_1(p t + 1)$

$A^x - 10^y q A + a_1 p t = 0$

Домножив на $t$, получим

$a_1pt^2 + tA^x - B^y q a = 0 (1)$ - квадратное уравнение относительно $t$. Так как, согласно основной теореме арифметики, $t$ должно быть определено однозначно, следовательно, (1) должно быть полным квадратом. Но полным квадратом оно быть не может, поскольку имеет свободный член со знаком минус. Следовательно, $t = 1$ и $B$ простое.

Помогите, пожалуйста, снова не могу найти ошибку.

Литература:
Л.Ф. Громова "Признаки делимости чисел с окончаниями 1, 3, 7, 9", журнал научных публикаций аспирантов и докторантов.

[mihaild]

MMZ в сообщении #1342589 писал(а):

Так как, согласно основной теореме арифметики, $t$ должно быть определено однозначно, следовательно, (1) должно быть полным квадратом. Но полным квадратом оно быть не может, поскольку имеет свободный член со знаком минус.

Ничего не понял. (1) - это уравнение, как оно может быть или не быть полным квадратом? Какое отношение основаня теорема арифметики имеет к квадратным уравнениям? Как из знака свободного члена можно что-то вывести про разрешимость уравнения в целых числах?

(еще предлагаю вместо систем счисления, коэффициентов делимости и прочего говорить сразу о сравнениях по модулю - скорее всего станет сильно проще читать)