Re: [代數] 一題數論

[yueayase (scrya)]

※ 引述《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)
→ Vulpix      :a是ring Z_n的unit，所以在unit group裡面，由條件
→ Vulpix      :知道a的order是n-1，代表Z_n\{0}都是unit。
→ Vulpix      :所以n不能有proper divisor，否則Z_n就有zero div.了
推 bajifox     :哈哈太感謝了