Research Space for Linear Algebra & Discrete Mathematics
p整除(x+1)(x-1)所以p一定整除(x+1) or (x-1)這滿直觀的
p是質數則他必可整除x+1 or x-1因為拆成兩數相乘所以他必可整除其中之一然後X應該寫成X≡1 or -1比較好不過這邊我想順便請教一下助教不知道是不是我誤解這證明意思但是這題跟99清大資工那題有什麼關係呢?連想不起來 囧http://imageshack.us/photo/my-images/263/img3139ms.jpg/
是啦,我是懂可整除其中之一但在最後為什麼要讓X = 1 or -1而且還可以寫成X≡1 or -1比較好謝謝
p|(x+1) <=> x ≡ -1 mod pp|(x-1) <=> x ≡ 1 mod p你是問這個嗎?
thx, 你這樣寫我清楚多了非常感謝
99清大那一題, 根據費馬小定理, 7^28 = 1 mod 29因為 a^2 = 1 mod p 之解只有 a=1 or -1, 所以 7^14 和 7^7 有可能會是1, 然後再檢查到 7^7 = 1 mod 29 即可知 x = 7k, for all k in Z
張貼留言
6 則留言:
p整除(x+1)(x-1)
所以p一定整除(x+1) or (x-1)
這滿直觀的
p是質數
則他必可整除x+1 or x-1
因為拆成兩數相乘
所以他必可整除其中之一
然後X應該寫成X≡1 or -1比較好
不過這邊我想順便請教一下助教
不知道是不是我誤解這證明意思
但是這題跟99清大資工那題
有什麼關係呢?
連想不起來 囧
http://imageshack.us/photo/my-images/263/img3139ms.jpg/
是啦,我是懂可整除其中之一
但在最後為什麼要讓X = 1 or -1
而且還可以寫成X≡1 or -1比較好
謝謝
p|(x+1) <=> x ≡ -1 mod p
p|(x-1) <=> x ≡ 1 mod p
你是問這個嗎?
thx, 你這樣寫我清楚多了
非常感謝
99清大那一題, 根據費馬小定理,
7^28 = 1 mod 29
因為 a^2 = 1 mod p 之解只有 a=1 or -1,
所以 7^14 和 7^7 有可能會是1,
然後再檢查到 7^7 = 1 mod 29
即可知 x = 7k, for all k in Z
張貼留言