数论学习笔记

整除

  1. 定义:$b=aq \Rightarrow a | b$
  2. 5个性质
    • 传递性:$a|b, b|c \Rightarrow a|c$
    • $a|b, a|c \Rightarrow a|(bx+cy)$
    • $a|b \Rightarrow ma|mb(m \neq 0)$
    • $ax+by=1,a|n,b|n \Rightarrow ab|n$ (证明如下,利用以上两个性质)    $$a|n,b|n \Rightarrow ab|bn, ba|an \Rightarrow ab|(an \cdot x + bn \cdot y) \Rightarrow ab|n(ax+by) \Rightarrow ab|n$$
    • $(b=qd+c \rightarrow d|b) \Longleftrightarrow (d|c)$
  3. 一些有用的结论
    • $2|a$:2能整除a的末位
    • $4|a$:4能整除a的末2位
    • $8|a$:8能整除a的末3位
    • $3|a$:3能整除a的各位之和
    • $9|a$:9能整除a的各位之和
    • $11|a$:11能整除a的偶数位和与奇数位和的差
    • $7|a, 11|a, 13|a$:末3位对应的数与末3位之前的数对应的数之差能被7、11、13整除
  4. 二元一次不定方程的整数解
    • $ax+by=c(a,b,c,x,y \in Z)$有解的充要条件是$gcd(a,b)|c$(证明如下)$$ax+by=c \xrightarrow[]{g=gcd(a,b)}  k_1 \cdot  gx+ k_2 \cdot gy=c \Rightarrow g(k_1x+k_2y)=c \Rightarrow g|c$$
    • 设$x_0, y_0$为特解,则通解为 $$x=x_0+\frac{b}{g}t, y=y_0-\frac{a}{g}t$$

同余

  1. 定义:$a-b=mk(k|a-b) \Longleftrightarrow  a \mod m = b \mod m \Longleftrightarrow  a \equiv b (\mod m)$
  2. 6个性质,2个推论
    • 自反性:$a\equiv a(\mod m)$
    • 对称性:$a\equiv b(\mod m) \Rightarrow b\equiv a(\mod m)$
    • 传递性:$a\equiv b(\mod m), b\equiv c(\mod m) \Rightarrow a\equiv c(\mod m)$
    • 同加性:$a\equiv b(\mod m) \Rightarrow a+c\equiv b+c(\mod m)$
    • 同乘性:
      • $a\equiv b(\mod m) \Rightarrow ac\equiv bc(\mod m)$
      • $a\equiv b(\mod m),c\equiv d(\mod m) \Rightarrow ac\equiv bd(\mod m)$
    • 同幂性:$a\equiv b(\mod m) \Rightarrow a^n\equiv b^n(\mod m)$
    • 推论一:
      • $(a+b) \mod c = [(a \mod c) + (b \mod c)] \mod c$
      • $(a\times b) \mod c = [(a \mod c) \times (b \mod c)] \mod c$
    • 推论二:$a \mod p = x, a \mod q = x, gcd(p,q)=1 \Rightarrow a \mod pq = x$

GCD和LCM

  1. $gcd(a,b)=gcd(a,b-a)=gcd(b,a \mod b)$ (辗转相除/二进制求法)
  2. $lcm(a,b)=\frac{ab}{gcd(a,b)}$
  3. 扩展欧几里得算法

说点什么

avatar
50
  Subscribe  
提醒