数论基础知识:整除、带余数除法及其性质
需积分: 0 168 浏览量
更新于2024-01-15
收藏 1.07MB PDF 举报
ACM算法与程序设计(十二)课程中介绍了数论和基础数学的相关知识。其中,整除和取余是本节课的主要内容。整除的定义是,如果存在一个整数q使得b=aq,那么就说b可以被a整除,并将b称为a的倍数,a称为b的约数。
带余数除法是指对于两个正整数a和b(b≠0),存在唯一的整数q和r,使得a=qb+r,其中0≤r<|b|。余数r可以通过a mod b来计算,例如13 mod 5=3,10 mod 2=0。当余数为0时,即r=0,表示b是a的约数。
根据以上的定义和性质,可以总结出以下关于整除的性质:
1. 若a可以整除b,并且a也可以整除c,则对于任意的整数x和y,a也可以整除xb和yc。
这是因为可以将b表示为b=ax和c表示为c=ay,将这两个等式代入a可以整除b和a可以整除c的定义中,可以得到b=ax是a的倍数,c=ay是a的倍数。而根据整除的定义,a的倍数的乘积仍然是a的倍数,所以对于任意的整数x和y,a也可以整除xb和yc。
2. 若a可以整除b,并且b可以整除c,则a可以整除c。
这是因为可以将b表示为b=ax,将c表示为c=by,然后将b=axy代入c=by中,得到c=a(xy),即c也是a的倍数。
3. 若m不等于0,则a可以整除b当且仅当ma可以整除mb。
这是因为可以将b表示为b=ax,然后将ma代入ma=mb中,得到ma=axm,即ma也是a的倍数,所以a可以整除b当且仅当ma可以整除mb。
4. 若a可以整除b,并且b可以整除a,则a等于±b。
这是因为a可以整除b表示为b=ax,b可以整除a表示为a=by,将b=ax代入a=by中,得到ax=by,即a和b成比例。因为a和b都是整数,所以a和b相差一个整数倍,即a=±b。
除了整除和取余,本节课还介绍了一些矩阵的应用,例如矩阵二分快速幂用来求解递推问题。这些内容都是数论和基础数学中的重要知识点,对于算法的设计和程序的编写有很大的帮助。通过学习这些知识,可以提高对整数运算的理解和应用能力。
2012-10-24 上传
2018-11-28 上传
2023-10-05 上传
2023-10-11 上传
2023-06-06 上传
2023-10-12 上传
2023-09-08 上传
2023-11-05 上传
WaiyuetFung
- 粉丝: 665
- 资源: 316
最新资源
- ES管理利器:ES Head工具详解
- Layui前端UI框架压缩包:轻量级的Web界面构建利器
- WPF 字体布局问题解决方法与应用案例
- 响应式网页布局教程:CSS实现全平台适配
- Windows平台Elasticsearch 8.10.2版发布
- ICEY开源小程序:定时显示极限值提醒
- MATLAB条形图绘制指南:从入门到进阶技巧全解析
- WPF实现任务管理器进程分组逻辑教程解析
- C#编程实现显卡硬件信息的获取方法
- 前端世界核心-HTML+CSS+JS团队服务网页模板开发
- 精选SQL面试题大汇总
- Nacos Server 1.2.1在Linux系统的安装包介绍
- 易语言MySQL支持库3.0#0版全新升级与使用指南
- 快乐足球响应式网页模板:前端开发全技能秘籍
- OpenEuler4.19内核发布:国产操作系统的里程碑
- Boyue Zheng的LeetCode Python解答集