-
1 # EmacserVimer
-
2 # 思考思考的動物
先明確定義:將 整數集 記為 Z,對於 任意 整數 a, b ∈ Z (b ≠ 0),如果存在 整數 c ∈ Z 使得 a = bc,則稱 b 整除 a,記為 b | a,並且稱 b 是 a 的 因數(也叫做 約數 或 除數),a 是 b 的 倍數。
於是,對於任何一個 整數 a ∈ Z (a ≠ 0),顯然有 a · 1 = a,(-a) · (-1) = a,我們稱 ±a 和 ±1 為 a 的顯然因數。
故,在整數範圍內考慮,一個非零整數 a(≠ ±1) 的因數至少有 4 個,即,a 的顯然因數:a 、1、 -1 和 -a,而 ±1 只有兩個因數 1 和 -1。
進而,在 正整數範圍 內考慮,一個正整數 a(≠ 1) 的因數至少有 2 個,即,a 和 1,而 1 時 只有 它自己 1個因數。
那麼,一個正整數的正因數具體有幾個呢?為了回答這個問題,我們需要引入素數的定義:對於 任意整數 p ∈ Z (p ≠ 0, ±1),如果 p 除了顯然因數外沒有其它因數,則稱 p 為 素數(也稱 質數 或 不可約數),否則 稱 p 為 合數(也稱 可約數)。
由於 整數集 Z 關於 0 是對稱的,因此我們只需要研究清楚 正整數集 Z₊,負整數集 Z₋ 就自然清楚了。於是:以後 素數 和 合數 預設特指 大於 1 的 正整數。
在《初等數論》中有一個非常重要的定理,稱為 算術基本定理:對於任意 正整數 n ∈ Z₊ (a > 1) ,必然有,
n = p₁p₂...pᵣ
其中 pᵢ( i = 1, 2, ..., r) 皆為素數,並且在便考慮順序的情況下,這個素因數分解式唯一。例如:
108 = 2 · 2 · 3 · 3 · 3
顯然,素因數 會有重複,於是我們將 上面的 素因數分解式 改寫為:
n = p₁ᵃ¹p₂ᵃ²...pᵣᵃʳ,(p₁< p₂ <... <pᵣ) ⑴
稱為 a 的 標準素因數分解式。例如:
108 = 2² · 3³
任意給定一個 正整數 n(> 1) ,n 的 正因數個數,記為 τ(n),稱 τ(n) 為 除數函式。
考慮 n 的 標準素因數分解式 ⑴ ,可分為下面的組:
1, p₁, p₁², ..., p₁ᵃ¹ (共 a₁ + 1 個)
1, p₂, p₂², ..., p₂ᵃ² (共 a₂ + 1 個)
...
1, pᵣ, pᵣ², ..., pᵣᵃʳ (共 aᵣ + 1 個)
顯然,n 的每個因數,就是從上面每組裡任意選擇一個數,然後將它們連乘的結果,所有肯能結果的個數是:
(a₁ + 1)(a₂ + 1)...(aᵣ + 1)
這就是 τ(n),即,
τ(n) = (a₁ + 1)(a₂ + 1)...(aᵣ + 1) = ∏ʳᵢ₌₁ aᵢ + 1
例如:
τ(108) = (2 + 1) · (3 + 1) = 12
又引入定義:對於 任意正整數 n, m ∈ Z₊,若 存在 正整數 a ∈ Z₊ 滿足 a | n 並且 a | m 則稱 a 是 n 和 m 的 公因數(也稱 公約數),將 n 和 m 的所有 公因數 中 最大的那個 稱為 最大公因數,記為 (n, m) 或 gcd(n,m)。
如果 (n, m) = 1,則稱 n 和 m 互素(或 互質)。例如:
108 和 49 互素:49 = 7²,(108, 49) = 1
108 和 9 不互素:9 = 3²,(108, 9) = 9
進一步觀察我發現性質: 當 n 和 m 互素,即, (n, m) = 1 時,有 τ(nm) = τ(n)τ(m)。
例如:
108 · 49 = 2² · 3³ · 7²
τ(108 · 49) = (2 + 1)(3 + 1)(2 + 1) = 36
τ(49) = (2 + 1) = 3
τ(108 · 49) = 36 = 12 · 3 = τ(108) · τ(49)
而 當 (n, m) ≠ 1 時,上面的性質不成立,例如:
108 · 9 = 2² · 3⁵
τ(108 · 9) = (2 + 1)(5 + 1) = 18
τ(9) = (2 + 1) = 3
τ(108 · 9) = 18 ≠ 36 = 12 · 3 = τ(108) · τ(9)
定義:如果 數論函式 f 滿足,
f(nm) = f(n)f(m),(n, m) = 1
則稱 f 是積性函式。
注:積性函式 是 最重要的 數論函式,在 Mobius 變換 中起到重要作用,以後有機會 給大家介紹。τ(n) 顯然 就是 積性函式。
順便:在初等數論中,還定義了 除數和函式 σ(n) ,它的值為 正整數 n(>1) 的 所有正因數之和,根據上面的經驗知下面的展開式的項,包含 n 的所有正因數:
(1 + p₁ + p₁² + ... + p₁ᵃ¹)(1 + p₂ + p₂² + ... + p₂ᵃ²) ... (1 + pᵣ + pᵣ² + ... + pᵣᵃʳ)
因此,
σ(n) = (1 + p₁ + p₁² + ... + p₁ᵃ¹)(1 + p₂ + p₂² + ... + p₂ᵃ²) ... (1 + pᵣ + pᵣ² + ... + pᵣᵃʳ)
= ((p₁ᵃ¹⁺¹ - 1) / (p₁ - 1))((p₂ᵃ²⁺¹ - 1) / (p₂ - 1))...((pᵣᵃʳ⁺¹ - 1) / (pᵣ - 1))
=∏ʳᵢ₌₁ (pᵢᵃⁱ⁺¹ - 1) / (pᵢ - 1)
如果是在 有理數域 Q 上考慮題主的問題呢?對於 有理數集 Q 中任意 一個非零 的 數 x(≠0) 必然存在 x 的倒數 x⁻¹ = 1,因此 對於 任意 有理數 y ∈ Q,y ≠ 0,必然有:
y = yx⁻¹ · x
根據 上面 因數的 定義 非零的 x 是任何非零 y 的 因數。
故,在有理數範圍內考慮,一個非零有理數 x 的因數必然有 |Q\{0}| = ℵ₀ 個。
注: A \ B 是差集運算,即,從 集合 A 中 除去 集合 B 中包含的元素。對於 實數域 R 和 複數域 C 和 有理數域 Q 類似,於是有:
在實數 或 複數 範圍內考慮,一個非零實數 x 或 非零複數 z 的因數必然有 |R\{0}| = ℵ₁ 或 |C\{0}| = ℵ₁ 個。
注: |A| 表示 集合A 中 的元素個數。對於無限集合,我們用 ℵ₀, ℵ₁, ... 來區別表示它們的元素個數,其中 只有 ℵ₀ 是可列的。最後,考慮 一下 0 的因數。根據 因數定義,0 不是任何 數的因數,而又因為 任何數 x 乘以 0 都是 0,即,
0 = x · 0
所以,任何非零數 x 都是 0 的因子。
故,分別在 整數、有理數、實數、複數 範圍內,0 的因子數分別是 |Z\{0}| = ℵ₀ 、 |Q\{0}| = ℵ₀、 |R\{0}| = ℵ₁ 、 |C\{0}| = ℵ₁ 個。
回覆列表
一個數的因素至少有1個!這個數就是自然數1,1的因數只有它本身!
什麼是自然數?根據ISO 80000-2標準的規定,自然數通常指的是非負整數(0,1,2,3,...),自然數是用來計數和定序的數,用來計數的時候稱為基數,用來定序的時候稱為序數。
在數論中,非零自然數也就是正整數,我們通常用N來表示這個集合,自然數是一個可數的,沒有上界的無窮集合。
對於0是不是自然數現在在於全球依然是一個不小的爭議,不過在國內2000之前的中小學教材一般不把0作為自然數,2000年以後的中小學教材普遍都認為0是自然數。
什麼是質數(素數)?一個大於1的正整數P,除了1和他本身之外沒有別的因子,那麼這個數就是質數、也就是我們經常所說的素數。最小的素數是2,它只有1和2兩個因子。
每一個整數都能表示我素數的乘積,假設一個數不是素數,那麼可以不斷地對這個數進行因式分解,知道所有的因子都變成素數位置。比如:360=3*120=3*30*4=3*3*10*4=3*3*5*2*2*2,一個整數不是素數就成為合數(0和1除外)。
素數有無窮多個嗎?素數有無窮多個的證明是著名數學家歐幾里得給出的,這也是數學歷史上一個經典的證明,使用的是反證法。
我們假設素數沒有無窮個:也就是說假設素數只有有限個,當然這個可能會很多,比如1億個、10億個等等。
一般地、我們假設有n個這樣的數,用p1,p2,...,pn來表示,除此之外其他的任何一個數字都是合數,那麼素數p1,p2,...,pn中有一個能夠整除它,現在假設這個數是M,讓它比上面的任何一個素數都要打,它也因此與任何一個都不同,又讓它不能夠被上述p1,p2,...,pn中任何一個整除,這就產生了矛盾。這個數可表示為M=p1p2...pn+1,我們假設所有素數的乘積再加上1,M比這些p中的任何一個都要大,因此必須是合數。不過用p1,p2等去除M總會餘1,因此這些P並不是M的因子,這是由我們的假設而產生的矛盾,而我們假設素數是有限的,因此假設不成立,那麼相應的素數就應該是無窮的。
其實數學是很有趣的一門學科,數理化、計算機應該算是所有學科門類當中最有趣的學科,大家還記得帶電粒子在磁場、電場當中的運動嗎?你還記得正十七邊形的尺規作圖嗎?還記得用C語言實現KMP演算法嗎?理工科有趣的地方,首先他們的各種各樣的公式定理就很有趣。