推 edgar111 : 我看到n^p-p的第一直覺是費馬小定理 不知道有沒有用 07/27 15:44
我也是 不過費馬小定理只有 n^(p-1) = 1 的情況
這題 n^p - p 需要更詳細的資訊
※ 編輯: Desperato (140.112.25.105), 07/27/2017 16:38:00
※ 引述《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 有一樣多個 p 當因數
一個比較強的情況 就是 ord(p) = q-1, 也就是 p 自己就是 primitive root
ok, 卡住了(欸
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1501140421.A.D76.html