- 鐵幣
- 12884 元
- 文章
- 4264 篇
- 聲望
- 2890 枚
- 上次登入
- 19-4-25
- 精華
- 10
- 註冊時間
- 05-11-19
- UID
- 208572
|
If p = 2, then we can take q = 3, since squares cannot be 2 mod 3. So suppose p is odd.
Consider N = 1 + p + p^2 + ... + p^(p-1). There are p terms. Since p is odd, that means an odd number of odd terms,
so N is odd. Also N = p + 1 mod p^2, which is not 1 mod p^2, so N must have a prime factor q which is not 1 mod
p^2.
We will show that q has the required property.
Since N = 1 mod p, p does not divide N, so q cannot be p. If p = 1 mod q, then N = 1 + 1 + ... + 1 = p mod q.
Since N = 0 mod q, that implies q divides p. Contradiction. So q does not divide p - 1.
Now suppose n^p = p mod q (*). We have just shown that n cannot be 1 mod q. We have also shown that q is not p, so n cannot be a multiple of q. So assume n is not 0 or 1 mod q. Take the pth power of both sides of (*). Since (p - 1)N = p^(p - 1), we have p^p = 1 mod q. So n to the power of p^2 is 1 mod q. But n^q= q mod q (the well-known Fermat little theorem). So if d = gcd(q-1, p^2), then nd = 1 mod q. We chose q so that q-1 is not divisible by p^2, so d must be 1 or p. But we are assuming n is not 1 mod q, so d cannot be 1. So it must be p. In other words, n^p = 1 mod q. But n^p = p mod q, so p = 1 mod q. Contradiction (we showed above that q does not divide p - 1).
鬥不過，所以放上詳解
版主戰敗(泣
[ 本文最後由 M.N.M. 於 07-4-2 11:55 PM 編輯 ] |
|
樓主: M.N.M.
傳送訊息
發表於 07-4-2 23:39:18
