更多課程 選擇中心
        Java培訓

        400-111-8989

        Java培訓 > Java教程  > 正文

        每個程序員都應該知道的基礎數論

        • 發布:Java培訓
        • 來源:Java教程
        • 時間:2017-10-26 10:40

        這篇文章討論了數論中每個程序員都應該知道的幾個重要概念。本文的內容既不是對數論的入門介紹,也不是針對數論中任何特定算法的討論,而只是做為數論的一篇參考。

        0. 皮亞諾公理

        整個算術規則都是建立在 5 個基本公理基礎之上的,這 5 個基本公理被稱為皮亞諾公理。皮亞諾公理定義了自然數所具有的特性,具體如下:

        0 是自然數;

        每個自然數都有一個后續自然數;

        0 不是任何自然數的后續自然數;

        不同自然數的后續自然數不同;

        如果集合 S 包含了數字 0,并且包含S中每一個數字的后續自然數,那么集合 S 就包含了所有的自然數。

        上述第5個公理也被稱為“數學歸納法的基礎”。

        通常,除了我們想要證明其他算術定理的情況,我們很少直接使用上述公理。但作為算術的基石,這些公理是值得我們去了解的。

        1. 算術基本定理和除法運算法則

        正如這個定理的名稱所言,算術基本定理是數論中所有概念的核心。

        算術基本定理含義如下:任何一個大于 1 的整數都可以以某種特定的方式寫成質數的乘積的形式(這種特定方式取決于乘積中質數的順序)。

        例如,18 = 2 * 9, 1755 = 33 *5 * 13.

        這個定理在幾乎所有的數論運算法則中都扮演著十分重要的角色,例如求一個數的質數因子、最大公約數、除數的和等等。

        想要證明這個定理其實很簡單,實際上它是歐幾里得第一個定理的一個推論(下面小節會討論到)。

        除法運算法則含義是說:給定兩個整數a,b(b不等于0),那么存在兩個整數q和r使得下面的等式成立:

        a = bq + r, 0 <= r < b

        通常我們把q稱為商,而把r稱為余數。如果r = 0,那么我就說b整除a,并且表示為:b | a.

        2. 歐幾里得定理

        數學中兩個重要定理,被稱為“歐幾里德的第一定理(或歐幾里德的引理)”和“歐幾里德的第二定理(通常簡稱為”歐幾里德定理“),內容如下:

        第一定理:p|ab => p|a or p|b。該定理的直接結論就是算術基本定理。

        第二定理:質數的數量是無限的。有很多簡單的證明方法。

        雖然確實存在無限多的質數,但也應該記住,質數之間存在任意大的差值。換句話說,給定n的前提下,總是可以獲得一些列的n個連續復合數。

        3. 最大公約數、最小公倍數和貝祖定理

        歐幾里得算法是求兩個數的最大公約數最常用的算法,而且也是一個很高效的算法,因為使用歐幾里得算法求解兩個數的最大公約數的算法步驟最多不會超過這兩個數中較小的那個數的5倍。

        最大公約數通常使用圓括號表示—— (a,b) 表示 a 和 b 的最大公約數。

        類似地,最小公倍數通常使用方括號表示—— [a,b] 表示 a 和 b 的最小公倍數。

        如果 (a,b) = 1,即 [a,b] = ab,此時我們稱 a 和 b 互質。

        如果 (a,b) = d,那么 (a/d,b/d) = 1。

        最大公約數和最小公倍數之間的關系可以由一個非常簡單的等式來表示:(a,b) * [a,b] = ab.

        該等式為我們提供了一種快速計算兩個數的最小公倍數的方法。

        貝祖定理是說,如果 d = (a,b) 那么一定存在整數 x 和整數 y 滿足 ax + by = d.(當然,如果存在的話,那么線性雙變量方程的理論保證了無窮多解的存在性)。

        同樣值得注意的是,k = d 是滿足 ax + by = k 有一個關于 x 和 y 的解的最小正整數。

        指定 a 和 b,我們可以通過遞歸或迭代的方式實現擴展的歐幾里得算法來求解滿足等式 ax + by = d 的 x 和 y。

        4. 整數因式分解

        整數因子分解的最常用的算法是 Eratosthenes 篩選法。在分解 N 時,將質數掃描到 sqrt(N) 就足夠了。

        另外,如果我們需要對 1 到 N 之間的所有數字進行因式分解,則可以使用該算法的單次運行來完成此任務 - 對于 1 到 N 之間的每個整數 k ,我們可以保持一對映射——整除 k 的最小質數、最大倍數,(p,a)。k 的剩余質因子與 k/(pa) 的相似。

        5. 線性同余方程組

        形如 ax≡b (mod n) 的方程式( x 是未知數)稱為線性同余。當且僅當存在整數 x 使得 n | (ax-b) 成立時,這樣的方程組將有一個解,即 ax -b = ny,y 是整數,換句話說,ax + n(-y)= b。

        我們已經從 Bezout 的等式中得知,像這樣的線性不定方程將只有在 (a,n) 的 gcd (假設該值為d) 整除 b 時才有解。

        在這種情況下,讓 b = dd',a = da',n = dn',所以我們有:

        da'x + dn'( - y)= dd',其中 gcd(a',n')= 1

        帶入變量 d

        a'x + n'( - y)= d'。

        由于 gcd(a',n') = 1,現在我們可以使用擴展的歐幾里德的算法來找到 a'x + n'( - y)= 1 的解,然后將該解乘以 d' 得到對于 a'x + n'( - y)= d' 的解。

        注意:如果 ax≡b(mod n) 有一個解,則 mod(n / d) 有且僅有一個解。

        如果這個解是用 x0 表示的,那么mod n將恰好有 d 個解,由 x0 + kn/d 給出,其中 0<= k

        6.中國剩余定理

        典型的問題形式是“尋找一個數,除以 2 余 1,除以 3 余 2,除以 7 余 5”其余各項可以被推廣為一元線性同余方程組之后可以使用中國剩余定理來解決。

        舉個例子,下面的問題可以被表示為三個線性同余式:“x ≡ 1 (mod 2), x ≡ 2 mod(3), x ≡ 5 mod (7)”

        也就是一元線性同余式方程組:

        x ≡ a1 (mod n1)

        x ≡ a2 (mod n2)

        x ≡ a3 (mod n3)

        ....

        x ≡ ak (mod nk)

        假設整數 ni,nj 兩兩互質,則對任意的 n=n1n2...nk,方程組有解

        對于任意的 i,當 0 <= di < ni,令 ci=n/ni,令 di 為同余式 cix=1(mod ni) 的解(這個解法可以在利用擴展的歐幾里德算法)。

        上面的線性方程組的通解可以給出為:

        c = a1c1d1 + a2c2d2 + ... + akckdk

        中國剩余定理的直接推論如下:假設 n = p1a1 * p2a2 * .... * pkak 為 n 的素因子分解。 那么,對于任何整數 a 和 b,我們對于每個 i 都有 a = b (mod n) iff a = b (mod piai ) 。

        討論一下 Ni 的不一定都是兩兩互質的中國剩余定理的推廣,如下 - 線性同余系統

        x≡a1(mod n1)

        x≡a2(mod n2)

        x≡a3(mod n3)

        ....

        x≡ak(mod nk)

        有解,當對于每個 i != j 都有 iff gcd(ni,nj) 除 (ai-aj) ,且存在唯一解 mod n,其中 n 是 n1,n2 ... k 的最小公倍數

        7. 二次方一致性

        給定 q 和 n,如果等式 x2≡q(mod n) 具有解,則 q 稱為二次殘差的模 n。

        如果該方程不具有解,則q被稱為“二次非殘差”。

        例如,x2≡9(mod 15) 具有解 x = 12,因此 9 是模 15 的二次余數。

        另一方面,等式 x2≡11(mod 15) 沒有解,因此 11 是二次非殘差,為了簡單起見,如果一個正方形可以取一些正整數 n 的形式(nk + q),則整數 q 是模 n 的二次余數。

        發現具有質數模的二次一致性是否具有一個解,是有些容易的:x2≡a(mod p) 只有在 (p-1)/ 2 = 1(mod p) 時才具有解。

        在這種情況下,可以使用 Shank-Tonelli 算法來獲得解決方案。

        8. 歐拉 Phi 函數、除數函數、約數和、Mobius 函數

        歐拉的 Phi 函數 (又稱為常數函數,由φ表示)是自然數的函數,給出與相應的自然數互質的正整數的數目。因此,φ(8) = 4, φ(9) = 6 等。

        該函數的以下屬性值得注意:

        如果 p 是素數,則 φ(pk) = (p-1)pk-1

        φ 函數是乘法的,即如果 if (a,b) = 1 則 φ(ab) = φ(a)φ(b)。

        φ(n) 的值可以通過歐拉公式獲得:令 n = p1a1 * p2a2 * .... * pkak 是 n 的素因子分解。則:

        φ(n) = n * (1- 1/p1)) * (1- 1/p2)) * ... * (1- 1/pk))

        以編程方式,如果我們欲求 1 到 n 的 φ , 那么我們可以非常好地使用篩選算法連同 φ 的乘法性質。中心思想是:如果 n 是素數,則 φ(n) = -1。否則,如果 n 是素數的冪,例如 n= pk,則 φ(n) = (p-1)pk-1。否則,對于某個素數p,令 n=pk*q 。使用乘法屬性, 我們有 φ(n) = φ(pk)φ(q)

        φ(n) 的兩個重要屬性:

        i. aφ(n) ≡ 1 (mod n) 每當 (a,n) = 1。 具體來說, 對于素數p,如果 p 不能整除 a,則 ap-1 ≡ 1 (mod p)。 這種特化也被稱為費馬小定理。

        ii. 令 d1, d2, ...dk 為 n 的所有除數(包括 n)。則 φ(d1) + φ(d2) + ... + φ(dk) = n

        例如,18的除數是1、2、3、6、9 和 18。觀察到 φ(1) + φ(2) + φ(3) + φ(6) + φ(9) + φ(18) = 1 + 1 + 2 + 2 + 6 + 6 = 18

        該除數函數,表示為 d(n),給出了一個自然數的除數的數目。例如,d(18) = 6。類似地,除數函數之和,表示為 σ(n),給出了 n 的除數的和。

        因此,σ(18) = 1+2+3+6+9+18 = 39。關于這兩個函數以下屬性毫無價值:

        如果 p 是素數,則 d(p) = 2。另外, d(pk) = k+1, 并且 σ(p) = p+1

        如果 n 是兩個不同的素數的乘積,假使 n = pq, 則 σ(n) = n+1+(p+q)。另外觀察到這種情況:φ(n) = +1-(p+q)。

        一般來說,令 n = p1a1 * p2a2 * .... * pkak 。則 d(n) = (a1+1) * (a2+1) * ... (ak + 1),并且 σ(n) 由以下乘積給出:

        σ(n) = ( (p1(a1+1) - 1) / (p1-1) ) * ( (p2(a2+1) - 1) / (p2-1) ) * ... * ( (pk(ak+1) - 1) / (pk-1) )

        如果 σ(n) =2n,則 n 被稱為“完全數”。換句話說, 完全數的真因子(即除了自身以外的除數)的和恰好等于它本身。

        mobius函數μ(n) 在所有正整數中定義如下:

        在 n 是非平方數(即 n 是不能被任意整數平方得到)并且 n 有偶數個不同的素數因子,則 μ(n) = 1

        在 n 是非平方數(即 n 是不能被任意整數平方得到)并且 n 具有奇數個不同素數因子,則μ(n) = -1

        在 n 是平方數,即 n 是某個整數的平方,則 μ(n) = 0

        Mobius 函數是乘法分配性的,即 a 和 b 互為質數,則 μ(ab) = μ(a)*μ(b).

        計算歐拉方程函數的一個有用公式可以用 mobius 函數給出:令 d1,d2,... dk 為 n 的所有除數。然后

        φ(n) = (d1 * mu (n/d1) ) + (d2 * μ(n/d2) ) + .... + (dk * μ(n/dk) )

        這也可以寫成:

        φ(n) = (μ(d1) * (n/d1) ) + (μ(d2) * (n/d2) ) + .... + (μ(dk) * (n/dk) )

        使用篩選法計算 phi[n] 的 Java 實現如下:

        每個程序員都應該知道的基礎數論

        階乘

        階乘是非常重要的。N 的階乘定義如下:N = (N)*(N-1)*(N-2)*(N-3)...1。在計算 nPr nCr 時需要使用階乘。他們像這里描述的那樣很快變得非常大,所以他們需要非常仔細的處理大數、大整數表示等。

        到此我們完成了對基本數理論概念的討論。

        整數序列

        流行的整數序列有很多。它們中的許多都基于遞歸關系。主要的定理被廣泛用于了解其復雜性,邊界與循環的關系。

        很多流行的整數序列,例如:費布那切數列,魯卡斯數字, 斯特恩雙原子數字, 懶卡特數字, 帕多萬數字 還有多邊形數字,諸如 五角形數字, 六角形數字。

        對數論的介紹:哈迪和賴特

        初等數論: 瓊斯和瓊斯

        數學誘導 - 一種技術教程,經常用于離散空間的證明。

        具有數學歸納原理的問題和解決方案的教程。

        感謝大家閱讀由java培訓機構分享的“每個程序員都應該知道的基礎數論”希望對大家有所幫助,更多精彩內容請關注Java培訓官網

        免責聲明:本文由小編轉載自網絡,旨在分享提供閱讀,版權歸原作者所有,如有侵權請聯系我們進行刪除

        預約申請免費試聽課

        填寫下面表單即可預約申請免費試聽!怕錢不夠?可就業掙錢后再付學費! 怕學不會?助教全程陪讀,隨時解惑!擔心就業?一地學習,可全國推薦就業!

        上一篇:將 Spring Boot 應用程序遷移到 Java 9:兼容性
        下一篇:Java工程師為何如此火爆?
        12大要點讓你的Java開發所向披靡~

        12大要點讓你的Java開發所向披靡~

        學習Java最好的12本免費在線電子書

        學習Java最好的12本免費在線電子書

        Java常用日志框架介紹

        Java常用日志框架介紹

        一篇文章了解RPC框架原理

        一篇文章了解RPC框架原理

        • 掃碼領取資料

          回復關鍵字:視頻資料

          免費領取 達內課程視頻學習資料

        • 視頻學習QQ群

          添加QQ群:1143617948

          免費領取達內課程視頻學習資料

        Copyright ? 2021 Tedu.cn All Rights Reserved 京ICP備08000853號-56 京公網安備 11010802029508號 達內時代科技集團有限公司 版權所有

        選擇城市和中心
        貴州省

        福建省

        • 達內廈門軟件園中心
        廣西省

        海南省

        国产高清情侣视频2019年,限制电影福利在线观看,23伊人大香蕉 百度 好搜 搜狗
        <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| <文本链> <文本链> <文本链> <文本链> <文本链> <文本链>