Question

请问这个mod函数怎么计算，麻烦大神讲解尽量详细一些，在下感觉不尽😃

Answer 1

设 x≡13-¹ (mod 99)，
则 13x≡1 (mod 99)，
由于 (13，99)≡1，所以由欧拉定理知
13^φ(99)≡1 (mod 99)，
因为 φ(99)＝φ(9)φ(11)＝6×10＝60，
所以 13^60≡1 (mod99)，
因此 13-¹≡x≡13^59 (mod 99)，
因为 13^59≡4^59≡(4³)^19 * 4²
≡(7×9＋1)^19 * 16≡1*7≡7(mod 9)，
13^59≡2^59≡(2^5)^11 * 2^4
≡(33-1)^11 * 16≡(-1)*5≡6(mod 11)，
所以由剩余定理得
13^59≡7*11*5＋6*9*5
≡655≡61(mod 99)，
也即 13-¹≡x≡61 (mod 99) 。