2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: В натуральных числах
Сообщение22.06.2014, 11:08 


26/08/11
2108
Shadow в сообщении #878163 писал(а):
Пусть $(x,y)$ решение первого уравнения с наименьшим положительным $x\in (0,b)$
Здесь нужна коррекция. На самом деле наименьшее неотрицательное решение для $x \in[0,b)$ Тогда аналогичные рассуждения можно провести для наименьшего неотрицательного $y$. А если и $x=0 \text{ и } y=0$ являются решениями, то $a=b=1$Вообще наличие решения когда одна из переменных равна нулю можно рассмотреть отдельно

 Профиль  
                  
 
 Re: В натуральных числах
Сообщение22.06.2014, 12:09 
Заслуженный участник
Аватара пользователя


21/11/12
1968
Санкт-Петербург
Shadow в сообщении #878163 писал(а):
Можно доказать проще.

Очень хорошо (у меня ведь и не доказано ничего), а как на счет сумм? Собственно $S+s=\frac{(A-1)(B-1)AB}{2}=\frac{ \varphi _{AB}AB}{2}$ - сумма вз. простых, не превосходящих модуля, но я из этого и исходил. А вот $S-s=\frac{(A^2-1)(B^2-1)}{6}$ следует откуда-нибудь? И верно ли это вообще?

 Профиль  
                  
 
 Re: В натуральных числах
Сообщение23.06.2014, 19:24 
Заслуженный участник
Аватара пользователя


21/11/12
1968
Санкт-Петербург
Shadow в сообщении #878163 писал(а):
доказать...

Попробую если не доказать, то показать. Выберем пару простых: $7;11$, запишем для наглядности все числа до 77-и в таблицу $7\times 11$ и, вычеркнув столбец с кратными семи, покрасим кратные одиннадцати.
$$\begin{matrix}
 & 1 & 2 & 3 & 4 & 5 & 6\\ 
 & 8 & 9 & 10 & \color{red}{11} & 12 & 13\\ 
 & 15 & 16 & 17 & 18 & 19 & 20\\ 
 & \color{red}{22} & 23 & 24 & 25 & 26 & 27\\ 
 & 29 & 30 & 31 & 32 & \color{red}{33} & 34\\ 
 & 36 & 37 & 38 & 39 & 40 & 41\\ 
 & 43 & \color{red}{44} & 45 & 46 & 47 & 48\\ 
 & 50 & 51 & 52 & 53 & 54 & \color{red}{55}\\ 
 & 57 & 58 & 59 & 60 & 61 & 62\\ 
 & 64 & 65 & \color{red}{66} & 67 & 68 & 69\\ 
 & 71 & 72 & 73 & 74 & 75 & 76
\end{matrix}$$
Самый простой способ узнать разрешимо ли для некоторого числа уравнение (1) - вычитать из него последовательно один из множителей, пока не наткнешься на кратное другому множителю. В таблице это соответствует движению вверх по столбцу. Кратное находится, если выбранное число оказалось в столбце под красным числом (синяя зона), в противном случае уравнение (1) для выбранного числа неразрешимо (зеленая зона):
$$\begin{matrix}
 & \color{green}{1} & \color{green}{2} & \color{green}{3} & \color{green}{4} & \color{green}{5} & \color{green}{6}\\ 
 & \color{green}{8} & \color{green}{9} & \color{green}{10} & \color{red}{11} & \color{green}{12} & \color{green}{13}\\ 
 & \color{green}{15} & \color{green}{16} & \color{green}{17} & \color{blue}{18} & \color{green}{19} & \color{green}{20}\\ 
 & \color{red}{22} & \color{green}{23} & \color{green}{24} & \color{blue}{25} & \color{green}{26} & \color{green}{27}\\ 
 & \color{blue}{29} & \color{green}{30} & \color{green}{31} & \color{blue}{32} & \color{red}{33} & \color{green}{34}\\ 
 & \color{blue}{36} & \color{green}{37} & \color{green}{38} & \color{blue}{39} & \color{blue}{40} & \color{green}{41}\\ 
 & \color{blue}{43} & \color{red}{44} & \color{green}{45} & \color{blue}{46} & \color{blue}{47} & \color{green}{48}\\ 
 & \color{blue}{50} & \color{blue}{51} & \color{green}{52} & \color{blue}{53} & \color{blue}{54} & \color{red}{55}\\ 
 & \color{blue}{57} & \color{blue}{58} & \color{green}{59} & \color{blue}{60} & \color{blue}{61} & \color{blue}{62}\\ 
 & \color{blue}{64} & \color{blue}{65} & \color{red}{66} & \color{blue}{67} & \color{blue}{68} & \color{blue}{69}\\ 
 & \color{blue}{71} & \color{blue}{72} & \color{blue}{73} & \color{blue}{74} & \color{blue}{75} & \color{blue}{76}
