Свойства комбинаторного разложения

[age]

Доказать, что существуют четыре числа $a,b,c,d>0$ над $\mathbb{Z}$, $ac-bd=1$ такие, что разложением $ad+bc$ можно представить всякое целое число $n>\varepsilon$.

[Руст]

Это скорее всего неверно. К тому же она не является задачей олимпиадного типа.

[age]

Не спорю, может и не олимпиадного. Что нам известно о диофантовых уравнениях $ax-by=p$? У всех них вначале ищется частное решение $(x_0,y_0)$ и затем путём добавления $a,b$ строится общее решение, которое имеет вид:
$\begin{cases} x=x_0+kb\\ y=y_0+ka \end{cases}$
других решений, насколько мне известно нет.

Тогда применяя к нашему условию, получаем условия на $c,d$:
$\begin{cases} c=c_0+kb\\ d=d_0+ka \end{cases}$
откуда:
$ad+bc=a\cdot(d_0+ka)+b\cdot(c_0+kb)=ad_0+bc_0+k(a^2+b^2)$

Остаётся уточнить вопрос о начальных условиях $(c_0, d_0)$, и ответить на вопрос можно ли такой формой представить любое целое число $n>\varepsilon$. По-моему, можно. Либо дать форму целых чисел, не представимых такой формой.

(Оффтоп)

К сожалению, я позабыл, как строится частное решение уравнения $ax-by=1$. Может кто напомнит? По-моему, как-то через сравнения по модулям $a, b$. Например, $13x-17y=1$.

[MrDindows]

age в сообщении #422478 писал(а):

Не спорю, может и не олимпиадного. Что нам известно о диофантовых уравнениях $ax-by=p$? У всех них вначале ищется частное решение $(x_0,y_0)$ и затем путём добавления $ab$ строится общее решение, которое имеет вид:
$\begin{cases} x=x_0+kab\\ y=y_0+kab \end{cases}$
других решений, насколько мне известно нет.

Та вы хотя бы подставьте эти $x$ и $y$ в начальное уравнение и увидите, что это не так)
Пусть $x,y$ - решение $ax-by=p$. Тогда, по вашему:
$a(x+kab)-b(y+kab)=ax-by+kab(a-b)=p+kab(a-b)=p $Что явно не верно)
Должно вообще-то быть так:
$\begin{cases} x=x_0+kb\\ y=y_0+ka \end{cases}$

[age]

Да, верно, ошибся, забыл что там уже идёт доумножение на $a$ и $b$. Исправил.

[MrDindows]

age в сообщении #422478 писал(а):

К сожалению, я позабыл, как строится частное решение уравнения $ax-by=1$. Может кто напомнит? По-моему, как-то через сравнения по модулям $a, b$. Например, $13x-17y=1$.

$13x\equiv 1 \ mod \ 17 $
Пфф, а вобще не так)
Надо выразить $x$ через $y$.
$x=\frac{17y+1}{13}=y+\frac{4y+1}{13} $
Значит $\frac{4y+1}{13}=z, \ z \in Z$
Откуда выражается $y$:
$y=\frac{13z-1}{4}=3z+\frac{z-1}{4} $
$\frac{z-1}{4}$ - Тоже должно быть целым, значит $z=4k+1$.
И возвращаем всё это в начальные переменные.
$y=3z+k=13k+3$
$x=y+z=17k+4$

[Руст]

Я писал скорее всего неверно, потому, что ваша система эквивалентно разложению:
$1+in=(a+bi)(c+di)$.
Если любое такое число больше некоторого разлагается, то простых вида $n^2+1$ конечное число (это эквивалентное утверждение).

Уравнение $ax-by=1$ решается алгоритмом Евклида при вычислении $gcd(a,b)$ по этому алгоритму одновременно находятся $x,y$.

[age]

MrDindows в сообщении #422495 писал(а):

$13x\equiv 1 \ mod \ 17 $

Нет-нет, там была какая-то более точная формула (без иксов), как выразить $x_0$ только через $13,17$ и $1$.

-- Вс мар 13, 2011 18:11:55 --

Руст в сообщении #422496 писал(а):

Уравнение $ax-by=1$ решается алгоритмом Евклида при вычислении $gcd(a,b)$ по этому алгоритму одновременно находятся $x,y$.

Да. А математически записать можно решение в виде формулы?

[MrDindows]

age в сообщении #422499 писал(а):

MrDindows в сообщении #422495 писал(а):

$13x\equiv 1 \ mod \ 17 $

Нет-нет, там была какая-то более точная формула (без иксов), как выразить $x_0$ только через $13,17$ и $1$.

-- Вс мар 13, 2011 18:11:55 --

Руст в сообщении #422496 писал(а):

Уравнение $ax-by=1$ решается алгоритмом Евклида при вычислении $gcd(a,b)$ по этому алгоритму одновременно находятся $x,y$.

Да. А математически записать можно решение в виде формулы?

Выше решение смотрите. Сходу или с помощью формулы- никак.

[nnosipov]

age в сообщении #422499 писал(а):

MrDindows в сообщении #422495 писал(а):

$13x\equiv 1 \ mod \ 17 $

Нет-нет, там была какая-то более точная формула (без иксов), как выразить $x_0$ только через $13,17$ и $1$.

-- Вс мар 13, 2011 18:11:55 --

Руст в сообщении #422496 писал(а):

