当前位置: 首页 > news >正文

费马小定理的证明

费马小定理:若 \(p\) 为质数,则 \(x^{p}\equiv x(\text{mod}\ p)\)。特别地,若 \(p\not\mid x\),则 \(x^{p-1}\equiv 1(\text{mod}\ p)\)
首先,若 \(p\mid x\),则 \(x\equiv 0(\text{mod}\ p)\Leftrightarrow x^p\equiv x(\text{mod}\ p)\)
\(p\not\mid x\),则我们构造一个集合 \(\{x, 2x, \dots (p - 1)x\}\)
假设这个集合里的元素有相同的,则若对于 \(i\not= j\),有 \(ix\equiv jx(\text{mod}\ p)\)
移向,得 \((i - j)x\equiv 0(\text{mod}\ p)\)
因为 \(i\not=j\),且 \(0<i,j<p\),因此 \(p\not\mid(i-j)\)
又因为 \(p\not\mid x\),所以 \((i - j)x\not\equiv 0(\text{mod}\ p)\),矛盾。
因此 \(x,2x\dots,(p-1)x\) 没有相同的元素,且里面的元素对 \(p\) 取模后与集合 \(\{1,2,\dots,p-1\}\) 相同。
我们让两个集合的所有元素分别相乘,得到 \(x\cdot 2x\cdots (p-1)x\equiv 1\cdot 2\cdots (p-1)(\text{mod}\ p)\)
得到 \(x^{p - 1}\equiv 1(\text{mod}\ p)\)
\(x^{p}\equiv x(\text{mod}\ p)\)

http://www.hskmm.com/?act=detail&tid=25688

相关文章:

  • 威尔逊定理的证明
  • 实用指南:HTML实现端午节主题网站:龙舟争渡,凭吊祭江诵君赋
  • 深入解析:rknn优化教程(一)
  • WannaCry勒索病毒数字取证与安全监控实战指南
  • 吴恩达深度学习课程一:神经网络和深度学习 第二周:神经网络基础(二)
  • 08. 自定义组件
  • 20251006 模拟测 总结
  • 数据源切换之道
  • 完整教程:tryhackme——Abusing Windows Internals(进程注入)
  • 向量存储vs知识图谱:LLM记忆系统技术选型
  • QBXT2025S刷题 Day5
  • FFT 学习笔记
  • Ai元人文系列:领域协同深耕:构建人机价值共生的文明实践框架
  • NFL统一数据生态系统技术架构解析
  • 复习题集
  • 实用指南:SCDN如何同时保障网站加速与DDoS防御?
  • 二分查找模板:基础二分与进阶二分
  • 【设计模式-4.5】行为型——迭代器模式 - 教程
  • 循环结构
  • SP6950 CTOI10D3 - A HUGE TOWER 题解
  • 浅谈并查集
  • 16_AiAgentMCP简单教程
  • 17_AiAgentMCP实现技术选型
  • JVM_XMS 和 java_opts哪种写法对?如何在JVM中设置JVM_XMS和java_opts?
  • POLIR-Society-Philosophy-mind: 思想/精神
  • 鸿蒙编译ffmpeg库 - 详解
  • 知道却做不到
  • 题解:loj154 集合划分计数
  • 为什么 Java 中打印Object类型的变量无需强转,而从Object类型的数组中取元素却要强转?
  • WinReanimator恶意软件清除指南:详细步骤与工具使用