同余

同余（英语：Congruence modulo，符号：≡）在数学中是指数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。最先引用同余的概念与“≡”符号者为德国数学家高斯。

$a\equiv b\mod m$

整除性

$a\equiv b\mod m\Rightarrow m|(a-b)$

即是说 a 和 b 之差是 m 的倍数

同余可以用来检验一个数是否可以整除另外一个数，见整除规则。

传递性

保持基本运算

保持：加、减、乘、乘方

不行：除法、开方

乘法逆元

除法的解决方案

费马小定理求乘法逆元：

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有

$a^{p-1}≡1\mod p$

则有：

$a^{-1}≡a^{p-2}\mod p$

常见的大质数：

1e9+7, 1e9+9

633. Sum of Square Numbers

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

public boolean judgeSquareSum(int c) {
    for (int i = 0; i * i <= c / 2; i++) {
        int b = (int) Math.sqrt(c - i * i);
        if (b * b == c - i * i) {
            return true;
        }
    }

    return false;
}

public boolean judgeSquareSum(int c) {
    for (int i = 2; i * i <= c; i++) {
        int count = 0;
        if (c % i == 0) {
            while (c % i == 0) {
                count++;
                c /= i;
            }
            if (i % 4 == 3 && count % 2 != 0) return false;
        }
    }
    return c % 4 != 3;
}