Доказать истинность, простое число.

[Tosha]

Помогите, плиз, разобраться с задами.
1) Доказать истинность:
$A(n)=\{\text{число}\;\;5\cdot 2^{3n-2}+3^{3n-1}\;\;\text{кратно}\;\;19\},\;n\in\mathbb{N}$

Индукция. База $n=1$ выполняется.

Переход. Предположим, что $A(n)$ истинно, проверим, будет ли тогда истинно $A(n+1)$?

$A(n+1)=\{\text{число}\;\;5\cdot 2^{3n+1}+3^{3n+2}\;\;\text{кратно}\;\;19\},\;n\in\mathbb{N}$

А как дальше?

2) Доказать, что для делимости $n^2-1$ на 24 необходимо и достаточно, чтобы $n$ было простым числом.

С чего тут начать? Проверил для $n=5,7,11$, тут сходится.

[Someone]

Tosha в сообщении #762339 писал(а):

2) Доказать, что для делимости $n^2-1$ на 24 необходимо и достаточно, чтобы $n$ было простым числом.

Неверно. Простота $n$ не является ни необходимой, ни достаточной. Попробуйте, например, $n=3$ и $n=25$.

Tosha в сообщении #762339 писал(а):

Помогите, плиз, разобраться с задами.
1) Доказать истинность:
$A(n)=\{\text{число}\;\;5\cdot 2^{3n-2}+3^{3n-1}\;\;\text{кратно}\;\;19\},\;n\in\mathbb{N}$

Индукция. База $n=1$ выполняется.

Переход. Предположим, что $A(n)$ истинно, проверим, будет ли тогда истинно $A(n+1)$?

$A(n+1)=\{\text{число}\;\;5\cdot 2^{3n+1}+3^{3n+2}\;\;\text{кратно}\;\;19\},\;n\in\mathbb{N}$

А как дальше?

Поделите второе число на первое.

[Tosha]

Someone в сообщении #762341 писал(а):

Неверно. Простота $n$ не является ни необходимой, ни достаточной. Попробуйте, например, $n=3$ и $n=25$.

Спасибо. Виноват, забыл написать, что $n\geqslant 5$. При $n\geqslant 5$ будет хотя бы "необходимо"? Понял, что достаточно уже не будет, так как контрпример $n=25$.

[_Ivana]

Осталось понять суть терминов "необходимо" и "достаточно" (как в математическом, так и в бытовом понимании), и можно будет двигаться дальше.

[vorvalm]

Простые числа, кроме 2 и 3, из классов $n=6k\pm1$
Возведите в квадрат и отнимите 1.

[Tosha]

Someone в сообщении #762341 писал(а):

Поделите второе число на первое.

Не вижу, чтобы сокращалось(

$\dfrac{5\cdot 2^{3n+1}+3^{3n+2}}{5\cdot 2^{3n-2}+3^{3n-1}}=\dfrac{40\cdot 2^{3n-2}+27\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}$

-- 10.09.2013, 14:00 --

_Ivana в сообщении #762361 писал(а):

Осталось понять суть терминов "необходимо" и "достаточно" (как в математическом, так и в бытовом понимании), и можно будет двигаться дальше.

Необходимо.
Из того, что $n$ -- простое следует истинность $A(n)$
Достаточно.
Из того, что $A(n)$ -- истинно, следует, что $n$ -- простое.
Я так понимаю.

Достаточно уже опровергнуто контрпримером $n=25$.

[provincialka]

Tosha в сообщении #762368 писал(а):

Необходимо.
Из того, что $n$ -- простое следует истинность $A(n)$
Достаточно.
Из того, что $A(n)$ -- истинно, следует, что $n$ -- простое.
Я так понимаю.

Достаточно уже опровергнуто контрпримером $n=25$.

Все наоборот.

-- 10.09.2013, 17:28 --

Tosha в сообщении #762368 писал(а):

Не вижу, чтобы сокращалось(

$\dfrac{5\cdot 2^{3n+1}+3^{3n+2}}{5\cdot 2^{3n-2}+3^{3n-1}}=\dfrac{40\cdot 2^{3n-2}+27\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}$

А Вы с остатком поделите.

[Tosha]

provincialka в сообщении #762476 писал(а):

[quote="Tosha в

Все наоборот.

А Вы с остатком поделите.

Да, действительно, наоборот. А как доказать хотя бы в одну сторону?

-- 10.09.2013, 21:07 --

С остатком:

$\dfrac{5\cdot 2^{3n+1}+3^{3n+2}}{5\cdot 2^{3n-2}+3^{3n-1}}=\dfrac{40\cdot 2^{3n-2}+27\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}=\dfrac{40\cdot 2^{3n-2}+8\cdot 3^{3n-1}+19\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}=$

$=\dfrac{8(5\cdot 2^{3n-2}+3^{3n-1})+19\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}=8+\dfrac{19\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}$

[provincialka]

Ну и? Что это дает? Как можно выразить $n+1$-ое число через $n$-ое?
Заметьте, число 19 уже появилось!

[Someone]

Tosha в сообщении #762580 писал(а):

Да, действительно, наоборот. А как доказать хотя бы в одну сторону?

http://dxdy.ru/post762367.html#p762367

[sergei1961]

Так как числа 12 и 19 взаимно простые, а также $27=8\mod 19$, то

$$ 5\cdot 2^{3n-2}+3^{3n-1}\mod(19)=12(5\cdot 2^{3n-2}+3^{3n-1})\mod(19)= $$ $$ 15\cdot 2^{3n}+4\cdot3^{3n}\mod(19)=15\cdot 8^n+4\cdot 8^n\mod(19)=19\cdot 8^n\mod(19)=0\mod 19. $$

[provincialka]

Ну вот, sergei1961. Мы нашего Tosha тянули-тянули к решению, а Вы - бац - и все выложили!

[Tosha]

provincialka в сообщении #762593 писал(а):

Ну и? Что это дает? Как можно выразить $n+1$-ое число через $n$-ое?
Заметьте, число 19 уже появилось!

Спасибо, кажется, что понятно.

$\dfrac{5\cdot 2^{3n+1}+3^{3n+2}}{5\cdot 2^{3n-2}+3^{3n-1}}=8+\dfrac{19\cdot 3^{3n-1}}{5\cdot 2^{3n-2}+3^{3n-1}}$

Пусть $L(n)=5\cdot 2^{3n-2}+3^{3n-1}$

$\dfrac{L(n+1)}{L(n)}=8+\dfrac{19\cdot 3^{3n-1}}{L(n)}$

$L(n+1)=8L(n)+19\cdot 3^{3n-1}$

По предположению индукции $L(n)$ делится на $19$. Тогда пусть $L(n)=19\cdot M(n)$

$L(n+1)=19L(n)+19\cdot 3^{3n-1}=8\cdot 19\cdot M(n)+19\cdot 3^{3n-1}=19(8M(n)+3^{3n-1})$

Из этого следует, что $L(n+1)$ делится на 19. Можно ли так?

-- 11.09.2013, 01:44 --

vorvalm в сообщении #762367 писал(а):

Простые числа, кроме 2 и 3, из классов $n=6k\pm1$
Возведите в квадрат и отнимите 1.

Спасибо.

1) $(6k+1)^2-1=36k^2+12k=12k(3k+1)$

a) $k=2p$

$12k(3k+1)=24p(6p+1)$ делится на $24$

b) $k=2p+1$