\end{matrix}$$
Каждая пара слагаемых, дающих в сумме $77$ симметрична относительно центра таблицы (меняются местами при повороте на $180 ^{\circ}$), то же и "фигуры", выделенные цветами. Поэтому одно из слагаемых всегда окажется в синей зоне, а другое - в зеленой. Таким образом задача сводится к нахождению зеленой и синей сумм или разности между ними, поскольку общая сумма известна.

 Профиль  
                  
 
 Re: В натуральных числах
Сообщение28.06.2014, 23:15 
Заслуженный участник
Аватара пользователя


21/11/12
1968
Санкт-Петербург
Shadow в сообщении #878163 писал(а):
1. Если первое уравнение имеет решение в натуральных числах, то второе не имеет.

Подобное доказательство хорошо работает, если пойти от обратного. Рассмотрим пару натуральных $C=AX_1+BY_1$ и $c=AX_1-BY_1$. Могут ли оба этих числа оказаться в синей зоне? Если да, то существует пара $X_2,Y_2$ таких, что $AX_1-BY_1=AX_2+BY_2$, откуда $A(X_1-X_2)=B(Y_1+Y_2)$. Из неравенства $AX_1+BY_1<AB$ $\Leftrightarrow $ $\frac{X_1}{B}+\frac{Y_1}{A}<1$ видно, что $X_1<B$ и тем более $X_2<B$, но это противоречит предыдущему: при простых $A,B$ должно быть как минимум $B=X_1-X_2$. Следовательно, $c$ - зеленое, и существуют $\color{blue} {C'} \color{black}{=AB-}\color{green}{c}\color{black} {=AB-(AX_1-BY_1)=A(B-X_1)+BY_1}$ и $\color{green} {c'} \color{black}{=AB-}\color{blue}{C}\color{black} {=AB-(AX_1+BY_1)=A(B-X_1)-BY_1}$, для которых верно $\color{blue}{C}\color{black}{+}\color{blue}{C'}\color{black}{+}\color{green}{c}\color{black}{+}\color{green}{c'}\color{black}{=2AB.}$ Из неравенств $\color{blue}{C}\color{black}{>}\color{green}{c}\color{black}{;\ }\color{blue}{C'}\color{black}{>}\color{green}{c'}$ следует $\color{blue}{C+C'}\color{black}{>}\color{green}{c+c'}$, откуда $\color{blue}{C+C'}\color{black}{>AB}\color{black}{;\ }\color{green}{c+c'}\color{black}{<AB}$. Все четыре числа суть основания квадратов, сравнимых по $\mod AB$ (штрих - означает: противоположной четности). Тем самым доказаны два первых утверждения.

Решение первоначальной системы в общем виде можно записать так: $$x=\frac{u+\color{green}{c}}{2};\ y=\frac{u-\color{green}{c}}{2};\ z=\frac{AB-u+\color{green}{c'}}{2};\ t=\frac{AB-u-\color{green}{c'}}{2},$$ где $u$ - некоторое число подходящей величины и четности. Количество решений в прогрессии, заданной парой $\color{green}{c,c'}$ не зависит от $u$: $$y+t-1=\frac{AB-(\color{green}{c}\color{black}{+}\color{green}{c'}\color{black}{)}}{2}-1,$$ а количество прогрессий соответствует количеству различных пар $\color{green}{c}\color{black}{,}\color{green}{c'}$ в зеленой зоне: $$\frac{(A-1)(B-1)}{4}$$.
Суммируя, меняем $(\color{green}{c}\color{black}{+}\color{green}{c'}\color{black})$ на $s$, $AB$ - на $AB\frac{(A-1)(B-1)}{4}=\frac{S+s}{2}$ (полусумма вз. простых, не преышающих модуля), единицу - на $\frac{(A-1)(B-1)}{4}$. $$N=\frac{\frac{S+s}{2}-s}{2}-\frac{(A-1)(B-1)}{4}=\frac{S-s}{4}-\frac{(A-1)(B-1)}{4}$$
Предположительно $S-s=\frac{(A^2-1)(B^2-1)}{6}$, но формула получена на ощупь. Как это доказать - мне не известно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Gagarin1968


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group