Re: [代數] 一題數論證明
※ 引述《utomaya (烏托馬雅)》之銘言：
: 對於 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
: 有人可以證明此性質嗎？
我們證明當 gcd(k, p-1)=1 時原同餘方程必有解
Proof.
設 g 為模 p 的 primitive root(原根)，我們設整數 L 使得 g^L ≡ a (mod p)
由於 gcd(k, p-1)=1，存在整數 m、n 使得 mk + n(p-1) = 1
故 a ≡ g^L ≡ g ^ [mk + n(p-1)]L ≡ g^(mkL) (mod p)
(↑費馬小定理)
可見 x ≡ g^(mL) 為原方程一解
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.251.61
※ 編輯: mixxim 來自: 140.112.251.61 (04/03 23:13)
→
04/03 23:20, , 1F
04/03 23:20, 1F
討論串 (同標題文章)