Question

关于同余问题。求教。

http://zhidao.baidu.com/question/175971648.html?si=1 关于这道题。
这里面的最佳答案中的3^38=3^32*3^6≡1*9*(-4)≡15(mod17) 不理解。因为完全是刚接触。希望详细的解释。

Answer 1

从你提到的问题那里复制了一些文字，作了重排。以下也用==代替≡.
题：解释 3^38=3^32*3^6≡1*9*(-4)≡15(mod17)
答：
a≡b(modm),c≡d(modm) 则ac≡bd(modm)
推论：a≡b(modm),则a^n≡b^n(modm).(即同余式两端取乘幂仍成立)

利用以上知识得到：
3^2≡9(mod17),(两边平方得下一式，以下类似)
3^4≡81≡-4(mod17)
3^8≡16≡-1(mod17)
3^16≡1(mod17)
如果利用费马小定理，可以立即得到3^16≡1(mod17)
于是：
3^38==3^32*3^6≡1*9*(-4)≡15(mod17)
其中3^32==(3^16)^2==1^2==1;
3^6==(3^2)*(3^4)==9*(-4)==-2==15

注：费马小定理：质数p不整除a,则：a^(p-1)≡1(modp)

附：对于非素数模(除数)m求余，还要用到费马小定理的推广：
欧拉函数定理：(a,m)=1,则a^φ(m)=1 mod m
φ(m)是欧拉函数，是不大于m且与m互素的正整数的个数。
比如：3^406 mod 14
小于14与14互质的自然数有6个(可以列举出来1,3,5,9,11,13；复杂的m有公式计算这个个数φ(m))，即φ(14)=6
于是：3^6==1 mod 14.
而406=6k+4
故3^406==3^4==81==11 mod 14.