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

费马小定理详解

费马小定理

定义:

p 为素数,a 为整数,则 a p ≡ a ( m o d p ) a^p \equiv a\ (\mod p) apa (modp) ,若 p ∤ a p \nmid a pa ,则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (\mod p) ap11 (modp)

先证明若 p ∣ a p \mid a pa ,证明过程如下:
∵ p ∣ a a m o d p = 0 a p m o d p = 0 \because p \mid a \\ a\mod p=0 \\ a^p \mod p =0 paamodp=0apmodp=0
再证明当 p ∤ a p \nmid a pa 时:

创建集合 S = S= S={ x 1 , x 2 , x 3 , ⋯ , x p − 1 x_1,x_2,x_3,\cdots,x_{p-1} x1,x2,x3,,xp1} ,S为1,2,3, ⋯ \cdots ,p-1的一个 排列 a x 1 , a x 2 , a x 3 , ⋯ , a x p − 1 ax_1,ax_2,ax_3,\cdots,ax_{p-1} ax1,ax2,ax3,,axp1 ,任意两项模 p 不同余

∃ ∀ i , j , ╞ 1 ≤ i < j < p \exists\ \forall\ i,j,╞ 1\le i <j <p   i,j,╞1i<j<p ,使得 a x i ≡ a x j ( m o d p ) ax_i\ \equiv ax_j (\mod p) axi axj(modp)

p ∣ a ( x i − x j ) p\mid a(x_i-x_j) pa(xixj)

∵ p ∤ a , ∴ p ∣ ( x i − x j ) \because p \nmid a\ \ ,\therefore p\mid(x_i-x_j) pa  ,p(xixj)

∵ x i m o d p ≠ x j m o d p \because x_i \mod p \not= x_j\mod p ximodp=xjmodp

∴ 矛盾 \therefore 矛盾 矛盾

∀ k ∈ S , p ∤ S k \forall \ k \in S,p\ \nmid\ S_k  kS,p  Sk

∵ a x 1 m o d p , a x 2 m o d p , ⋯ , a x p − 1 m o d p \because ax_1\mod p,ax_2\mod p,\cdots,ax_{p-1}\mod p ax1modp,ax2modp,,axp1modp 为1,2,3, ⋯ \cdots ,p-1的一个排列(上文已提到)

∴ ( a x 1 ) ( a x 2 ) ( a x 3 ) ⋯ ( a x p − 1 ) ≡ x 1 ⋅ x 2 ⋅ x 3 ⋯ x p − 1 ( m o d p ) \therefore (ax_1)(ax_2)(ax_3)\cdots(ax_{p-1})\equiv x_1\cdot x_2\cdot x_3 \cdots x_{p-1} (\mod p) (ax1)(ax2)(ax3)(axp1)x1x2x3xp1(modp)
x 1 ⋅ x 2 ⋅ x 3 ⋯ x p − 1 = ( p − 1 ) ( p − 2 ) ( p − 3 ) ⋯ 2 ⋅ 1 = ( p − 1 ) ! x_1\cdot x_2 \cdot x_3 \cdots x_{p-1} \\ =(p-1)(p-2)(p-3)\cdots 2\cdot 1 \\ =(p-1)! x1x2x3xp1=(p1)(p2)(p3)21=(p1)!
∵ p ∤ ( p − 1 ) ! \because p\nmid(p-1)! p(p1)!

∴ a p − 1 ≡ 1 ( m o d p ) \therefore a^{p-1}\equiv 1 (\mod p) ap11(modp)

得证

相关文章:

费马小定理详解

费马小定理 定义&#xff1a; 设 p 为素数&#xff0c;a 为整数&#xff0c;则 a p ≡ a ( m o d p ) a^p \equiv a\ (\mod p) ap≡a (modp) &#xff0c;若 p ∤ a p \nmid a p∤a &#xff0c;则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (\mod p) ap−1≡1 (modp)…...