$12k(3k+1)=12(2p+1)(6p+4)=24(2p+1)(3p+2)$ делится на $24$

2) $(6k-1)^2-1=36k^2-12k=12k(3k-1)$

Аналогично, только другой знак.

А как быть с простыми числами из других классов? Все ли числа вида $6k\pm 1$ являются простыми?

[Someone]

Tosha в сообщении #762688 писал(а):

А как быть с простыми числами из других классов?

А "из других классов" — это только $2$ и $3$. Подумайте сами, почему. Там всё очевидно сразу, надо только написать вид чисел каждого класса.

Tosha в сообщении #762688 писал(а):

Все ли числа вида $6k\pm 1$ являются простыми?

Разумеется, нет. Опять же, контрпримеры подберите сами, они небольшие и за минуту подбираются устно.

Tosha в сообщении #762688 писал(а):

По предположению индукции $L(n)$ делится на $19$. Тогда пусть $L(n)=19\cdot M(n)$

$L(n+1)=19L(n)+19\cdot 3^{3n-1}=8\cdot 19\cdot M(n)+19\cdot 3^{3n-1}=19(8M(n)+3^{3n-1})$

Из этого следует, что $L(n+1)$ делится на 19. Можно ли так?

Можно. Только опечатку исправьте.

[Tosha]

Someone в сообщении #762693 писал(а):

А "из других классов" — это только $2$ и $3$. Подумайте сами, почему. Там всё очевидно сразу, надо только написать вид чисел каждого класса.

Да, действительно, выписал, эти числа не будут простыми заведомо.

$6k$ делится на 6. $6k+2$ делится на 2. $6k+3$ делится на 3. $6k+4$ делится на 2.

Someone в сообщении #762693 писал(а):

Tosha в сообщении #762688 писал(а):

Все ли числа вида $6k\pm 1$ являются простыми?

Разумеется, нет. Опять же, контрпримеры подберите сами, они небольшие и за минуту подбираются устно.

При $k=11$ число $6k-1$ не будет простым.

Необходимо.
Из того, что $A(n)$ -- истинно, следует, что $n$ -- простое.
Не выполняется необходимость. Контрпример $n=25$
Достаточно.
Из того, что $n\geqslant 5$ -- простое следует истинность $A(n)$
Вот тут пока что мне не очевидно. Но есть предположение. Все простые числа, большие $n\ge 5$, представимы в виде $n=6k\pm 1$. Ну а для $n=6k\pm 1$ у меня уже получилось доказать делимость на 24. Верно?

Someone в сообщении #762693 писал(а):

Можно. Только опечатку исправьте.

$L(n+1)=8L(n)+19\cdot 3^{3n-1}=8\cdot 19\cdot M(n)+19\cdot 3^{3n-1}=19(8M(n)+3^{3n-1})$