2014 dxdy logo

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

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




 
 арифметические прогрессии, общие члены
Сообщение22.09.2008, 04:23 
Дано $n$ арифметических прогрессий, бесконечных в обе стороны. У каждых двух из них имеется общий член (у каждой пары, вообще говоря, свой). Доказать, что и у всех одновременно прогрессий есть общий член.
Доказательство желательнго сделать по индукции: предполагая, что утверждение верно для $n-1$ последовательностей, обозначим общий член $n-1$ первых последовательностей $A$. Затем вычтем из каждого члена всех $n$ последовательностей число $A$. Остаётся доказать, что в новой $n$-ной последовательности содержится член, кратный наименьшему общему кратному разностей первых $n-1$ последовательностей. А вот как это сделать коротко и просто? У меня не получается.

 
 
 
 Re: арифметические прогрессии
Сообщение22.09.2008, 05:36 
Аватара пользователя
Докажите и воспользуйтесь тем, что для любых двух элементов целочисленной арифметической прогрессии существует элемент этой же прогрессии, являющийся кратным их обоих.

А для нецелочисленных прогрессий ваше утверждение, вообще говоря, не верно - контрпример из трех прогрессий:
$x_i= i$
$y_i = \pi\cdot i$
$z_i = 1 + (\pi - 1)\cdot i$.

 
 
 
 
Сообщение22.09.2008, 06:09 
Аватара пользователя
А бесконечная в "обе стороны" прогрессия --- это множество вида

$$
\{ x + zd : z \in \mathbb{Z} \}
$$

с фиксированными $x$ и $d \neq 0$? Вероятно, да, хотя я первый раз встречаюсь с такой терминологией.

С другой стороны, вероятно, всё же нет. Ибо если да, то утверждение, которое требуется доказать, просто неверно.

...

На месте многоточия было доказательство, но когда я его написал, то увидел, что maxal меня опередил.

Короче, уточняйте условие!!!

 
 
 
 
Сообщение22.09.2008, 12:56 
Извините, не заметил, что не указал свойство йелочисленности прогресий. А вид они имеют Профессор Снэйп такой, как Вы предположили.

 
 
 
 
Сообщение22.09.2008, 17:31 
Спасибо, доказал лемму о том, что для любых двух элементов целочисленной арифметической прогрессии существует элемент этой же прогрессии, являющийся кратным их обоих, а из этого совсем просто последовало всё, что нужно. Но доказательство леммы оказалось довольно громоздким. Может, есть короткие способы?

 
 
 
 
Сообщение22.09.2008, 21:57 
Аватара пользователя
lexus c. писал(а):
Спасибо, доказал лемму о том, что для любых двух элементов целочисленной арифметической прогрессии существует элемент этой же прогрессии, являющийся кратным их обоих, а из этого совсем просто последовало всё, что нужно. Но доказательство леммы оказалось довольно громоздким. Может, есть короткие способы?

Пусть $x$ и $y$ - это элементы прогрессии. Без потери общности можно считать, что наша прогрессия имеет вид $x+n(y-x)=d(ny'-(n-1)x')$, где $d=\gcd(x,y),\ x'=x/d,\ y'=y/d$ и поэтому $\gcd(x',y')=1$. Тогда по китайской теореме об остатках система сравнений
$$\begin{cases} n\equiv 0\pmod{x'}\\ n\equiv 1\pmod{y'}\end{cases}$$
имеет решение $n=n_0$. Тогда $x+n_0(y-x)$ - искомый элемент прогрессии, который делится как на $x$, так и на $y$.

 
 
 
 
Сообщение23.09.2008, 01:01 
maxal писал(а):
lexus c. писал(а):
Спасибо, доказал лемму о том, что для любых двух элементов целочисленной арифметической прогрессии существует элемент этой же прогрессии, являющийся кратным их обоих, а из этого совсем просто последовало всё, что нужно. Но доказательство леммы оказалось довольно громоздким. Может, есть короткие способы?

Пусть $x$ и $y$ - это элементы прогрессии. Без потери общности можно считать, что наша прогрессия имеет вид $x+n(y-x)=d(ny'-(n-1)x')$, где $d=\gcd(x,y),\ x'=x/d,\ y'=y/d$ и поэтому $\gcd(x',y')=1$. Тогда по китайской теореме об остатках система сравнений
$$\begin{cases} n\equiv 0\pmod{x'}\\ n\equiv 1\pmod{y'}\end{cases}$$
имеет решение $n=n_0$. Тогда $x+n_0(y-x)$ - искомый элемент прогрессии, который делится как на $x$, так и на $y$.

Ясно, спасибо )

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group