题目

设m>1,x,y和g都是正整数,且gcd(g,m)=1.如果x ≡y(modφ(m)),求证gx ≡gy(mod m).

提问时间：2021-03-17

答案

应该是证明g^x ≡ g^y (mod m).不妨设x ≥ y,由x ≡ y (mod φ(m)),存在正整数k使x-y = k·φ(m).由gcd(g,m) = 1,根据Fermat-Euler定理,有g^φ(m) ≡ 1 (mod m).因此g^(x-y) = (g^φ(m))^k ≡ 1^k = 1 (mod m).两边...