设m>1,x,y和g都是正整数,且gcd(g,m)=1.如果x ≡y(modφ(m)),求证gx ≡gy(mod m).
问题描述：
设m>1,x,y和g都是正整数,且gcd(g,m)=1.如果x ≡y(modφ(m)),求证gx ≡gy(mod m).
答
应该是证明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).两边...