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

[student]

Пусть $m,n$ натуральные числа, такие что число $A=\frac{(m+3)^n+1}{3m}$ -целое.Докажите что $A$-нечетное число.

[maxal]

Надо заметить, что m является делителем $3^n+1$, а потому может делиться максимум на $2^2$. Далее рассматриваем случаи:

$m=2k+1$ и $m=4k+2$ - тривиальны.

Если $m=8k+4$, то $n$ - нечетно. Заметим, что если $p$ - нечетный простой делитель числа $3^n+1$, то $-3$ является квадратом по модулю $p$, а поэтому $p$ имеет вид $p=3t+1$ и, следовательно, $m\equiv 1\pmod 3$. Но в этом случае $A$ не является целым.

[student]

Пусть $f(x)=x^3+17.$ Докажите, что для каждого натурального числа $n\geq 2$ можно найти натурального $x$ для которой $f(x)$делится на $3^n$ но не делится на $3^{n+1}.$

[maxal]

student писал(а):

Пусть $f(x)=x^3+17.$ Докажите, что для каждого натурального числа $n\geq 2$ можно найти натурального $x$ для которой $f(x)$делится на $3^n$ но не делится на $3^{n+1}.$

Индукция по $n$. Для $n=2$ можно взять $x=1$, а для $n=3$ можно взять $x=13$.
Пусть требуемое $x$ существует для $n=m>2$. Докажем, что оно существует и для $n=m+1$. Будем искать новое $x$ в виде $x'=3^{m-1}y + x$, где $y$ нам предстоит определить. При этом
$3^{m+1} | f(x') = 3^{3m-3} y^3 + 3^{2m-1} y^2 x + 3^m y x^2 + x^3 + 17$
и
$3^{m+2} \not| f(x') = 3^{3m-3} y^3 + 3^{2m-1} y^2 x + 3^m y x^2 + x^3 + 17$
эквивалетнны
$3 | y x^2 + \frac{x^3 + 17}{3^m}$ и $3^2 \not| y x^2 + \frac{x^3 + 17}{3^m}$, которые очевидно имеют решение $y\in\{1,2,4,5\}$.
чтд.

[student]

Найдите всех натуральных $n$для которых существует некоторое целое $m$ такое, что $m^2+9$ делится на $2^n-1$

[maxal]

student писал(а):

Найдите всех натуральных $n$для которых существует некоторое целое $m$ такое, что $m^2+9$ делится на $2^n-1$

Только $n=1$. Для $n>1$ сравнение $m^2\equiv -9\pmod{2^n-1}$ не имеет решений (достаточно вычислить символ Якоби).

[Руст]

n=2 $2^2-1=3|3^2+9$.

[maxal]

Да, забыл про делимость на 3. В общем, если $2^n - 1$ делится на 3, но не на 9 (то есть когда $n$ делится на 2, но не на 3), то сравнение сводится к $m'^2 = -1\pmod{\frac{2^n-1}{3}}$, которое только через символ Якоби не разрешить. Это сравнение имеет решение только, если простые делители входящие в разложение $\frac{2^n-1}{3}$ имеют вид $4k+1$. Например, для $n=2, 4, 8$ решения есть, а для $n=10$ - нет.

[Руст]

Очевидно, что решениями являются все числа $n=2^k$ и только они (иначе появится делитель числа $2^n-1$ вида 4k+3 отличное от 3. При этом не важно в чётной степени или в нечётной оно входит в разложение.

[student]

Докажите, что если $p>3$- простое число и $k=\Bigl[\frac{2p}{3}\Bigr]$, то $C_{p}^{1}+C_{p}^{2}+\cdots + C_{p}^{k}\equiv 0 (\mod p^2)$

[Руст]

Это задача встречалась и в Mathlinks и нескоько в другом виде здесь на форуме. Достаточно заметить, что $C_p^m=\frac{p}{m}\mod p^2.$

[maxal]

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

Достаточно заметить, что $C_p^m=\frac{p}{m}\mod p^2.$

Ты знак потерял: $C_p^m\equiv(-1)^{m-1}\frac{p}{m}\pmod{p^2}.$

[Руст]

Да верно, что делает задачу более тривиальной (не требуется обращаться к суммам степеней по неполным вычетам, которые я здесь как то приводил) а приводит к сумме с одним знаком по всем чётным.

[student]

Найдите наибольший общий делитель элементов множества $\{ n^{13}-n \; \vert n\in \mathbb{Z}\}$.

[Руст]

Если (p-1) делит 12, то это число делится на p в первой степени, т.е. это число делится на 2*3*5*7*13. Легко показать, что общий делитель не делится на большее число.