知識總結 約數個數定理和約數和定理及其證明

2022-09-22 17:53:58 字數 769 閱讀 5434

據說這倆是小學奧數內容?完了我菜成一團沒上過小學

本文只研究正整數\(a\)的約數個數和約數和。首先對\(a\)分解質因數

\[a=\prod_i^n p_i^ \ (p_i是質數)

\]先看結論

\[num=\sum_i^n (a_i+1)

\]考慮對於\(a\)的任意一個約數\(a\),都顯然存在唯一的數列\(a'\)使

\[a=\prod_i^n p_i^ \ (0 \leq a'_i \leq a_i)

\]由唯一分解定理得,每一個符合條件的數列\(a'\)都對應\(a\)的一個約數,反之亦然。由乘法原理得共有\((a_1+1)*(a_2+1)...*(a_n+1)\)種數列\(a'\),得證。

同樣先看結論:

\[sum=\prod_^n\sum_^p_i^j

\]首先考慮\(n=1\)的情況,即\(a=p^a \ (p是質數)\),顯然約數和是\(\sum_^p^i\)

當\(n>1\),如果已知了\(x=a/}\)的約數和\(sum'\),如何求\(a\)的約數和\(sum\)呢?

顯然,給每個\(x\)的約數\(x'\)均乘上每一個\(p_n^i \ (0 \leq i \leq a_n)\),就構成了\(a\)的約數集合。那麼就得到

\[sum=\sum \left(x'*\sum _^p_n^i\right)

\]由乘法分配律得到

\[sum=sum'*\sum _^p_n^i

\]又由當\(n=1\)時\(sum=\sum_^p^i\)遞推得到最終的結論。