Сумма делителей делится на 24

[xmaister]

Пусть $n\in\mathbb{N}$. Известно, что $24|n$. Доказать, что сумма всех делителей $n-1$ включая $1$ и $n-1$ делится на 24.

(Попытка)

$n-1$ не делится ни на 2 ни на 3, тогда все делители $n-1$ будут иметь вид $6r\pm 1$. $n-1=24m-1$. Пусть $6r-1$ 1 из делителей $n-1$, тогда $n-1=(6r-1)t$, $t=6r'+1$. Если $t=6r'-1$, то $24m-1=36rr'-6(r+r')+1;$$6l=36rr'-6(r+r')+2;$ $l=6rr'-r-r'+\frac13$, т.е. $l$-не целое. Получаем противоречие. Далее $36rr'+6(r-r')=24m;$ $2r'(3r-1)+(r+r')=4m\Leftrightarrow 2r(3r'+1)-(r+r')=4m$, значит $r+r'$ делится на 4, тогда $6r-1+6r'+1$ делится на 24.

[Sonic86]

xmaister в сообщении #474351 писал(а):

тогда $6r-1+6r'+1$ делится на 24.

В смысле Вы думали, что надо доказать, что если $n-1=d_1d_2$, то $24|d_1+d_2$? Если я правильно понял, то нет, видимо имеется ввиду доказать, что $24| \sigma (n-1)$, где $\sigma (k) = \sum\limits_{d|k} d$ - сумма всех делителей числа.

xmaister в сообщении #474351 писал(а):

Пусть $6r-1$ 1 из делителей $n-1$, тогда $n-1=(6r-1)t$, $t=6r'+1$. Если $t=6r'-1$, то $24m-1=36rr'-6(r+r')+1;$$6l=36rr'-6(r+r')+2;$ $l=6rr'-r-r'+\frac13$, т.е. $l$-не целое.

Я так понял, что это доказательство того, что если $24|n \Leftrightarrow n-1$ имеет вид $24k-1$, то $n-1=n_1n_2$, где $n_1$ имеет вид $6k-1$, а $n_2$ имеет вид $6k+1$? Если да, то это правильно.

[xmaister]

Sonic86 в сообщении #474407 писал(а):

имеется ввиду доказать, что $24| \sigma (n-1)$, где $\sigma (k) = \sum\limits{d|k} d$ - сумма всех делителей числа.

Ну да.

Sonic86 в сообщении #474407 писал(а):

Я так понял, что это доказательство того, что если имеет вид , то , где имеет вид , а имеет вид ? Если да, то это правильно.

А то что $n-1=(6r-1)(6r'+1)\Rightarrow 24|[6(r+r')]$ я не правильно доказал?

-- 09.08.2011, 13:08 --

Что-то я запутался...
Разве из того, что $n-1=(6r-1)(6r'+1)$ и $24|[6(r+r')]$ не следует $24|\left(\sum\limits_{i}d_i\right)$?

[Sonic86]

Ой! Я исправил свою формулу
(в FireFox формулы копируются )

xmaister в сообщении #474419 писал(а):

А то что $n-1=(6r-1)(6r'+1)\Rightarrow 24|[6(r+r')]$ я не правильно доказал?

Это как раз правильно. Мне просто показалось, что я не понял.

xmaister в сообщении #474419 писал(а):

Разве из того, что $n-1=(6r-1)(6r'+1)$ и $24|[6(r+r')]$ не следует $24|\left(\sum\limits_{i}d_i\right)$?

В том-то и дело, что не следует. Вы нашли некоторые 2 делителя и показали, что их сумма делится на 24. Но в общем случае число имеет гораздо больше делителей. Ровно 2 делителя имеют лишь простые числа. Числа вида $pq$, например, имеют 4 делителя: $1;p;q;pq$.

http://ru.wikipedia.org/wiki/%D0%90%D1% ... 0%B8%D1%8F
Здесь есть немного про $\sigma (n)$, может пригодится.

