Представление всех делителей числа

[ean]

Привет,

Пытаюсь разобраться с такой задачкой: число представимо следующим образом $a=p^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_r}_r$, где $p_i$ - простые (различные) числа. Нужно доказать, что все делители числа $a$ имеют вид $b=p^{\beta_1}_1p^{\beta_2}_2...p^{\beta_r}_r$, где $0\leqslant \beta_i\leqslant \alpha_i$
Я так действовал:
Пусть $c$ - делитель $a$ не представимый в виде $b$. Представляем $c$ в виде произведения степеней простых множителей $c=k^{\gamma_1}_1k^{\gamma_2}_2...k^{\gamma_m}_m$.
Т.к. $c$ делитель $a$, то существует $t$ такое, что $a=ct$. $t$ так же представляем в виде произведение степеней простых чисел $t=l^{\delta_1}_1l^{\delta_2}_2...l^{\delta_n}_n$. Следовательно $a$ представляется таким способом $a=k^{\gamma_1}_1k^{\gamma_2}_2...k^{\gamma_m}_ml^{\delta_1}_1l^{\delta_2}_2...l^{\delta_n}_n$, но $a=p^{\alpha_1}_1p^{\alpha_2}_2...p^{\alpha_r}_r$ и известно, что число раскладывается на простые множители единственным образом (с точностью до порядка множителей). Поэтому все $k_i$ совпадают с некоторыми (различными) $p_j$, следовательно $c$ представимо в виде $b$, что и требовалось доказать.
Скажите верно ли доказательство? У меня сомнения насчёт того, правильно ли я делаю вывод, не перескакиваю ли через какие-нибудь логические связки.
Задачка из Куранта и Роббинса "Что такое математика?"

И в продолжение этой же задачи: нужно доказать, что число всех делителей $a$ равно произведению $(\alpha_1+1)(\alpha_2+1)...(\alpha_r+1)$.
Как я понимаю, нужно просто перечислить все делители. Перечисляем следующим образом:
$p^0_1p^0_2...p^0_r$, $p^1_1p^0_2...p^0_r$, $p^2_1p^0_2...p^0_r$, ..., $p^{\alpha_1}_1p^0_2...p^0_r$ - $\alpha_1+1$ множителей (включая 1). Дальше фиксируем $p^0_1$ и перебираем все $p_2$ начиная с 1, т.е.
$p^0_1p^1_2...p^0_r$, $p^0_1p^2_2...p^0_r$, $p^0_1p^3_2...p^0_r$, ..., $p^0_1p^{\alpha_2}_2...p^0_r$, дальше двигаемся от $p^1_1$, получаем
$p^1_1p^1_2...p^0_r$, $p^1_1p^2_2...p^0_r$, $p^1_1p^3_2...p^0_r$, ..., $p^1_1p^{\alpha_2}_2...p^0_r$, и т.д., получаем перебрав $p_1$ и $p_2$ $(\alpha_1+1)(\alpha_2+1)$ элементов последовательности (делителей).
Перебрав все $p_i$ получаем $(\alpha_1+1)(\alpha_2+1)...(\alpha_r+1)$ делителей, что и требовалось доказать.
Правильно? Или тут возможен какой-то более изящный ход рассуждений?

[maxal]

ean в сообщении #339216 писал(а):

Поэтому все $k_i$ совпадают с некоторыми (различными) $p_j$, следовательно $c$ представимо в виде $b$, что и требовалось доказать.

Тут еще надо сказать, что показатель каждого простого $p$ в разложении $c$ не может превосходить соответствующего показателя в разложении $a$.

А для второй задачки достаточно заметить, что каждый показатель $\beta_i$ может меняться в пределах от 0 до $\alpha_i$ независимо от остальных показателей.

[Батороев]

Вторую задачу легче решить, если знать, как находятся все делители числа в виде слагаемых при раскрытии скобок в выражении:
$ (p_1^{\alpha_1}+p_1^{\alpha_1-1}+p_1^{\alpha_1-2}+...+ p_1+1)... (p_r^{\alpha_r}+p_r^{\alpha_r-1}+p_r^{\alpha_r-2}+...+ p_r+1)$

Число слагаемых и дает число делителей.

Единственное, возникает сомнение, можно ли считать делителем числа само число, т.к. оно получается в виде первого слагаемого? Ведь в противном случае, ни о каких совершенных числах речи быть не могло?

[maxal]

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

Единственное, возникает сомнение, можно ли считать делителем числа само число, т.к. оно получается в виде первого слагаемого? Ведь в противном случае, ни о каких совершенных числах речи быть не могло?

Совершенное число определяется через сумму своих собственных делителей, то есть, делителей отличных от самого числа.
Само число же, конечно, является своим делителем, но несобственным.

[Батороев]

Понял... Тоды "ой!"

[ean]

maxal в сообщении #339270 писал(а):

Тут еще надо сказать, что показатель каждого простого $p$ в разложении $c$ не может превосходить соответствующего показателя в разложении $a$.

Как я понимаю, для этого нужно сказать, что все $l_i$ тоже совпадают с $p_j$. Тогда возможно два варианта, либо $p_j$ совпадает только с одним делителей $c$ - $k_i$, тогда исходя из единственности разложения следует $\alpha_j=\gamma_i$. Либо $p_j=k_i=l_h$, тогда $\alpha_j=\gamma_i+\delta_h$. Следовательно выполняется неравенство $0\leqslant\gamma_j\leqslant \alpha_i$, когда $k_j=p_i$, что и требовалось показать. Верно?

maxal в сообщении #339270 писал(а):

