Задачи по теории делимости.

[student]

Известно, что при $n\in\mathbb{N}$ $4^n+2^n+1$-- простое число. Докажите что $n=3^k, k\in \mathbb{N}.$

[Руст]

Это легко получается из двух соотношений $4^n+2^n+1=\frac{2^{3n}-1}{2^n-1}$ и
$gcd(2^n-1,2^m-1)=2^{gcd(m,n)}-1.$

[student]

Пусть $b, m, n\in \mathbb{N},\ \ b>1,$ $m\ne n$.
Предположим, что $b^m-1$ и $b^n-1$-- имеют одинаковое множество простых делителей. Покажите, что $b+1$- является степенем 2.

[Руст]

Пусть b=2, m,n такие простые числа, что $2^m-1,2^n-1$ так же простые (простые Мерсена) они имеют единственный простой делитель. А число 2+1 не является степенью двойки.

[student]

Ах да конечно!
Я ошибся! Вместо "количество" должно быт "множество"!

[Руст]

Пусть p простое число, являющееся делителем b^n-1, Тогда p не делит b, и для любого такого p, существует минимальный период T(p), что b^n-1 делится на p, тогда и только тогда, когда n делится на T(p). Если n нечётно, то b^n-1 содержит новый простой делитель, отличный от делителей b^d-1 для всех делителей d. Это верно и для чётных n, за исключением случая, когда (n>m) n=2m и b^m+1 является степенью двойки. Поэтому все исключения есть n=2m и $b^m+1=2^k$ единственным решением которой является m=1, (соответственно n=2) и b=2^k-1.

[maxal]

student писал(а):

Пусть $b, m, n\in \mathbb{N},\ \ b>1,$ $m\ne n$.
Предположим, что $b^m-1$ и $b^n-1$-- имеют одинаковое множество простых делителей. Покажите, что $b+1$- является степенем 2.

Прямое следствие теоремы Зигмонда.

[student]

Пусть $p(n)$-- наибольший простой делитель $n$ при $n>1.$ Докажите, что существует бесконечное число натуральных $n$
для которых $p(n)<p(n+1)<p(n+2).$

[Руст]

Если не ошибаюсь, эта задача из Mathlinks. Там предлагают $n=2^k$. Правда для обоснования такого решения нужно показать, что функция $f(k)=p(2^k+1)$ не является (нестрого) монотонно растущей начиная с некоторого k.
По моему проще расмотреть числа вида $n=kp-1,n+1=kp,n+2=kp+1,k=1,2,..,p$ и показать, что всегда существует такое k из этого множества.

[student]

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

По моему проще расмотреть числа вида $n=kp-1,n+1=kp,n+2=kp+1,k=1,2,..,p$ и показать, что всегда существует такое k из этого множества.

Как? Можно поподробнее? Я не смог показать.

[Руст]

Вообще то несложно с помощью подсчёта произведения всех делителей чисел kp+1,k=1,2,...,p показать, что хотя бы для одного p(kp+1)>p. Но показать, что при этом p(kp-1)<p усложняет ситуацию. Поэтому дам другое доказательство. Очевидно, что существует бесконечно много таких х, что p(x)>p(x-1). Если для такого х выполняется, что p(x+1)>p(x), то доказывать ничего. Иначе рассмотрим числа $p_k=p(x^{2^k}+1)$. Так как $p_k>2^k$ при k>0, то ситуация $p_k<p(x)$ для всех k невозможна. Поэтому, существует такое k, что $p_0<p(x),p_1<p(x),...,p_{k-1}<p(x),p_k>p(x)$. Тогда $n=x^{2^k}-1$ удовлетворяет всем требованиям $p(n)<p(n+1)=p(x)<p(n+2)$.

[student]

Шестизначное число, записанное шестью отличными от нуля разными цифрами, делится на 37. Докажите, что перестановками цифр этого числа можно получить ещё по крайней мере 23 различных чисел делящихся на 37.

[TOTAL]

student писал(а):

Шестизначное число, записанное шестью отличными от нуля разными цифрами, делится на 37. Докажите, что перестановками цифр этого числа можно получить ещё по крайней мере 23 различных чисел делящихся на 37.

Можно первую цифру переставить в конец, вторую поменять местами с пятой, третью - с шестой. Всего 24 варианта.

[student]

TOTAL писал(а):

Можно первую цифру переставить в конец, вторую поменять местами с пятой, третью - с шестой. Всего 24 варианта.

По признаку делимости на 37, если $\overline{a_1a_2a_3a_4a_5a_6}$ делится на 37 то $\overline{a_1a_2a_3}+\overline{a_4a_5a_6}\equiv 0(\mod 37)$
Если вы имеете ввиду перестановку $a_1$ c $a_3$ и $a_2$ с $a_5$
$a_3$ с $a_6$
то получится 7 варианта кроме самого числа!
Еще 16 вариантов получим из чисел $\overline{a_2a_3a_1a_5a_6a_4}$ и $\overline{a_3a_1a_2a_6a_4a_5}$.

[TOTAL]

student писал(а):

TOTAL писал(а):

Можно первую цифру переставить в конец, вторую поменять местами с пятой, третью - с шестой. Всего 24 варианта.

По признаку делимости на 37, если $\overline{a_1a_2a_3a_4a_5a_6}$ делится на 37 то $\overline{a_1a_2a_3}+\overline{a_4a_5a_6}\equiv 0(\mod 37)$
Если вы имеете ввиду перестановку $a_1$ c $a_3$ и $a_2$ с $a_5$
$a_3$ с $a_6$
то получится 7 варианта кроме самого числа!
Еще 16 вариантов получим из чисел $\overline{a_2a_3a_1a_5a_6a_4}$ и $\overline{a_3a_1a_2a_6a_4a_5}$.

Вот 6 вариантов, полученных перестановкой первой цифры в конец:

ABCDEF
BCDEFA
CDEFAB
DEFABC
EFABCD
FABCDE


Из каждого из этих вариантов получается еще 3. Например, вот 4 варианта с первой цифрой A:

ABCDEF
AECDBF
ABFDEC
AEFDBC