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

[student]

Натуральное число $N$ имеет ровно 12 делителей (включая 1 и $N$). Занумеруем их в порядке возрастания: $d_1<d_2<\ldots < d_{12}$
Известно, что делитель с номером$d_4-1$равен произведению $(d_1+d_2+d_3+d_4)d_8$. Найдите $N.$

[maxal]

student писал(а):

Натуральное число $N$ имеет ровно 12 делителей (включая 1 и $N$). Занумеруем их в порядке возрастания: $d_1<d_2<\ldots < d_{12}$
Известно, что делитель с номером$d_4-1$равен произведению $(d_1+d_2+d_3+d_4)d_8$. Найдите $N.$

Заметим, что $N$ не является полным квадратом и для любого $1\leq k\leq 12$ выполняется $d_k\cdot d_{13-k}=N$.
Так как $(d_1+d_2+d_3+d_4)d_8$ является делителем $N$, то
$N = d_5\cdot d_8 \geq (d_1+d_2+d_3+d_4)d_8 > d_4 d_8.$
Откуда заключаем, что $d_1+d_2+d_3+d_4=d_5$ и $d_4-1 = 12$, а значит $d_4=13$.

Так как число делителей N равно 12, то N имеем вид: $pqr^2$, $pq^5$, $p^2q^3$ или $p^{11}$, где $p, q, r$ - различные простые, одно из которых равно $13$.

Понятно, что случай $p^{11}$ невозможен.

Если $N$ содержит ровно 2 различных простых делителя, то с необходимостью имеем:
i) $d_1=1,\ d_2=3,\ d_3=9$ и $d_5 = 1 + 3 + 9 + 13 = 26 = 2\cdot 13$, а значит $d_2=2$, противоречие.
или
ii) $d_1=1,\ d_2=2,\ d_3=4$ и степень двойки в разложении $N$ равна 2. В этом случае $d_5 = 1 + 2 + 4 + 13 = 20 = 2^2 5$, а значит $d_4=5$, противоречие.

Если же $N$ имеет вид $p q r^2$, где $p,q,r$ - различные простые. Случаи $r=2$ и $r=3$ по сути рассмотрены выше. Если же $r\geq 5$, то 13 обязано быть наибольшим простым делителем $N$. В этом случае небольшим перебором убеждаемся, что искомого $N$ в таком виде не существует:

? test(N)=d=divisors(N);if(sum(i=1,4,d[i])==d[5],print(N))
? forprime(p=2,11,forprime(q=p+1,11,test(p*q*13^2);test(p*q^2*13);test(p^2*q*13)))

UPDATE: Похоже, это была ошибочная формулировка задачи http://www.mathlinks.ro/viewtopic.php?t=22001, которая в отличие от данной имеет решения.

[ИСН]

Делитель номер $d_4-1$ больше восьмого, да хорошо так больше, раз в десять минимум. Однако это делитель. Какой? Варианты: 9-й, 10-й, 11-й, или само N. Соответственно, варианты для самого d_4: 10, 11, 12, 13.
12 отпадает, до него шли бы 1, 2, 3, 4 и 6.
10 - вперёд него идут 1, 2 и 5, тогда этот Неизвестный (Но Большой) делился бы на 1+2+5+10=18, тогда есть ещё делитель 3, тогда 10 - не четвёртый. Мимо.
Думаю дальше...

Добавлено спустя 37 секунд:

Опередили, бросил думать своё, читаю Ваше...

[student]

Известно, что $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$.

[Руст]

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

[student]

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

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

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

[Руст]

Можно школьными методами доказать, но это по сути завуалированное доказательство факториальности кольца Гауссовских чисел и получается громоздко.

[student]

Руст!
А если возмем $a=z, b=1, c=1, d=0$ не ошибаемся? Поскольку в условие задачи сказано что $a,b,c,d$- целые числа!

[TOTAL]

student писал(а):

Известно, что $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$.

Индукция:
$(z+x)^2+1=x(y+2z+x)$
$x=a^2+b^2$
$y+2z+x=(a+c)^2+(b+d)^2$

[student]

Найдите все пары $(n,p)$ неотрицательных целых чисел такие, что
1. $p$-простое число,
2. $n<2p$
3. $(p-1)^n+1\equiv 0(\mod n^{p-1})$.

[maxal]

student писал(а):

Найдите все пары $(n,p)$ неотрицательных целых чисел такие, что
1. $p$-простое число,
2. $n<2p$
3. $(p-1)^n+1\equiv 0(\mod n^{p-1})$.

Пусть $q$ - наименьший простой делитель $n$. Тогда $(p-1)^n\equiv -1\pmod{q}$, то есть $\mathop{ord}_q(p-1)<q$ делит $2n$. В виду минимальности $q$ имеем $\mathop{ord}_q(p-1)=1$ или $\mathop{ord}_q(p-1)=2$. Откуда либо $q|(p-2)$, либо $q=p$. Рассмотрим эти случаи:
Если $q=p$, то неравенство $n<2p$ влечет $n=p$ и $(p-1)^p +1\equiv 0\pmod{p^{p-1}}$. Нетрудно видеть, что $(p-1)^p +1$ для $p>2$ делится на $p^2$, но не на $p^3$, и поэтому $p\leq 3$. Получем решения $n=p=2$ и $n=p=3$.
Если $q|(p-2)$, то $-1\equiv (p-1)^n\equiv 1\pmod{q}$, что влечет $q=p=2$ - случай рассмотренный выше.

[student]

maxal писал(а):

Пусть $q$ - наименьший простой делитель $n$. Тогда $(p-1)^n\equiv -1\pmod{q}$, то есть $\mathop{ord}_q(p-1)<q$ делит $2n$. В виду минимальности $q$ имеем $\mathop{ord}_q(p-1)=1$ или $\mathop{ord}_q(p-1)=2$. Откуда либо $q|(p-2)$, либо $q=p$.

Что то не понял! Что значит $ord_q(n)$?

[maxal]

student писал(а):

Что значит $ord_q(n)$?

Мультипликативный порядок $n$ по модулю $q$, то есть такое минимальное натуральное число $k$, что $n^k\equiv 1\pmod{q}$.

[student]

Найдите натуральное число $n\in (100,2007)$, такое что $n|2^n+2$.

[maxal]

student писал(а):

Найдите натуральное число $n\in (100,2007)$, такое что $n|2^n+2$.

Этот тип задач и методы решения уже обсуждали в viewtopic.php?t=4786
По поводу этой конкретной - см. также A006517.