同余与同余方程(扩展欧几里得)

同余与同余方程(扩展欧几里得)

同余应该是数论中比较基础的一个东西了。感觉挺重要的。。。高中没学好到大学来补了。

涉及3个数，a,b,m。就是a % m == b % m.

可以写成：a  b(mod m)。

一、同余及其一些性质

同余有一些显然性质，有的时候会有很大功效。(不列举了，一般书上都有的)。

例1：给定整数n,m,k.求n^m mod k的值。m,n,k*k为长整型范围内的自然数。

这样的题根据数据类型有不同的解法：

这里m还在数据类型可表示的范围内，当m极大时，就要用到欧拉降幂这个东西。

这里说一下m还在数据类型可存储范围内的做法。

n^1   n (mod k)

n^2   (n mod 7) * (n mod 7) mod 7

n^4   (n^2 mod 7) * (n^2 mod 7) mod 7

......

将m进行二进制分解，然后递推得到结果，当然递归