Уравнение $ax-by=1$ решается алгоритмом Евклида при вычислении $gcd(a,b)$ по этому алгоритму одновременно находятся $x,y$.

Да. А математически записать можно решение в виде формулы?

Можно. Например, так: $x=13^{\varphi(17)-1} \bmod{17}$. Только обычно проку от таких формул мало.

[Sonic86]

Руст писал(а):

Если любое такое число больше некоторого разлагается, то простых вида $n^2+1$ конечное число (это эквивалентное утверждение).

Тогда оно скорее всего неверно...

[age]

Попробовал найти формулу алгоритма Евклида в явном виде. Получилось нечто вида:
$q_n+1$
$q_{n-1}q_n+1$
$q_{n-2}(q_{n-1}q_n+1)+1$
$q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1$
$q_{n-4}\left(q_{n-3}[q_{n-2}(q_{n-1}q_n+1)+1]+q_{n-1}q_n+1\right)+q_{n-2}(q_{n-1}q_n+1)+1$
............
я даже не знаю как это грамотно скомпоновать
В общем, в следующем шаге последний член будет умножаться на $q_{n-5}$ и к нему будет прибавляться предпоследний. В итоге в самом конце должна получиться некоторая "бериберда", которая возможно как-то "собирается". В любом случае, применять такую формулу для анализа очень нецелесообразно.

где
$q_1=\left[\dfrac ab\right]$, $q_2=\left[\dfrac{b}{a\mod b}\right]$, $q_3=\dfrac{a\mod b}{b-\left[\dfrac{b}{a\mod b}\right]\cdot (a\mod b)}$ ,............, $q_n$
в квадратных скобках указана целая часть числа.
Для $q_4$ знаменатель из $q_3$ уйдёт в числитель, а знаменатель ещё более усложнится.

Должна быть более простая формула, уж слишком что-то замудрено для такого простого алгоритма, который пишется буквально в три строчки.

-- Вс мар 13, 2011 23:17:07 --

MrDindows в сообщении #422495 писал(а):

$13x\equiv 1 \ mod \ 17 $
Пфф, а вобще не так)
Надо выразить $x$ через $y$.
$x=\frac{17y+1}{13}=y+\frac{4y+1}{13} $
Значит $\frac{4y+1}{13}=z, \ z \in Z$
Откуда выражается $y$:
$y=\frac{13z-1}{4}=3z+\frac{z-1}{4} $
$\frac{z-1}{4}$ - Тоже должно быть целым, значит $z=4k+1$.
И возвращаем всё это в начальные переменные.
$y=3z+k=13k+3$
$x=y+z=17k+4$

Ну это вы переписали тот же алгоритм Евклида: остаток, потом остаток на остаток и т.д. Если числа будут большие то рассуждение пропорционально вырастет.

-- Вс мар 13, 2011 23:24:45 --

nnosipov в сообщении #422584 писал(а):

Можно. Например, так: $x=13^{\varphi(17)-1} \bmod{17}$. Только обычно проку от таких формул мало.

Спасибо. Насколько я понимаю $\varphi(17)$ - это функция Эйлера? Формула необходима для анализа некоего выражения, поэтому желательно всё же чтобы ей можно было как-то манипулировать.
Если ваша формула верна, необходимо доказать, что всякое целое число $n>\varepsilon$ можно представить:

$n=a\left(b^{\varphi(a)-1} \bmod{a}\right)+b\left(a^{\varphi(b)-1} \bmod{b}\right)+k(a^2+b^2)$.

здесь $a,b,k$ - любые целые числа.
Либо показать те целые числа, которые такой формой не представимы.

[age]

да, проверил на wolframalpha всё здорово работает! Только надо немного переписать формулу.

$n=a\left(a-b^{\varphi(a)-1}\bmod{a}\right)+b\left(a^{\varphi(b)-1} \bmod{b}\right)+k(a^2+b^2)$.

[age]

Опять неверно записал. Ещё раз:

$n=k(a^2+b^2)\pm\left[a\left(a-b^{\varphi(a)-1}\bmod{a}\right)+b\left(a^{\varphi(b)-1} \bmod{b}\right)\right]$.

теперь, если положить, что $b=1$, то получим:

$n=k(a^2+1)\pm a(a-1)$.

этой формой можно представить абсолютно любое целое ??? ниччего не пойму. Бред получается.

-- Пн мар 14, 2011 01:46:29 --

неверно. Нельзя положить $b=1$, тогда формула для $x_0,y_0$ даёт результат $(0,1)$ для абсолютно любых $a$. Видимо, таковая особенность формулы. Положим, $b=2$:

$n=k(a^2+4)\pm\left[a\left(a-2^{\varphi(a)-1}\bmod{a}\right)+2\right]$.

И для $b=3$:

$n=k(a^2+9)\pm\left[a\left(a-3^{\varphi(a)-1}\bmod{a}\right)+3\left(a\bmod{3}\right)\right]$.

[age]

Первое из этих уравнений можно переписать:

$k(a^2+4)\pm(ma+2)$, $m<a$

Второе:

$k(a^2+9)\pm(ma+3t)$, $m<a$, где $t=0,1,2$.

При этом $m$ зависит от $a$, т.е. для каждого $a$ есть только одно $m$. Очевидно, что далеко не всякое целое число можно так представить.

-- Пн мар 14, 2011 02:14:31 --

Нда-с, с функцией Эйлера далеко не уедешь. Попробую поискать другое решение линейного диофантова уравнения $ax-by=1$.