#创作计划# 同余问题

Srobot

2025-12-13 21:10:27

发布于：广东

9阅读

0回复

0点赞

一、同余概述

1、基本定理

定义：给定正整数 $m,a,b$ ，若 $m\ mod\ a=m\ mod\ b$ ，则称 $a$ 和 $b$ 对模 $m$ 同余，记作 $a≡b\ (mod\ m)$ ，并称该式子为同余式；否则称 $a$ 和 $b$ 对模 $m$ 不同余。
费马小定理：若 $p$ 是质数，则 $\forall a\in N^+,a^p≡a\ (mod\ p)$ 。
欧拉定理：若正整数 $a,b$ 互质，则 $a^{\phi(b)}≡1\ (mod\ b)$ ，其中 $\phi(b)$ 为欧拉函数，其定义为：若正整数 $x$ 有 $m$ 个不同质因数，分别记为 $p_1,p_2,...p_{m-1},p_m$ ，则 $\phi(x)=x\prod_{i=1}^{m}(1-\frac{1}{p_i})$ 。

2、同余性质

对于正整数 $a,b,c,m$ ，对模 $m$ 同余满足：

$a≡a\ (mod\ m)$
$a≡b\ (mod\ m)\Rightarrow b≡a\ (mod\ m)$
$a≡b\ (mod\ m),b≡c\ (mod\ m)\Rightarrow a≡c\ (mod\ m)$
$a≡b\ (mod\ m)\Rightarrow a+c≡b+c\ (mod\ m)$
$a≡b\ (mod\ m),c≡d\ (mod\ m)\Rightarrow ac≡bd\ (mod\ m)$
$a≡b\ (mod\ m)\Rightarrow a^c≡b^c\ (mod\ m)$
$a≡b\ (mod\ m),gcd(a,b)=1\Rightarrow a≡ab\ (mod\ m)$

二、算法扩展

欧几里得算法： $\forall a,b\in N,gcd(a,b)=gcd(b,a\ mod\ b)$ 。
定理：设 $a,b$ 不全为 $0$ ，则 $\exists x,y\in N,ax+by=gcd(a,b)$ 。
代码实现（求解 $ax+by=gcd(a,b)=d$ 的一组解 $x,y$ ）：

void ed(int a,int b,int &d,int &x,int &y){
    if(b==0){
        d=a;
        x=1;
        y=0;
    }
    else{
        ed(b,a%b,d,x,y);
        int t=x;
        x=y;
        y=t-(a/b)*y;
    }
}