Re: [代數] 一題數論
※ 引述《bajifox (嘖)》之銘言：
: let a and n>1 be any integers such that a^(n-1)≡1(mod n)
: but a^d not≡ 1 for every proper divisor d of n-1
: ^^^^^
: 表示不同餘 XD
: prove that n is a prime
: 哈哈不太知道怎麽做
: 謝謝
Suppose n is not a prime.
Since a^(n-1)≡1(mod n), a is not divisible by n.
φ(n)
By Euler's Theorem, a ≡ 1(mod n)
Note that φ(n) < n - 1 since there is a number k < that divides n.
By assumption, a^d not≡ 1 for every proper divisor d of n-1
So, the order of a modulo n is n-1.
(If not, let k < n-1 be the order of a modulo n. Then k | n-1
since a^(n-1)≡ 1(mod n), which contradicts the above assumption.)
Then, n-1 | φ(n).
However, φ(n) < n-1. Then, φ(n) can't be divisible y n-1. A contradiction!
So, n is a prime.
Remark:
(1)其實可以改成直接證明法, 利用φ(n) ≦ n-1 for all n 和 n-1 | φ(n)
可得到 φ(n) = n-1 => n 是質數
(2)感覺可以用Z 這個cyclic group來得出n is a prime, 但我不熟, 不確定怎麼寫
n
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.251.163.216
※ 編輯: yueayase 來自: 111.251.163.216 (06/08 00:27)
→
06/08 00:50, , 1F
06/08 00:50, 1F
→
06/08 00:52, , 2F
06/08 00:52, 2F
→
06/08 00:54, , 3F
06/08 00:54, 3F
推
06/09 11:42, , 4F
06/09 11:42, 4F
討論串 (同標題文章)