標籤：

AMC 初等數論數學

AMC、HMMT、PUMaC數論Number Theory知識補充

05-16

AMC、HMMT、PUMaC數論Number Theory知識補充

來自專欄 Kenny的數學物理分享

數論與平常數學學習有一定距離，給各位考AMC的同學做一些知識補充。

一、廢話部分

Fundamental Theorem of Arithmetic 算術基本定理：

任何一個大於1的自然數，都可以唯一分解成有限個質數的乘積。

Every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers in a unique representation, up to the order of the factors.

二、數論中三個重要的積性函數Multiplicative function

*積性函數Multiplicative function 的定義：

$I!f ;gcdleft( m,n ight)=1$

$then ; f!left( mn ight)=f!left( m ight)cdot f!left( n ight)$

$x=prod_{i=1}^{n}p_{i}^{k_{i}}=p_{1}^{k_{1}}! cdot p_{2}^{k_{2}} cdot ...cdotp_{n}^{k_{n}}$

1、 $auleft( x ight)$ 約數個數函數 number of positive divisors:

$auleft( x ight) =prod_{i=1}^{n}k_{i}+1=left( k_{1} +1 ight)cdot left( k_{2} +1 ight) cdot ...cdot left( k_{n} +1 ight)$

各質因數指數加一相乘，十分重要，常用。

簡單證明：簡單的排列組合，不詳細敘述

2、 $sigmaleft( x ight)$ 約數和函數 sum of positive divisors：

$sigmaleft( x ight)=prod_{i=1}^{n}sum_{j=0}^{k_{i}}{left( p_{i} ight)^{j}}=prod_{i=1}^{n}frac{left( p_{i} ight)^{k_{i}+1}-1}{p_{i}-1}$

看著複雜，不好說清，舉個例子：

$100=2^{2} imes 5^{2}$

約數和為 $sigmaleft( 100 ight)=left( 1+2+2^{2} ight)left( 1+5+5^{2} ight)=217$

較為重要

證明：不同的組合遍歷所有約數，不詳細說明

3、 $phileft( x ight)$ 歐拉函數 number of positive integers that less than $x$ relatively prime to $x$ :

$phileft( x ight)=xcdotprod_{i=1}^{n}left( 1-frac{1}{p_{i}} ight)$

AMC中極少出現，HMMT及PUMaC中出現。主要用來求模運算中的逆元

證明：由於質數冪的互質數易求，因此利用積性函數特性將書分解為質數冪的乘積即可。

三、同餘

$定義a的逆元a^*為:acdot a^{*}equiv1;left ( mod; p ight)$

1、Wilsons theorem

$left( p-1 ight)!equiv-1;left ( mod; p ight)$

簡單證明思路：除1和p-1外，剩下兩兩互為逆元，構成完全剩餘系

2、Fermats theorem費馬小定理

$I!f ;gcdleft( n,p ight)=1 ;and;p;is;a;prime;number$

$n^{left( p-1 ight)}equiv1;left ( mod; p ight)$

常用於計算逆元

證明困難，需要簡單群論知識，這裡不敘述思路

3、Eulers theorem歐拉函數定理

$I!f ;gcdleft( m,n ight)=1$

$m^{phileft( n ight)}equiv1;left ( mod; n ight)$

費馬小定理的general形式，經常用於計算逆元及消去線性同餘方程中的係數

四、線性同餘方程

1、利用Euclidean algorithm輾轉相除法

$I!f ;gcdleft( m,n ight)=1;and; m=qn+1$

$Rightarrow m-qn=1$

$ncdotleft( -q ight)equiv 1;left( mod ;n ight)$

$-q$ 為 $n$ 的逆元

2、利用Eulers theorem歐拉函數定理

$kx+bequiv c; left( mod;m ight)Rightarrow kxequiv c-b; left( mod;m ight)$

$I!f ;gcdleft( k,m ight)=1$

$k^{phileft( n ight)-1}cdot kxequiv left( c-b ight)k^{phileft( n ight)-1};left ( mod; n ight)$

$xequiv left( c-b ight)k^{phileft( n ight)-1};left ( mod; n ight)$

3、解線性同餘方程組：

中華剩餘定理Chinese congruence theorem

思路：先解每個方程再兩兩湊

祝大家AMC、HMMT考出好成績！有任何問題歡迎私信我kennyja@126.com

推薦閱讀：

※【2016新劇推薦】《Preacher：傳教士》第一季第一集影評：暴力血腥的黑色幽默冒險
※如何評價 AMC 新劇《傳教士》(Preacher)？
※《行屍走肉》S8回顧+預熱：全面戰爭
※如何評價《行屍走肉》第六季第一集？

TAG:數學 | 初等數論 | AMC |