→ Sfly :你有些iff不太對 05/17 04:11
推 wsx02 :謝謝囉!! 05/17 20:44
→ yueayase :喔,x=7k 但 x 可能不是28的因數... 05/17 23:16
→ yueayase :應該只有7的order和某些7的倍數是28的因數 05/17 23:17
※ 引述《wsx02 ()》之銘言：
: x
: solve for x in 7 ≡1(mod 29)
: 28
: 這個直接套Fermat是 7 ≡1(mod 29)
: 然後下面這段我看不太懂
: 2
: 因為當a ≡1(mod 29)時, a≡1 or -1(mod 29)
: 所以必須考慮7^14及7^7在mod 29下有可能為1
: 答案是x = 7k
: 請問是28/2 = 14
: 14/2 = 7 這樣嗎?
: 這題有別的解法嗎? 是怕說萬一忘記除2會整個錯掉0.0
: 翻討論串有提到 直接去檢查28的因數 2.4.7.14會比較快 請問檢查28的因數就好?
: 謝謝
David M. Burton的Chapter 8:primitive roots and indices的p147~p148提到:
Definition: Let n > 1 and gcd(a,n) = 1. The order of a modulo n is the smallest
k
positive integer k such that a ≡ 1 (mod n)
Theorem: Let the integer a have order k modulo n (gcd(a,n)=1, n > 1).
h
Then a ≡ 1 (mod n) iff k | h; in particular k | φ(n)
Proof:
h
(=>) if a ≡ 1 (mod n), h = qk + r, 0 ≦ r < k by Division Algorithm.
qk+r qk r k q r r
=> a ≡ a a ≡ (a ) a ≡ a ≡ 1 (mod n) since a has order k
modulo n.
Then r must be 0. If not, k is not the order of a
since 0 ≦ r < k. k
(Note that k is the smallest positive integer such that a ≡ 1 (mod n)).
Thus, h = qk <=> k | h
(<=) if k | h, h = kq for some integer q.
h kq k q q
Then a ≡ a ≡ (a ) ≡ 1 ≡1 (mod n) -----------------(1)
since a has order k modulo n.
φ(n)
By Euler's Theorem, a ≡ 1 (mod n) since gcd(a,n) = 1, n≧1
=> k | φ(n)
x
用上面的性質和Fermat's Theorem, 就知道7 ≡ 1(mod 29) iff x | φ(29)=28
所以只要檢查28的因數(1,2,4,7,14,28)即可
2
7 ≡ 49 ≡ -9 (mod 29)
4
7 ≡ (-9)(-9) ≡ -6 (mod 29)
7
7 ≡ (-6)(-9)7 ≡ (-4)7 ≡ -28 ≡ 1 (mod 29) <- done!
=> 7 has order 7 modulo 29.
x
By (1), note that a ≡ 1 (mod 29) if 7 | x.
Thus, x = 7k, k ∈ Z
剛才忘記只要檢查28的因數,不用把不是因數的也算出來...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.161.149
※ 編輯: yueayase 來自: 111.251.161.149 (05/17 00:07)
※ 編輯: yueayase 來自: 111.251.161.149 (05/17 00:11)
※ 編輯: yueayase 來自: 111.251.161.149 (05/17 00:18)