PXE批量安装

系统装机的三种引导方式 u盘光盘网络装机 光盘&#xff1a; 1.类似于usb模式 2.刻录模式 系统安装过程 加载boot loader Boot Loader 是在操作系统内核运行之前运行的一段小程序。通过这段小程序&#xff0c;我们可以初始化硬件设备、建立内存空间的映射图&#xff0c;从…...

stm32f103c8t6最小系统板

STM32F103C8T6最小系统板是为基于ARM Cortex-M3内核的STM32F103C8T6微控制器设计的电路板&#xff0c;它包含了单片机正常运行所需的最基本组件。以下是构成STM32F103C8T6最小系统板的基本部分&#xff1a; 单片机芯片&#xff1a;STM32F103C8T6本身&#xff0c;它是一款32位微…...

QCefView 在 Linux 下的编译(更新)

在前面的文章《QT 应用程序中集成浏览器》中已经介绍过 QCefView 的构建。这几天发现 QCefView 代码进行了更新,构建方式也发生了一点点变化,所以在此更新一下 QCefView 的编译方法。 QCefView 其实包含了两个项目,一个就是 QCefView 项目本身,另外一个就是 CefViewCore。…...

无卤素产品是什么?有什么作用?

无卤素产品&#xff0c;即在生产过程中完全不使用卤素元素——氟、氯、溴、碘等——的产品。 卤素元素&#xff0c;虽然在电子设备、材料等领域应用广泛&#xff0c;却也可能潜藏危害。其阻燃剂&#xff0c;一旦在产品生命周期结束后释放&#xff0c;将对土壤和水体造成污染&a…...

esp32-cam 1. 出厂固件编译与测试

0. 环境 - ubuntu18 - esp32-cam - usb转ttl ch340 硬件连接 esp32-camch340板子U0RTXDU0TRXDGNDGND5V5V 1. 安装依赖 sudo apt-get install vim sudo apt install git sudo apt-get install git wget flex bison gperf python python-pip python-setuptools python-serial p…...

题目:线性代数

问题描述&#xff1a; 解题思路&#xff1a; 列相乘&#xff0c;然后行相加。 注意点&#xff1a;由于元素数据范围最大为1e6&#xff0c;两个元素相乘乘积最大为1e12&#xff0c;如果元素类型为int则在乘的过程中就会爆炸&#xff0c;所以需要开long long类型。 AC代码…...

docker学习笔记3:VmWare CentOS7安装与静态ip配置

文章目录 一、安装CentOS71、下载centos镜像2、安装二、设置静态ip三、xshell连接centos本专栏的docker环境是在centos7里安装,因此首先需要会安装centos虚拟机。 本篇博客介绍如何在vm虚拟机里安装centos7。 一、安装CentOS7 1、下载centos镜像 推荐清华源,下载如下版本 …...

leetcode 547.省份数量

思路&#xff1a;dfs 或者这道题用bfs也是可以的。 这道题有点迷惑性&#xff0c;这里的数组给的是无向图的数组&#xff0c;而并不是地图&#xff0c;这里需要着重注意一下。 而后&#xff0c;这里的状态数组st没必要是二维的&#xff0c;我们并不会去遍历所给的数组&#…...

Qt5 框架学习及应用 — 对象树

Qt 对象树 对象树概念Qt为什么使用对象树 &#xff1f;将对象挂到对象树上 对象树概念 对象树&#xff1a;对于树的概念&#xff0c;相信许多学过数据结构的同学应该都不会陌生。在学习数据结构的时候我们所接触的什么二叉树、多叉树、哈夫曼树、AVL树、再到红黑树、B/B树………...

Ansible自动化运维工具---Playbook

一、playbook playbook是剧本的意思 通过 task 调用 ansible 的模块将多个 play 组织在一 个playbook中运行。 playbook本身由以下各部分组成&#xff1a; Tasks: 任务&#xff0c;即调用模块完成的某操作Variables: 变量Templates: 模板Handlers: 处理器&#xff0c;当某条…...

