数论学习笔记

性质定理

辗转相除

$(qn+r,n)=(r,n)$
$(a,b)=(a\pm b,b)=(a,b\pm a)$

分数性质

分数一定为有限小数或者无限循环小数
若分母p含有质因数2和5，则肯定是有限小数
若分母p不含质因数2和5，则只需证明 $\frac{m}{p}$ 可以写成 $\frac{n}{999...}$ 的形式，那么该分数即为无限循环小数
先证明一个引理：
若p为质数且 $p\geq7$，则 $9,99,999,...,999...99$ 中一定有p的倍数
用反证法证明：
若没有p的倍数，则有 $a_i\equiv a_j (mod\ p)$ ($a_i>a_j$)
$a_i-a_j \equiv 999...9000...00 \equiv 0 (mod\ p)$
则 $p|999...99$
矛盾，得证
则 $\frac{m}{p}$ 可以写成 $\frac{n}{999...}$ 的形式
$\frac{1}{9}=0.1111...$
$\frac{1}{99}=0.010101...$
$\frac{1}{999}=0.001001001...$
$\frac{n}{999...}$ 可以写成 $0.abcd..$ 的循环，证毕

费马小定理

若 $(a,p)=1$ 且p为质数，则有：

• $a^{p-1}\equiv 1(mod\ p)$

首先证明一个引理：
对于m的一组完系：$a_1,a_2,...,a_m$ 若 $(k,m)=1$ 则 $ka_1,ka_2,...,ka_m$ 也为m的一组完系
使用反证法证明：
若 $ka_1,ka_2,...,ka_m$ 不为m的一组完系，由抽屉原理可得必有 $ka_i \equiv ka_j (mod\ m)$
得：$k(a_i-a_j)\equiv 0\ (mod\ m)$
由 $(k,m)=1$ 知 $p|(a_i-a_j)$
矛盾，证毕
$0,1,2,...,p-1$ 为模p的一组完系
由上述引理可知：$0,a,2a,...,a(p-1)$ 也为模p的一组完系
得：$(p-1)!\equiv a^{p-1}(p-1)!\ (mod\ p)$
$(p-1)!(a^{p-1}-1)\equiv 0\ (mod\ p)$
$p|(p-1)!(a^{p-1}-1)$
又p为质数，则$p|(a^{p-1}-1)$ 得证

裴蜀定理

已知 (a,b)=d，则对于任意整数 x,y，都满足 $ax+by=kd(k\in Z)$
特别地，存在 x,y 使得 $ax+by=d$

毕达哥拉斯三角形

概念：三边均为整数的三角形
令三边分别为 a,b,c
则三边平方关系一定有 奇+偶=奇，不会出现其它情况
取任意正整数 m,n，且(m,n)=1，m>n $k\in N^*$
通解为：
$~~~~~~~~~~~$ $a=k(2mn)$
$~~~~~~~~~~~$ $b=k(m^2-n^2)$
$~~~~~~~~~~~$ $c=k(m^2+n^2)$

欧拉函数 $\phi(n)$

特别地，我们有 (0,1)=1
当 $n\geq2$ 时，(0,n)≠1
$\phi(1)=\phi(2)=1$
对于大于等于 3 的整数 $\phi(n)\geq2$
当 p 为质数时，有：
① $(p,m)=1\iff(p^n,m)=1$
② $\phi(p^n)=p^n-p^{n-1}$

解法

已知 (m,n) 和 [m,n] 求 m，n

例：已知 (m,n)=12，[m,n]=72，求 m，n，其中 $m>n$
设 $m=12m_1,n=12n_1$，$(m,n)=1$
$[m,n]=[12m_1,12n_1]=12[m_1,n_1]=72$
$[m_1,n_1]=6$
① $m_1=3,n_1=2$ ② $m_1=6,n_1=1$
代入求解即可
核心思路是缩小取值范围

求不定方程通解

$ax+by=c$
令 $x_0,y_0$ 为不定方程特殊解
令原方程为 $ax'+by'=0$
得到 $x'=-\frac{b}{(a,b)}t$，$y'=\frac{a}{(a,b)}t$ 其中 $t \in Z$
通解为：
$~~~~~~~~~~~~x=x_0+x'=x_0-\frac{b}{(a,b)}t$
$~~~~~~~~~~~~y=y_0+y'=y_0+\frac{a}{(a,b)}t$