А для второй задачки достаточно заметить, что каждый показатель $\beta_i$ может меняться в пределах от 0 до $\alpha_i$ независимо от остальных показателей.

Да, это я понимаю, $r$ вложенных циклов со счётчиками от 0 до $\alpha_i$ даёт нам как раз $(\alpha_1+1)(\alpha_2+1)...(\alpha_r+1)$ итераций, но не знаю как это верно сформулировать.

-- Чт июл 15, 2010 15:30:37 --

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

Вторую задачу легче решить, если знать, как находятся все делители числа в виде слагаемых при раскрытии скобок в выражении:
$ (p_1^{\alpha_1}+p_1^{\alpha_1-1}+p_1^{\alpha_1-2}+...+ p_1+1)... (p_r^{\alpha_r}+p_r^{\alpha_r-1}+p_r^{\alpha_r-2}+...+ p_r+1)$

Число слагаемых и дает число делителей.

Ну да, а как пройти к такому разложению?

[Батороев]

ean в сообщении #339347 писал(а):

Ну да, а как пройти к такому разложению?

Я как-то на досуге увлекся совершенными числами и пришел к этому разложению "сам не знамо как".

А если серьезно, то по-видимому, с учетом того, что писал maxal:

maxal в сообщении #339270 писал(а):

А для второй задачки достаточно заметить, что каждый показатель $\beta_i$ может меняться в пределах от 0 до $\alpha_i$ независимо от остальных показателей.

Ведь, в представленном разложении все так и выполнено, т.е. использовались во-первых, все степени $\beta_i$, а во-вторых, независимо (т.к. разведены по соответствующим скобкам).

[VAL]

Решение обеих задачек: очевидно.
Если кому-то не очевидно (а таких, например, среди моих студентов большинство), то это следствие порочного отношения к арифметике в нынешней средней школе

[maxal]

VAL в сообщении #339406 писал(а):

Решение обеих задачек: очевидно.

На самом деле прежде чем такое заявлять, нужно хотя бы раз всё аккуратно доказать (см. мой теглайн).

[VAL]

maxal в сообщении #339410 писал(а):

VAL в сообщении #339406 писал(а):

Решение обеих задачек: очевидно.

На самом деле прежде чем такое заявлять, нужно хотя бы раз всё аккуратно доказать (см. мой теглайн).

Даю честное, благородное слово, что именно это мне было очевидно с первого раза!

Позволю себе, не то чтобы оффтоп, скорее, небольшой мемуар. Наверное, возраст диктует жанр

С каноническим разложением натуральных чисел у меня связана одна история времен моего поступления в вуз. На устном экзамене по математике мне необходима была пятерка: в тот год, как раз, начали средний балл аттестата учитывать, а он у меня был ниже, чем у большинства конкурентов, да и за сочинение мне больше тройки не светило (не умею без очепяток писать).

А тут достается вопрос: свойства НОД и НОК - единственный, который я не повторял, поскольку он изучался в более младшем классе, чем все остальные, входившие в программу экзамена. А учебника за этот класс у меня не было и искать я его не стал, не попадется же этот вопрос...
В общем, сел готовиться по другим вопросам, а что по этому отвечать - без понятия. Нет, что такое НОД и НОК я знал, у меня же по алгебре в школе тройка была настоящая, не натянутая. Но вот что отвечать по вопросу - без понятия.

И вдруг слышу один экзаменатор (через девять лет я устроился на кафедру алгебры и геометрии как раз вместо него, он в другой вуз перешел) шепчет другой экзаменаторше: "Вы не смотрели как в новом учебнике НОД и НОК излагается. Я слышал, что через каноническое разложение". А напарница ему, отвечает, что она тоже не курсе. А он ей, ничего, мол, разберемся.
В тот год, как раз на другие (колмогоровские) учебники переходили.

Я, разумеется, учился по старым учебникам, ведь переходили постепенно, начиная с какого-то младшего класса. Но за соломинку ухватился. Сформулировал и доказал (возможно, сославшись на очевидность, сейчас уже не помню) ту самую лемму, с которой начинается эта ветка. На ее основании получил формулы для нахождения НОД и НОК, а затем еще некоторые свойства. Те ли свойства были нужны, не знаю. Я потом не удосужился проверить. Но экзаменаторы ведь тоже не знали и проверяли только правильность свойств. А с этим проблем не было.

В общем, свою пятерку я получил. И зацепился за полупроходной балл.
А если бы данная тематика не была мне (абитуриенту-троечнику) очевидна, форум dxdy лишился бы одного ЗУ, а Математический Марафон одного ведущего

[rush]

(Оффтоп)

Цитата:

форум dxdy лишился бы одного ЗУ, а Математический Марафон одного ведущего

и босс одного поинта

[ewert]

(Оффтоп)

VAL в сообщении #339435 писал(а):

Те ли свойства были нужны, не знаю.

У меня была противоположная ситуация на коллоквиуме по матану в середине первого семестра.

Попался мне один из вопросов -- что-то типа критерия Коши, детали уже не помню (насчёт эквивалентности сходимости и фундаментальности). Ну я это твёрдо знал, и рассказал абсолютно честно, ровно так, как в школе учили. Нет, не засчитали и поставили четвёрку, я очень обиделся. Потом-то (через день) понял, что мы просто не сошлись в том, что считать определением, а там это вопрос неоднозначный.

Ну там-то, конечно, не прав был в первую очередь (хотя и не совсем) я сам -- к порядку изложения в лекционным курсе надо относиться уважительнее. И тем не менее, к чему это всё: формулировки типа "свойства НОД и НОК" -- совершенно неприличны. Мало ли что считать свойствами, а что чем. Формулировать вопросы следует конкретно.