同余入门
同余定义：
a%m==b%m 则称a同余b（在%m的情况下） （a≡b(mod m)）
它满足以下3条性质：
1.自反性：一个数永远与自身同余
2.交换律：a≡b(mod m) --> b≡a(mod m)
3.传递性：a≡b(mod m) b≡c(mod m) --> a≡c(mod m)
引理1： (b-a)%m==0 --> a≡b (mod m)
证明： 对于一个数a，a+km≡a(mod m)
同时，我们让a<b时，a+km中有一个会是b，即b=a+km，得证
引理2： a≡b (mod m) gcd(a,m)=1 --> gcd(b,m)=1
证明：
设a=mp+k,b=mq+k
因为a，m互质，所以k不会是m的因数,gcd(k,m)=1
所以gcd(b,m)=gcd(mq+k,m)=gcd(m,k)=1,得证
定理1： a≡b (mod m) , x≡y(mod m) --> a+x≡b+y(mod m)
设a=mp+k1,b=mq+k1,x=mr+k2,y=ms+k2
a+x=mp+mr+k1+k2
b+y=mq+ms+k1+k2
(a+x)-(b+y)=mp+mr-mq-ms=m(p+r-q-s)%m==0
∴a+x≡b+y(mod m)
定理2： a≡b(mod m) , x≡y(mod m) --> ax≡by(mod m)
证明：
设a=mp+k1,b=mq+k1,x=mr+k2,y=ms+k2
ax=mpmr+mrk1+mpk2+k1k2
by=mqms+msk1+mqk2+k1k2
ax-by=(mpmr+mrk1+mpk2-mqms-msk1-mqk2)%m==0
∴ax≡by(mod m)
定理3： ac≡bc(mod m),gcd(c,m)=1 --> a≡b(mod m)
证明：
设ac=mp+k,bc=mq+k
ac-bc=m(p-q)
c(a-b)%m=0
∵gcd(c,m)=1
∴(a-b)%m=0
∴a≡b(mod m)
定理4： ac≡bd , c≡d(mod m) , gcd(c,m)=1
∵c≡d(mod m)
∴bc≡bd(mod m)
∵ac≡bd,bd≡bc(mod m)
∴ac≡bc(mod m)
∴a≡b(mod m)
定理5： a≡b(mod p) a≡b(mod q) ,gcd(p,q)==1 --> a≡b(mod pq)
同余的基本性质定理大致在此，希望能给大家的数论打一个良好的基础