※ 引述《Desperato (Farewell)》之銘言:
: ※ 引述《cuttlefish (無聊ing ><^> .o O)》之銘言:
: : 試證明對每一個質數p, 存在質數q, 使得gcd(n^p-p, q)=1 對所有的正整數n.
: : 謝謝
: 做不出來(攤手)
: 原題可改寫為 given prime p, exists some prime q
: n^p != p (mod q) for all n = 0, 1, ... , q-1
: 由於只是要找到這麼一個 q, 所以就到處抄公式(欸),反正有就好(?
: 首先 by primitive root theorem, 只要 q 是個 prime 則
: Z_q^x = {1, 2, ..., q-1} 是個 cyclic group
: 也就是說存在 k (稱為 primitive root of q)
: 使得 k^(q-1) = 1 但 k^t != 1, t=1,..., q-1
: 如果 p 不整除 q-1 的話, f : Z_q^x -> Z_q^x 就會是 bijection
: n |-> n^p = f(n)
: 那就無法避免有個 n^p 會對到 p 了
: 因此 p 必須要整除 q-1, q = kp + 1
: 此時只要 p 不在 Im(f) 裡面
: 就不會有 n^p 對到 p,那就沒問題了
: 這個時候 ord(p) (本來就)整除 q-1, 但是不整除 k = (q-1)/p
這邊不知道是我誤會 還是您寫錯了
ord(p)|q-1, ord(p)!|(q-1)/p 應該推得ord(p)|p才對
換言之 ord(p)=1 or p
但是我不確定你的ord(p)是什麼意思
所以就沒辦法繼續做下去了
: 也就是說 ord(p) 和 q-1 有一樣多個 p 當因數
: 一個比較強的情況 就是 ord(p) = q-1, 也就是 p 自己就是 primitive root
: ok, 卡住了(欸
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.217.39
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1501408200.A.21E.html