关于同余的总结

一、一些重要的定义和定理

如果是的一个因子，就说和关于同余，并记为，也等价于。

如果,那么就叫做模的一个剩余

如果，那么就称为模的一个最小剩余

由与某个给定的剩余同余的所有数组成的一个类叫做同余类

同余类的每个成员都叫做这个类的一个代表

总共有 个同余类, 它们分别以 作为代表, 任何 个分别属于这 个剩余类的数组成一个集合, 称为模 的一个完全剩余系, 简称完系。(剩余系的概念在线性同余方程种有应用)

如果那么

如果，那么

(重要!)如果是模的一个完全剩余系，且有,那么也是模的一个完全剩余系。更一般地，也是完全剩余系。

设为模的完全剩余系。根据完全剩余系定义，这组整数模两两不同余。要证明：也是模的一组完全剩余系，只需要证明这个数模两两不同余即可。

反证法：假设存在和，使得则有。由于,所以，即.这与模两两不同余矛盾了。

因此证得：模两两不同余。

补充：的应用

I. Rise of Shadows

思路：追击问题，我们以时针作为参照物(静止不动),相对运动速度针对分针分析。

相当于分针相对于时针以每分钟的速度运动。

其中

那么柿子转化为：

即：

根据剩余定理：如果是模的一个完全剩余系，且有,那么也是模的一个完全剩余系。更一般地，也是完全剩余系。

为满足互质条件，同除，那么

那么：

同时

接下来只需求解出的整数解的个数。

因为是的完全剩余系，又,那么也是构成模意义下的完全剩余系。

由于之后余数，因此一共又，一共个，并且无重复。即于余数值一一对应。在中一共有个。

再把还原到,答案就是个。

注意特判：，此时所有都满足，答案是。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll H,M,A;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>H>>M>>A;
    if(2*A==H*M)cout<<H*M<<"\n";
    else
    {
        //(H-1)t mod HM = |A|
        ll g = __gcd(H-1,H*M);
        cout<<(2*(A/g)+1)*g<<"\n";
    }
    return 0;
}

二、一元线性同余方程

研究线性同余方程有什么用处？

表示是的倍数，设为倍，则有.

所以，求解一元线性同余方程等价于求二元线性丢番图方程。