文章来源: http://thunderfyc.wordpress.com.cn  

最小自然数原理
      任何一个非空正整数集C有最小元素

证明第一数学归纳法
    设命题A1~An
    任意正整数Ar为真 能推出Ar+1为真
    A1为真
    假设{A}中有一个不为真 使得An不为真的全体正整数集C非空
    则C中有一个最小整数p 且p>1 因此Ap不为真，但Ap-1为真 矛盾

证明素数无穷 与构造素数的方法
    假设素数有限 为P1~Pn
    则A=p1p2…..pn+1
    A>π 所以A为合数 任意π去除余1 A为素数
    假设不成立
    A为素数 

文章来源: http://thunderfyc.wordpress.com.cn 

素数分解唯一性
    设存在最小m=p1p2..pr = q1q2..qs 有两种
    令p1<=p2<=…<=pr
      q1<=q2<=…<=qs
    p1!=q1 否则 存在更小m’=m/p1 矛盾
    不妨假设p1<q1
    令m’=m-(p1q2…qs)
      m’=p1(p2p3…pr-q2q3…qs)
      m’=(q1-p1)q2q3…qs
      m’<m 所以 m’分解有唯一性
      q2>=q1>p1 所以p1为q1-p1因子
      hp1=q1-p1 则p1是q1因子 q1是素数 矛盾
    假设不成立。

ln n 定义 函数y=x^-1从x=1到x=n的面积

设A_n为[1,n]中素数的个数，那么A_n/n ~ 1/ln n

10 = -1(mod 11) 10^2 = 1(mod 11)  10^3 = -1(mod 11)
Z = a_0 + a_1 * 10 + a_2 * 10^2 +…+ a_n * 10^n
Z mod 11 = a_0 - a_1 + a_2 - a_3 +….

费马小定理
    a^p-1 = 1 (mod p) p为素数 p不整除a
证明
    m_1 = a
    m_2 = 2a
    m_p-1 = (p-1)a

    任意两数对p不同余，否则存在r<s，使得p为m_s - m_r = (s-r)a 因子s-r <p => p | a

    m_1*m_2*…*m_p-1 = 1*2*3 *…*(p-1)*a^(p-1) = 1*2*3…*(p-1) (mod p)
    (p-1)! *(a^(p-1) - 1) = 0 ( mod p)
    a^(p-1) - 1 = 0 (mod p)

一个数a 如果不是p的倍数且模p同余某数平方 a为p的二次剩余
不是p的倍数的b不同余于任何数平方 为非二次剩余

a^((p-1)/2) = 1(mod p)
b^((p-1)/2) = -1(mod p)
1~p-1中有(p-1)/2 二次剩余 (p-1)/2 非二次剩余

二次互反律
    p q为素数，若(p-1)/2*(q-1)/2为偶 q是p的非二次剩余 <=> p是q的二次剩余
               若(p-1)/2*(q-1)/2为积 p是q的二次剩余 <=>q是p的非二次剩余

毕达哥拉斯三元数
    a = v^2 - u^2
    b = 2uv             (u, v) = 1
    c = u^2 + v^2       u*v 为偶
费马大定理
    n>2时 a^n + b^n = c^n 无正整数解

欧几里德除法
 gcd(a, b) = gcd(b, a mod b)

若素数p整除ab 则 p | a  或 p | b
若p不整除a (a, p) = 1 则存在整数k l 使得 1 = ka + lp

若d = (a, b)
则存在 d = ka + lb

连分数
    840 = 1*611+229
    611 = 2*229+153
    229 = 1*153 +76
    153 = 2*76 + 1
    840/611 = 1 + 229/611 = 1 + 1/(611/229) = 1 + 1/(2 + 1/(229/153)) = 1 + 1 / (2 + 1 / (1 + 1/(2+(1/76))))

线性丢番图方程
 ax+by = c (a, b)|c时有解

素数分解唯一性
欧拉函数
 φ(n) = n*(1-1/p_1)*(1-1/p_2)*…*(1-1/p_n) p为素因子 φ(n)为比n小的与n互素的数个数
 a^φ(n) = 1 (mod n)  (a, n) = 1

n = p_1^a_1 * p_2^a_2…*p_r^a_r 因数个数为(a_1+1)(a_2+1)…(a_r+1)
因数和(1+p1+p1^2+…p1^a_1)….

文章来源: http://thunderfyc.wordpress.com.cn