初等数论--整除--两数乘积保持整除性_季炜丹的博客-程序员宅基地

技术标签: 信息安全  初等数论  数学  密码学  

博主本人是初学初等数论(整除+同余+原根),本意是想整理一些较难理解的定理、算法,加深记忆也方便日后查找;如果有错,欢迎指正。
我整理成一个系列:初等数论,方便检索。

m ∣ r , n ∣ r , ( m , n ) = 1 → m n ∣ r m\mid r,n\mid r,(m,n)=1\rightarrow mn\mid r mr,nr,(m,n)=1mnr

m ∣ r → r = p m m\mid r\rightarrow r=pm mrr=pm
n ∣ r → r = q n n\mid r\rightarrow r=qn nrr=qn

  • r = p m = q n → m ∣ q n r=pm=qn\rightarrow m\mid qn r=pm=qnmqn

m ∣ q n m\mid qn mqn
m ( m , n ) ∣ q n ( m , n ) \frac{m}{(m,n)}\mid q\frac{n}{(m,n)} (m,n)mq(m,n)n
m ( m , n ) ∣ q \frac{m}{(m,n)}\mid q (m,n)mq
因为 ( m , n ) = 1 (m,n)=1 (m,n)=1
m ∣ q m\mid q mq
q = a m , a ∈ Z q=am,a\in \mathbb{Z} q=am,aZ
r = q n = a m n , a ∈ Z r=qn=amn,a\in \mathbb{Z} r=qn=amn,aZ
m n ∣ r mn\mid r mnr

m ∣ r , n ∣ r → [ m , n ] ∣ r m\mid r,n\mid r\rightarrow [m,n]\mid r mr,nr[m,n]r

[ m , n ] = l c m ( m , n ) [m,n]=lcm(m,n) [m,n]=lcm(m,n) 最小公倍数
( m , n ) = g c d ( m , n ) (m,n)=gcd(m,n) (m,n)=gcd(m,n) 最大公因数
m n = [ m , n ] ⋅ ( m , n ) ⇒ [ m , n ] = m n ( m , n ) mn=[m,n]\cdot (m,n)\Rightarrow[m,n]=\frac{mn}{(m,n)} mn=[m,n](m,n)[m,n]=(m,n)mn

因为 n ∣ r n\mid r nr,所以 r = q n r=qn r=qn
因为 m ∣ r m\mid r mr,所以
m ∣ q n m\mid qn mqn
⇒ m ( m , n ) ∣ q n ( m , n ) \Rightarrow \frac{m}{(m,n)}\mid \frac{qn}{(m,n)} (m,n)m(m,n)qn
⇒ m ( m , n ) ∣ q \Rightarrow\frac{m}{(m,n)}\mid q (m,n)mq
⇒ m n ( m , n ) ∣ q n \Rightarrow \frac{mn}{(m,n)}\mid qn (m,n)mnqn
⇒ [ m , n ] ∣ q n \Rightarrow [m,n]\mid qn [m,n]qn
⇒ [ m , n ] ∣ r \Rightarrow [m,n]\mid r [m,n]r

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41545715/article/details/121597845

智能推荐

java uuid 生成 策略_java 类设置id生成策略_吴佳晗的博客-程序员宅基地

