2014 dxdy logo

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

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




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


26/08/11
2066
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
1881
Санкт-Петербург
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
1881
Санкт-Петербург
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
1881
Санкт-Петербург
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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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