同余與模運算LET'SEMBARKONTODAY'SSHARINGJOURNEYTOGETHER01同余基本概念Let'sembarkontoday'sjourneyofsharingandcommunicationtogether同余的定義在數(shù)論中，同余是研究整數(shù)關(guān)系的重要工具。給定正整數(shù)m，若整數(shù)a與b的差a-b能被m整除，即m|(a-b)，則稱a與b模m同余，記作a≡b(modm)。余數(shù)視角從余數(shù)角度看，模m同余意味著a與b除以m后余數(shù)相同。例如，17和23除以6余數(shù)均為5，因此17≡23(mod6)。等價表述同余關(guān)系還可等價表述為存在整數(shù)k，使a-b=km。若a與b不同余，則記作a?b(modm)。同余定義與符號體系同余關(guān)系性質(zhì)等價關(guān)系同余關(guān)系是等價關(guān)系，滿足自反性、對稱性和傳遞性。自反性：任何整數(shù)a，有a≡a(modm)；對稱性：若a≡b(modm)，則b≡a(modm)；傳遞性：若a≡b且b≡c，則a≡c。等價類劃分基于同余關(guān)系，整數(shù)集被劃分為互不相交的等價類。每個等價類包含所有模m同余的整數(shù)，為后續(xù)剩余類概念奠定基礎(chǔ)。02同余運算規(guī)則Let'sembarkontoday'sjourneyofsharingandcommunicationtogether同余運算封閉性若a≡b(modm)且c≡d(modm)，則a±c≡b±d(modm)與ac≡bd(modm)。該性質(zhì)使同余式可像等式一樣進(jìn)行加減乘運算，簡化大數(shù)模運算。封閉性規(guī)則冪次與約簡的同余技巧01若a≡b(modm)，則a^k≡b^k(modm)對正整數(shù)k成立。此性質(zhì)可用于快速計算大指數(shù)模值，提升計算效率。冪次同余02當(dāng)d整除m且d為正時，若a≡b(modm)，則a≡b(modd)。這體現(xiàn)了模數(shù)縮小對同余關(guān)系的保持。約簡同余03在互素模數(shù)下，聯(lián)合同余關(guān)系可進(jìn)一步拓展，為中國剩余定理的引入奠定基礎(chǔ)。聯(lián)合同余消去律與逆元條件素數(shù)模下的消去律當(dāng)模數(shù)為素數(shù)p時，任何非零c均可消去。這為模p下的除法運算提供了理論基礎(chǔ)，簡化了計算過程。若ac≡bc(modm)且c與m互素，則可推出a≡b(modm)?；ニ貤l件是消去律成立的關(guān)鍵，否則需調(diào)整模數(shù)。消去律條件03剩余系Let'sembarkontoday'sjourneyofsharingandcommunicationtogether剩余類的劃分與特征模m剩余類是所有除以m余r的整數(shù)集合，記作[r]_m。共有m個互不相交的剩余類，每個類中的元素彼此同余。01以模2為例，整數(shù)被劃分為奇數(shù)類[1]_2和偶數(shù)類[0]_2，直觀展示了剩余類的劃分方式。

02劃分實例剩余類定義完全剩余系的構(gòu)造從每個剩余類中各取一數(shù)組成的m元集合稱為完全剩余系。非負(fù)最小完全剩余系為{0,1,…,m-1}。完全剩余系定義當(dāng)模數(shù)為奇數(shù)時，絕對最小完全剩余系為{-(m-1)/2,…,(m-1)/2}，體現(xiàn)了對稱性。奇模數(shù)絕對最小系偶模數(shù)絕對最小系當(dāng)模數(shù)為偶數(shù)時，絕對最小完全剩余系可為{-m/2+1,…,m/2}或{-m/2,…,m/2-1}。04簡化剩余系與歐拉函數(shù)Let'sembarkontoday'sjourneyofsharingandcommunicationtogether簡化剩余系的定義與示例從與m互素的剩余類中各取一數(shù)組成的集合稱為簡化剩余系，其大小等于歐拉函數(shù)φ(m)。簡化剩余系定義在模8的非負(fù)最小完全剩余系{0,1,…,7}中，只有1、3、5、7與8互素，因此{(lán)1,3,5,7}是模8的一個最小簡化剩余系。模8的簡化剩余系歐拉函數(shù)的積性公式積性公式歐拉函數(shù)φ(m)表示不超過m且與m互素的正整數(shù)個數(shù)。若m的標(biāo)準(zhǔn)分解式為m=∏p_i^{a_i}，則φ(m)=m∏(1-1/p_i)，該公式將φ(m)計算轉(zhuǎn)化為質(zhì)因數(shù)分解問題。05算法實現(xiàn)與示例Let'sembarkontoday'sjourneyofsharingandcommunicationtogether計算單個歐拉函數(shù)值的算法euler(n)中，初始化r=n，然后用試除法遍歷2到√n的整數(shù)。算法初始化每遇到因子i，執(zhí)行r-=r/i并除盡i的冪次。第6行利用乘法逆元思想實現(xiàn)r*(1-1/i)的整數(shù)運算。因子處理若剩余n>1，再執(zhí)行一次r-=r/n。該算法時間復(fù)雜度為O(√n)，高效計算歐拉函數(shù)值。最終調(diào)整批量計算與結(jié)果展示01批量算法批量計算歐拉函數(shù)的算法euler(n,phi[])中，用篩法思想對每個質(zhì)數(shù)i，將其倍數(shù)j的phi[j]初始為j，再執(zhí)行phi[j]=phi[j]/i*(i-1)。02結(jié)果展示該算法一次篩出2到n-1的所有φ值，時間復(fù)雜度接近O(nloglogn)。圖10.3展示了前50個自然數(shù)的φ值對照，驗證了算法的準(zhǔn)確性。06小結(jié)Let'sembarkontoday'sjourneyofsharingandcommunicationtogether同余思想的價值延伸同余作為等價關(guān)系，將無限整數(shù)集轉(zhuǎn)化為有限剩余類，簡化了數(shù)論研究。同余的核心價值01歐拉函數(shù)在密碼學(xué)與數(shù)論中起著橋