1、歡迎大家！歡迎大家！費(fèi)馬小定理和歐拉定理費(fèi)馬小定理和歐拉定理費(fèi)馬小定理是初等數(shù)論四大定理（威爾遜定理，歐拉定理（數(shù)論中的歐拉定理），中國(guó)剩余定理(又稱孫子定理)和費(fèi)馬小定理）之一，在初等數(shù)論中有著非常廣泛和重要的應(yīng)用。實(shí)際上，它是歐拉定理的一個(gè)特殊情況。知識(shí)背景費(fèi)馬小定理是初等數(shù)論四大定理（威爾遜定理，歐拉定理（數(shù)論中的我們知道模6的剩余類為：0 mod 6,1 mod 6,2 mod 6,3 mod 6,4 mod 6,5 mod 6.其中剩余類1 mod 6,5 mod 6里的所有數(shù)均與6互素，我們稱這兩個(gè)剩余類為與6互素的剩余類。給定模m，如果模m的一個(gè)剩余類里面的某個(gè)數(shù)與m互素，就把這

2、個(gè)剩余類叫作一個(gè)與模m互素的剩余類。新知學(xué)習(xí)我們知道模6的剩余類為：0 mod 6,1 mod 6,2 由此我們可知：在模3的剩余類中，1 mod 3,2 mod 3為與3互素的剩余類，在模4的剩余類中，1 mod 4,3 mod 4為與4互素的剩余類，等等。 我們已經(jīng)知道，1 mod 6,5 mod 6為所有與6互素的剩余類，那么我們?cè)谶@兩個(gè)剩余類中任取一個(gè)數(shù)，例如1和5，則由這兩個(gè)數(shù)組成的集合1,5，稱為模6的一個(gè)簡(jiǎn)化剩余系。新知學(xué)習(xí)由此我們可知：在模3的剩余類中，1 mod 3,2 mod 定義 在于模m互素的全部剩余類中，每一類中任取一數(shù)所組成的數(shù)的集合，叫作模m的一個(gè)簡(jiǎn)化剩余系。不難

3、得到：與模m互素的剩余類的個(gè)數(shù)是（m），模m的每一簡(jiǎn)化剩余系是由與m互素的（m）個(gè)對(duì)模m不同余的整數(shù)組成的。新知學(xué)習(xí)定義 在于模m互素的全部剩余類中，每一類中任取一數(shù)所組成的如果a1，a2，a（m）是模m的一個(gè)簡(jiǎn)化剩余系，并且（a，m）=1，那么aa1，aa2，aa（m）是也是模m的一個(gè)簡(jiǎn)化剩余系。新知學(xué)習(xí)如果a1，a2，a（m）是模m的一個(gè)簡(jiǎn)化剩余系，并且（歐拉定理 設(shè)m是一個(gè)大于1的整數(shù)，a是一個(gè)整數(shù)，且滿足條件（a，m）=1，則有：a 1（mod m）.（m）新知學(xué)習(xí)歐拉定理 設(shè)m是一個(gè)大于1的整數(shù)，a是一個(gè)整數(shù)，且滿足條件在歐拉定理中，若m是素?cái)?shù)p，由（P）=P-1便得到：費(fèi)馬小定理 設(shè)p為素?cái)?shù)，且（p，a）=1，則有：a 1（mod P）.P-1新知學(xué)習(xí)在歐拉定理中，若m是素?cái)?shù)p，由（P）=P-1費(fèi)馬小定理 典例分析例1：證明：典例分析例1：證明：典例分析典例分析解：例2：典例分析這樣的合數(shù)n存在，而且有無(wú)窮多個(gè)，其中最小的滿足條件的合數(shù)n=341=1131（是從兩個(gè)不同奇質(zhì)數(shù)作乘積去試算出來(lái)的。）事實(shí)上，由于210-1=1023=3413故 2101（mod341）所以 23401341（mod341），故341符合要求。解：例2：典例分析這樣的合數(shù)n