什么是接口和类?Java中的集合框架有哪些主要接口和类?

Java中的集合框架有哪些主要接口和类&#xff1f; Java中的集合框架&#xff08;Java Collections Framework&#xff09;提供了一套丰富的接口和类&#xff0c;用于存储和操作对象的集合。以下是Java集合框架中的主要接口和类&#xff1a; 主要接口 Collection&#xff1a; 这…...

算法学习笔记(最短路——Bellman-Ford)

B e l l m a n — F o r d Bellman—Ford Bellman—Ford是一种单源最短路径算法&#xff0c;可以用于边权为负的图&#xff0c;但是只能用于小图。 大概过程&#xff1a; 枚举每一条边&#xff0c;更新可以更新的节点&#xff08;起点到自己距离为 0 0 0&#xff0c;从地点开…...

try-catch-finally的省略与springboot

在 Java 中&#xff0c;try-catch 块是用于捕获和处理异常的结构&#xff0c;它可以帮助您在代码中处理可能发生的异常情况。在某些情况下&#xff0c;您可能希望省略 try-catch 块并将异常向上抛出&#xff0c;让调用者处理异常。这种情况通常适用于以下情况&#xff1a; 方法…...

容器Docker:轻量级虚拟化技术解析

引言 随着云计算和虚拟化技术的飞速发展&#xff0c;容器技术以其轻量级、高效、可移植的特性&#xff0c;逐渐成为了软件开发和部署的新宠。在众多容器技术中&#xff0c;Docker以其简单易用、功能强大的特点&#xff0c;赢得了广泛的关注和应用。本文将全面介绍Docker的基本概…...

windows 系统中cuda 12.1 环境安装

文章目录 1. 安装cuda 12.11.1 下载1.2 安装 cuda1.2.1 安装步骤1.2.2 环境变量安装1.3 安装cuDNN1.3.1 安装1.3.2 cuDNN配置验证2. anaconda 安装2.1 安装2.2 环境变量配置3. 报错解决1. 安装cuda 12.1 首先通过nvidia-smi 查看可以安装的CUDA最高版本...

字节和旷视提出HiDiffusion,无需训练,只需要一行代码就可以提高 SD 生成图像的清晰度和生成速度。代码已开源。

字节和旷视提出HiDiffusion&#xff0c;无需训练&#xff0c;只需要一行代码就可以提高 SD 生成图像的清晰度和生成速度。代码已开源。 支持将图像生成的分辨率提高至40964096&#xff0c;同时将图像生成速度提升1.5至6倍。 支持所有 SD 模型同时也支持 SD 模型的下游模型&…...

linux下dd制作启动U盘

dd命令是比较推荐的一种Linux环境中制作U盘启动盘的方式&#xff0c;无需安装额外的工具&#xff0c;基本上所有Linux发行版都集成了这个命令。 1、插入U盘&#xff1b; 2、打开终端&#xff1b; 3、确认U盘路径&#xff0c;在终端中输入&#xff1a;sudo fdisk -l 例如&am…...

springboot整合mybatis配置多数据源(mysql/oracle)

目录 前言导入依赖坐标创建mysql/oracle数据源配置类MySQLDataSourceConfigOracleDataSourceConfig application.yml配置文件配置mysql/oracle数据源编写Mapper接口编写Book实体类编写测试类 前言 springboot整合mybatis配置多数据源&#xff0c;可以都是mysql数据源&#xff…...

练习项目后端代码解析切面篇(Aspect)

前言 之前注解篇时我说&#xff0c;通常情况下一个自定义注解一般对应一个切面&#xff0c;虽然项目里的切面和注解个数相同&#xff0c;但是好像有一个名字看起来并不对应&#xff0c;无所谓&#xff0c;先看了再说。 ExceptionLogAspect切面 我在里面做了具体注释&#x…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...