[代數] 二次剩餘

[justinj (黑旋風)]

似乎沒看到有人有推廣(是因為沒什麼用處?)

通用定義:
  φ(n):與n互質的個數
  (a,n)=1
  (m,n)=1

1. a^φ(n)=1(mod n)

2. x^2=a(mod n) 有解,則a^(φ(n)/2)=1(mod n)
                無解,則a^(φ(n)/2)=-1(mod n)

3.當n>2 , 2|φ(n)

4.小於n/2的與n互質個數為φ(n)/2

5.當2|m,     m        φ(n)/2
           (---) =(-1)
             n

6.m,n都是奇數時,    m    n         φ(m)*φ(n)/4
                  (---)(---) = (-1)
                    n    m


以上證明看高斯的證明換過去就好了..

--
　　         /\/.      ◢◣   \\/.
　　,\//,   //o\,\//,.\//\█◣ /o\\   ,\/,,\/
　　//o\◢◣  | //o\\/o//o\\█◣|◢◣ //o\/o\.//,
　　 |◢██◣| ◣|   |  |██████◣|  | \o\\
　　◢██████|◣◢█|███████◣ |  |

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.40.36.239
※ 文章網址: http://www.ptt.cc/bbs/Math/M.1408408798.A.1EC.html
→ hatebnn     : 可應用在代數編碼學、密碼學
→ hatebnn     : 二次互反律的證明有幾百個，Eisenstein的證明較高斯
→ hatebnn     : 的簡易明瞭(計算格點的做法)