威爾遜定理

来源:http://www.cnblogs.com/16er/archive/2016/01/26/5160244.html
-Advertisement-
Play Games

2016.1.26威爾遜定理證明:若p為質數,則p可整除(p-1)!+1First : 先把奇奇怪怪的取值試驗一下 若p=2,成立; 若p=3,成立; 那麼我們就開始研究p>=5的情況Second : 我們先來證明幾個結論 設A = {2,3,4,……,p-2} 設a∈A 記B = {a,2a,3a...


2016.1.26

 

威爾遜定理證明:若p為質數,則p可整除(p-1)!+1

 

First : 先把奇奇怪怪的取值試驗一下

      若p=2,成立;

      若p=3,成立;

      那麼我們就開始研究p>=5的情況

 

Second : 我們先來證明幾個結論

        設A = {2,3,4,……,p-2}   設a∈A

        記B = {a,2a,3a,……,(p-1)a}

       

【B中不會有取模p同餘的數……………………………………結論1

        證明:設b1a,b2a∈B,  b2,b1∈[1,p-1]上不同兩數

              假設b1a≡b2a (mod p)

              則|b1-b2|a≡0 (mod p)

              然而|b1-b2|∈[1,p-2]

              所以|b1-b2|a∈B

              然而B中顯然沒有數能被p整除,所以題設不成立

              所以結論1得證

        由於B中有p-1個元素,非p倍數模p餘數也只有p-1種,所以B中模p餘數構成集合C={1,2,3,…,p-1} 】

 

      【B中被p除餘1的數是ba,b∈A且b!=a…………………..結論2

        證明:若b=1,則ba=a,由於a∈A,所以a!=1,不成立

              若b=p-1,則(p-1)a≡p-a(mod p), 由於a∈A,所以p-a∈[2,p-2],不成立

              若b=a,則a2≡1(mod p),所以(a+1)(a-1)+≡0(mod p),因為p是素數,所以(a+1)和(a-1)中有且只有一個是p的倍數. 由於a∈A,所以(a+1)∈[3,p-1],(a-1)∈[1,p-3],所以他倆都不可能是p的倍數

              結論2得證 】

       

      【接著結論2,若a不同,b也不同…………………………結論3

        證明:設a1!=a2,但都屬於A,且ba1≡ba2≡1(mod p)

              易知ba1,ba2∈B,而根據結論1,則不成立

              結論3得證】

 

Third : 證明瞭這麼多結論,那麼這個定理也基本浮出水面了

       結論1告訴了我們B中對於每一個a都有唯一一個b∈[1,p-1]使得ab≡1(mod p)

       結論3升華了結論1,將b的範圍縮至b∈[2,p-2],且不會使a=b.也就是說,在[2,p-2]中每個數都可以找到一個與之唯一對應的逆元(註:p顯然是偶數,所以該區間內可以將所有整數分成一對兒一對兒的),且該逆元屬於[2,p-2]。

所以(p-1)!+1≡(p-1)+1≡0(mod p)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 在CMD命令行中啟動運行startup.bat,啟運程式總是閃退,查看日誌發現如下錯誤:26-Jan-2016 18:12:34.463 SEVERE [main] org.apache.coyote.AbstractProtocol.init Failed to initialize end po...
  • 關於AOP、之前我已寫過一個系列的隨筆: 《自己實現簡單的AOP》,它的關註點在於實現、實現語言是C#,實現方式為 自定義實現RealProxy 抽象類、重寫Invoke方法,以便進行方法調用的攔截、藉此實現AOP。感興趣的園友可以去瞅瞅。 今天、我們來看一下Spring中的AOP,本隨筆著重...
  • 本文翻譯自《effective modern C++》,由於水平有限,故無法保證翻譯完全正確,歡迎指出錯誤。謝謝!如果你曾經同過久的編譯時間鬥爭過,那麼你肯定對Pimpl("point to implementation",指向實現)機制很熟悉了。這種技術讓你把類的數據成員替換成指向一個實現類(或....
  • python3應該是python的趨勢所在,當前目前爭議也比較大,這篇隨筆的主要目的是記錄在linux6.4下搭建python3環境的過程 以及碰到的問題和解決過程。
  • 在任何迴圈語句的主體部分,均可用break控制迴圈的流程。break用於強行退出迴圈,不執行迴圈中剩餘的語句。(break語句還可用於多支語句switch中)continue 語句用於迴圈語句體中,用於終止某次迴圈過程,即跳過迴圈體中尚未執行的語句,接著進行下一次是否執行迴圈的判定。【break的例...
  • 一、寫在前面緩存作為系統性能優化的一大殺手鐧,幾乎在每個系統或多或少的用到緩存。有的使用本地記憶體作為緩存,有的使用本地硬碟作為緩存,有的使用緩存伺服器。但是無論使用哪種緩存,介面中的方法都是差不多。筆者最近的項目使用的是memcached作為緩存伺服器,由於memcached的一些限制,現在想換re...
  • Optimizer+ 是 Zend 開發的閉源但可以免費使用的 PHP 優化加速組件,是第一個也是最快的 opcode 緩存工具。現在,Zend 科技公司將 Optimizer+ 在 PHP License下開源成為 Zend Opcache。Zend OPcache 通過 opcode 緩存和優化...
  • 1 #coding=utf-8 2 class Fruit:#定義一個類 3 def __init__(self,color): 4 self.color=color 5 print("fruit's color:' %s" % self.color) 6 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...