推 mixxim :這題會用到費馬小定理與primitive root的性質 04/03 23:02
→ Sfly :gcd(k,p-1)=1 => km+(p-1)n=1 for some int m,n 04/04 23:49
→ Sfly :then x=a^m is a solution for x^k=a mod p. 04/04 23:50
對於 x^k = a mod p ，p為質數，x,k為整數
對於任何a且1<=a<p，x必有解的條件為 gcd(k, p-1)=1
若gcd(k, p-1)>1 則對任一a且1<=a<p，x不一定有解
例如，x^2= 6 mod 11，找不到任何整數x可以滿足此算式，因為gcd(2,11-1)=2 > 1
但若 x^3=6 mod 11，則可以找到 8^3=6 mod 11，因為 gcd(3, 11-1)=1
有人可以證明此性質嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.185.69.173