В целых числах

[ИСН]

Ну, попробуйте по индукции, хотя я к тому не вижу никаких оснований.
Но лучше так. Какой множитель стопудово, наверняка есть?

[Keter]

Shadow, не просто так Вы дали эту задачку Я понял, тут нужно ограничить, по аналогии с уравнением.
Множитель 2

ИСН в сообщении #652459 писал(а):

стопудово, наверняка есть.

Значит нужно доказать, что если $2n=p_1+p_2$, то $n$ составное. $p_1, p_2$ - последовательные простые, больше 2.

Тогдо выполняется неравенство $p_1 < \dfrac{p_1+p_2}{2} < p_2$, то есть $p_1<n<p_2$. Получается, что какое-то натуральное число зажато между последовательными простыми, которые больше двух, значит оно составное однозначно.
Вот и получаем еще как минимум два множителя. Итого три.

-- 01.12.2012, 16:17 --

(Оффтоп)

А вот еще вопрос по ходу. Новую тему создавать не хочется.

Найти все натуральные $n$ при которых дробь $\dfrac{7n+2}{3n+1}$ можно сократить.

Как это зависит от дроби? $\dfrac{4n+3}{20n+23}$, $\dfrac{11n+8}{7n+3}$, $\dfrac{16n+1}{40n+2}$

Как решаются такие штуки?

[Shadow]

Правильно Кетер

Keter в сообщении #652463 писал(а):

Как это зависит от дроби

Вы знаете алгоритм Евклида...для нахождения НОД двух чисел.

[Keter]

Shadow, не знаю.

[Keter]

Shadow в сообщении #652476 писал(а):

алгоритм Евклида

Как его здесь использовать? Беру я дробь $\dfrac{4n+3}{20n+23}$. И записываю, что $4n+3=\frac{1}{5}(20n+23)-\frac{8}{5}$, $20n+23=(\frac{25n}{2}+\frac{23 \cdot 5}{8}) \cdot \frac{8}{5}+0.$ И в чем смысл?
$\text{НОД}(4n+3; 20n+23)=\frac{100n+115}{8}$. То есть дробь $\frac{4n+3}{20n+23}$ несократима так как $\frac{100n+115}{8}$ не может быть целым числом: числитель - нечетное, знаменатель - четное.

[ИСН]

Это Вы что сделали и зачем? Прочитайте где-нибудь про алгоритм Евклида, ну.

[Keter]

ИСН, я прочитал...

$\text{НОД}(a; b)$
$a=bq+r, b=rq_1+r_1, ..., r_{n-1}=r_n q_{n+1}+0$
$\text{НОД}(a; b)=\text{НОД}(b; r)=...=\text{НОД}(r_{n-1}; r_n)=r_n$

Ну и попытался найти. Но я не понял в чем смысл. Зачем его искать, что мне это даст? По идеи, найдя НОД числителя и знаменателя, ну допустим я получу выражение $\dfrac{3n+1}{5}$, я должен сказать, что данная там какая-то дробь сокращается, когда число $\dfrac{3n+1}{5}$ целое. Или нет?

[ИСН]

Как-то так, да.

[Keter]

Наверное я неправильно нахожу НОД. Открываю книгу, читаю пример:

$\gcd(30n+2, 12n+1)=\gcd(6n, 12n+1)=\gcd(6n, 1)=1$

Вообще не понял, как они находят этот $\gcd$? Почему $\gcd(30n+2, 12n+1)=\gcd(6n, 12n+1)$, например? И дальше не понятно.

Пытаюсь по аналогии: $\gcd(20n+23, 4n+3)=\gcd(4n, 4n+3)=\gcd(4n, 3)=...$. Что дальше?

ИСН в сообщении #652655 писал(а):

Как-то так, да.

Но если как-то так, тогда как найти $n$, при которых сокращается дробь $\frac{11n+4}{7n+3}$ ?

$\gcd(11n+4, 7n+3)=\gcd(n, 7n+3)=\gcd(n, 3)=...$

[ИСН]

Они этот gcd находят по алгоритму Евклида, а Вы как? Вы первый шаг какой делаете? Сколько раз "меньшее" содержится в "большем"? Вычитаем его из него, и...

[Keter]

$\frac{11n+8}{7n+3}$

$11n+8=\frac{11}{7}(7n+3)+\frac{23}{7}$

$7n+3=(\frac{49n+21}{23})\frac{23}{7}+0$

$\gcd(11n+8, 7n+3)=\frac{49n+21}{23}$

Я понял, как был сделан переход $\gcd(30n+2, 12n+1)=\gcd(6n, 12n+1)$, тут дважды воспользовались тем, что $\gcd(a, b)=\gcd(a-b, b)$ при $a>b$. Но дальше...
$\gcd(6n, 12n+1)=\gcd(6n, 1)=1$ Как?

[ИСН]

А тут, если в Ваших терминах, дважды воспользовались тем, что $\gcd(b, a)=\gcd(b, a-b)$.

-- Вс, 2012-12-02, 00:04 --

Чуть не забыл: при $a>b$, конечно.

[Shadow]

Ну, из чисел $6n \text { и } 12n+1$ что больше? Вычитайте из большего меньшее.

[Keter]

понял)

$\gcd(11n+8, 7n+3)=\gcd(4n+5, 7n+3)=\gcd(3n-2, 4n+5)=\gcd(n+7, 3n-2)=...$ не понял

[ИСН]

Что мешает Вам сделать ещё один точно такой же шаг, как до этого? Что какие-то числа получаются отрицательными? Так вон уже на втором шаге одно такое получилось. Или "-2" - это ещё ладно, не считается, а вот дальше уже страшно?