[xmaister]

Sonic86, я и не предполагал, что $n-1$ имеет $2$ делителя. Я имел в виду то, если $d_i=6r\pm 1$, то среди делителей найдётся $d_j=(6r'\mp 1)$, такой что $n-1=(6r\pm 1)(6r'\mp 1)$. Т.к. $24|(d_i+d_j)$, то $\sigma (n)=\sum (d_i+d_j)$ кратно 24.
Если это не верно, тогда я в тупике. Подскажите пожалуйста как по другому решить эту задачу.

-- 09.08.2011, 21:44 --

Sonic86 в сообщении #474441 писал(а):

В том-то и дело, что не следует. Вы нашли некоторые 2 делителя и показали, что их сумма делится на 24.

Почему некоторые, если $n-1=d_id_j$, то их $d_i+d_j$ всегда делится на 24.

[Sonic86]

xmaister в сообщении #474544 писал(а):

Sonic86, я и не предполагал, что $n-1$ имеет $2$ делителя. Я имел в виду то, если $d_i=6r\pm 1$, то среди делителей найдётся $d_j=(6r'\mp 1)$, такой что $n-1=(6r\pm 1)(6r'\mp 1)$. Т.к. $24|(d_i+d_j)$, то $\sigma (n)=\sum (d_i+d_j)$ кратно 24.
Если это не верно, тогда я в тупике. Подскажите пожалуйста как по другому решить эту задачу.

Т.е. Вы пытаетесь сгруппировать в сумме $\sum\limits_{d|n}d$ делители попарно: $d$ с $\frac{n}{d}$? Если да, то об этом надо писать сразу. В таком случае все верно. Нужно лишь еще сказать, что $d \neq \frac{n}{d}$ - это очевидно.

-- Ср авг 10, 2011 03:52:36 --

Я просто прочел

xmaister в сообщении #474351 писал(а):

Пусть $6r-1$ 1 из делителей $n-1$

и тогда и начал думать, что $6r-1$ - это некоторый делитель. А оказалось - произвольный. В общем, разобрались.

[Батороев]

xmaister в сообщении #474544 писал(а):

Подскажите пожалуйста как по другому решить эту задачу.

Пусть $m=n-1=p_1p_2...p_i$.
Тогда сумма делителей $m$ равна $(p_1+1)(p_2+1)...(p_i+1)$.
Если раскрыть скобки, то получится набор слагаемых, попарные суммы которых (первое с последним, второе с предпоследним и т.д.) будут кратны $24$.

Не знаю, может быть, это тот же самый путь, который Вы рассматриваете - только "другими словами".

[Sonic86]

Батороев в сообщении #474617 писал(а):

Пусть $m=n-1=p_1p_2...p_i$.
Тогда сумма делителей $m$ равна $(p_1+1)(p_2+1)...(p_i+1)$.

Для $n=p^2 \sigma (n)=p^2+p+1 = \frac{p^3-1}{p-1} \neq (p+1)^2$ Общая формула в Вики и здесь могут быть случаи, когда $n$ не свободно от квадратов.

[Батороев]

Тьфу... забыл общую формулу:
Сумма делителей $m=p_1^{a_1}p_2^{a_2}...p_i^{a_i}$
равна $(p_1^{a_1}+p_1^{a_1-1}+...+1)(p_2^{a_2}+p_2^{a_2-1}+...+1)...(p_i^{a_i}+p_i^{a_i-1}+...+1)$
а затем все равно открываем скобки.

[Батороев]

xmaister

Посмотрел Ваше решение. Пути разнятся, но приходим к одному и тому же.

Если раскрыть в предложенной мной формуле скобки, то получим попарные суммы $d_i + d_j$.

Тогда далее необходимо рассмотреть разность $n-(d_i+d_j)=(d_i-1)(d_j-1)$ по основанию $3$ и по основанию $8$ с учетом того, что по обоим основаниям $d_id_j\equiv (-1)$.