public class Data_Brand implements Serializable {//[email protected]@GeneratedValue(strategy = GenerationType.AUTO)private Integer id;//自序ID,默认生成策略private String Brand_Name;//品牌名称brandName brand_name}@Enti...

Android多媒体学习日记(一)_ekenlinbing的博客-程序员宅基地

知识归纳:             多媒体框架是由第三方PacketVideo提供的OpenCore实现的,它支持播放和录音许多的音频和视频格式,以及静态图像文件,包括MPEG4、MP3、H.264、AMR、AAC、AMR、JPG、PNG。             多媒体核心OpenCore,它的另外的一个称呼是PacketVideo,是按Android的多媒体核心,基于C++实现的,定义

hdu5114Collision_GAUSS_CLB的博客-程序员宅基地

CollisionTime Limit: 15000/15000 MS (Java/Others)    Memory Limit: 512000/512000 K (Java/Others)Total Submission(s): 26    Accepted Submission(s): 8Problem DescriptionMatt is playing a

vue 组件 更换html标签,Vue: 标签页组件_weixin_39725193的博客-程序员宅基地

index.html:标签页组件标签一的内容标签二的内容标签三的内容var app = new Vue({el: '#app',data: {activeKey: '1'}})pane.js:Vue.component('pane', {name: 'pane',template: '\\\',props: {name: {type: String},label: {type: String,de...

对话框包含select框双向绑定_悄悄地卷的博客-程序员宅基地_select双向绑定

//关于zhsq小区页面的编辑界面弹出框双向绑定的一些细节:因为弹出的对话框有下拉框部分、双向绑定下拉框数据时又要监听数据、与表格普通数据分开双向绑定所以在computed中就要使用get()、set(val)来实现双向绑定相关代码:<el-form :model=form> <el-form-item label="公司名称" prop="companyDept"> <el-select v-model="companyShow" pl.

随便推点

七上八下猜数字_六一儿童节游园活动的项目和游戏规则.doc_阿野与阿厉的博客-程序员宅基地

“六一儿童节”游园活动的项目及游戏规则在纸上画一个人头,游戏者蒙上双眼,原地转五圈,而后让游戏者走向指定的位置,把“鼻子”贴到人头上,贴中者得奖。二、夹珠在一个大桶内装满水,再往桶中放入较多得玻璃珠。游戏者手拿一双筷子向桶中夹珠。在指定时间内(一分钟),夹起指定个数(十五个)得奖。? 三、妙接对联或歇后语主持人要准备好较多的对联或歇后语。主持人说出上联或下联,让参赛者来接,对的就得奖。参赛者在接...

Hadoop之MapReduce 根据用户流量日志文件数据统计每个用户流量总和_一粒尘埃zc的博客-程序员宅基地

文章目录1.实现需求2.MapReduce编程模型1.实现需求2.MapReduce编程模型input读取文件splitting分割文件,框架自动完成mapping处理文件,以key,value的方式存储 ,需要自己实现shuffing把相同的key归类到一起,框架自动完成Reducing处理相同的key的数据,需要自己实现Final result处理最后结果...

HTML按钮的风格,7种Material Design风格打开菜单按钮特效_医学科普联盟的博客-程序员宅基地

这是一款效果非常炫酷的Material Design风格打开菜单按钮特效。该特效有7种不同的效果,每一种效果中都可以通过点击主菜单按钮来打开一组主菜单按钮,各种打开子菜单的动画效果各不相同。使用方法HTML结构这7种打开菜单按钮特效的基本HTML结构都非常相似:使用一个来作为包裹元素,里面使用一个div元素来作为按钮组包裹元素。然后在其里面放置一个button元素作为主菜单按钮,在用一个div包裹...

java页面响应太慢,求JSP页面访问过慢的解决办法_彼一暝的博客-程序员宅基地

当前位置:我的异常网» Java Web开发»求JSP页面访问过慢的解决办法求JSP页面访问过慢的解决办法www.myexceptions.net网友分享于:2015-08-26浏览:54次求JSP页面访问过慢的解决方法在把作好的项目部署到服务器上去后可以运行,但是响应速度实在太慢,随便开个页面要等个半天,实在是受不了服务器的配置大致是:CPU 2G,内存 2G。操作系统是wi...

C语言中的time函数总结_带你去网吧里偷耳机的博客-程序员宅基地_c语言中time函数

编程中经常用到时间表达及转换的函数,它们都定义在time.h库函数中,在此做一下总结,以方便后续查看使用。几个时间概念:1:Coordinated Universal Time(UTC): 协调世界时,又称世界标准时间,也即格林威治标准时间(Greenwich Mean Time,GMT),中国内地的时间与UTC得时差为+8,也即UTC+8,美国为UTC-5。2:Calendar Time...

10. xxl-job原理---回调_Gavin_Alison的博客-程序员宅基地_xxljob回调

xxl-job: v2.0.2 原理 目录学习0. xxl-job原理1. xxl-job原理—定时任务架构2. xxl-job原理-- 调度中心3. xxl-job原理-- 执行器注册4. xxl-job原理-- 执行器注册问题5 xxl-job原理-- 执行器注册问题6. xxl-job原理-- 调度中心注册7. xxl-job原理-- 任务管理8. xxl-job原理--...

推荐文章

热门文章

相关标签