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

[student]

Пусть $d_1<d_2<d_3<d_4$- наименьшие 4 делители натурального числа $n$.
Найдите все $n$ для которых $n=d_{1}^2+d_{2}^2+d_{3}^2+d_{4}^2$.

[maxal]

student писал(а):

Пусть $d_1<d_2<d_3<d_4$- наименьшие 4 делители натурального числа $n$.
Найдите все $n$ для которых $n=d_{1}^2+d_{2}^2+d_{3}^2+d_{4}^2$.

Понятно, что $d_1=1$, а также, что $n$ - четно (в противном случае $d_1,d_2, d_3, d_4$ обязаны быть нечетны, а сумма их квадратов - четна, противоречие). Поэтому $d_2=2$ и кроме этого, ровно одно из $d_3$ и $d_4$ также четно. Рассмотрим два варианта:
1) $4|n$. Тогда $\{d_3,d_4\}=\{4,p\}$, где $p\geq 3$ - простое, и $n=1+2^2+4^2+p^2=21+p^2$, откуда $p^2\equiv 3\pmod{4}$, что невозможно.
2) $4\not|n$. Тогда $d_3=p$ и $d_4=2p$, где $p\geq 3$ - простое, и $n=1+2^2+p^2+(2p)^2=5+5p^2$. Откуда $p=5$ и $n=130$ - единственное решение.

[student]

Найдите всех натуральных $x\ne y$ такие, что $x^2+y^3|x^3+y^2$.

[maxal]

student в сообщении #153611 писал(а):

Найдите всех натуральных $x\ne y$ такие, что $x^2+y^3|x^3+y^2$.

Пусть $d=\gcd(x,y)$ и поэтому $x=d\cdot m$ и $y=d\cdot n$, где $\gcd(m,n)=1$. Тогда делимость $(x^2+y^3)|(x^3+y^2)$ равносильна $(m^2+dn^3)|(dm^3+n^2)$.

Легко видеть, что $m^2+dn^3$ делит $dm(m^2+dn^3) - (dm^3+n^2) = n^2(d^2mn - 1)$, а также $dn(dm^3+n^2) - (m^2+dn^3) = m^2(d^2mn-1)$. Поэтому в виду взаимной простоты $m,n$, получаем, что $m^2+dn^3$ делит $d^2mn-1$.

Отсюда, в частности, следует, что $m<d^2n$, $n^2<dm<d^3n$ и поэтому $n<d^3$ и $m<d^5$. То есть, для каждого фиксированного $d$ количество решений конечно. Однако, описать их единой формулой - проблематично.

Вот для примера решения $[d,m,n]$ для $d\leq 100$:

[2, 3, 1]
[7, 9, 1]
[13, 3, 1]
[15, 4, 1]
[17, 4, 1]
[19, 5, 1]
[19, 16, 1]
[22, 137, 2]
[23, 10, 1]
[26, 55, 2]
[27, 2, 1]
[32, 7, 2]
[35, 9, 4]
[40, 9, 1]
[41, 9, 1]
[43, 185, 3]
[44, 41, 3]
[46, 5, 1]
[46, 559, 4]
[60, 253, 6]
[61, 39, 4]
[62, 297, 7]
[63, 193, 3]
[63, 44, 5]
[67, 17, 2]
[73, 53, 1]
[74, 33, 2]
[77, 4, 1]
[77, 67, 1]
[85, 16, 1]
[87, 8, 1]
[89, 144, 5]
[89, 151, 7]
[92, 19, 1]
[97, 68, 5]

[age]

student в сообщении #84084 писал(а):

Известно, что $x,y,z\in \mathbb{N}$ и $xy=z^2+1$. Докажите, что можно найти такие целые $a,b,c,d$ для которых $x=a^2+b^2$ $y=c^2+d^2$ $z=ac+bd$.

student в сообщении #84092 писал(а):

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

это значит, что $z+i=(a+bi)(c-di)$ (кольцо Гауссовских чсел факториально).

В Mathlink-e тоже так сказали, но можно ли решит эту задачу более легким способом понятному простому школьнику? Поскольку эта задача дана в Иранскую олимпиаду школьников 2001 года, а многие школьники врядли знают такие вещи!

$z^2+1=(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2=(ad+bc)^2+(ac-bd)^2$.
Если не существует ни одного $ac+bd\neq z$, $ad-bc\neq1$, что число $A=z^2+1$ может иметь лишь представления $(ac+bd)^2+(ad-bc)^2$ отличные от $z^2+1$, что противоречит условию задачи.
Откуда либо $ad-bc=1$ либо $ac-bd=1$. Случаи полностью аналогичны с точностью до перестановки букв.

[maxal]

Для натурального $n>1$ положим $r=\frac{n^{n-1}-1}{n-1}$. Докажите, что $n^r-1$ делится на $r^2$.

[Руст]

$r=(n-1)m, m=1+\sum_{k=0}^{n-3}\binom{n-1}{k+2}(n-1)^k$.
Так как $n^{n-1}-1=m(n-1)^2$,
$n^r-1=(1+m(n-1)^2)^m-1=r^2[1+\sum_{i=2}^m\binom{m}{i}m^{i-2}(n-1)^{2i-2}].$

[age]

Руст
$r$ не обязательно делится на $n-1$. Например, при $n=3$.

[Руст]

age в сообщении #333047 писал(а):

Руст
$r$ не обязательно делится на $n-1$. Например, при $n=3$.

Делится обязательно.
$r(3)=\frac{3^2-1}{3-1}=4=(n-1)*m,m(3)=2$.

[age]

Ну да.