两个桶,容积M、N,M和N互质,那么可以通过这两个桶得到任何{X|x属于N*,且M<X<N}体积的水。
如M=3,N=10,则4,5,6,7,8.9体积的水都能通过这两个桶得到。
证明:
这里用到一个定理:不定等式aX+bY=1当XY互质时,一定有解。
网上的证明如下:http://zhidao.baidu.com/link?url=ha07uKDOcQa3TP6CUy2zBGSNzlJtp8QMguL4U4QXPuD_vZbT_aS1OKA19eq9Rd06Bjf3KI2yr98reXCuIC7imq
正整数最小为1,因为a,b为正整数,所以a+b>=2,因此x和y不能同时为正。不妨设y<0,则令m=-y,
于是ax+by=1,变为ax-bm=1
因为a,b互质,因此a,2a,3a,.....,(b-1)a,ba,这b个数除以b后的余数全部包含0,1,2,3......b-2,b-1,选取余数为1的,例如ka,则必有1<=k<b,而此时(ka-1)/b一定是整数不妨设为M.于是有ka-Mb=1
于是原题的x=k,y=-M,均为整数。
本方法只是寻找了一个最小解,显然还有整数解x=k+nb,y= -(M+na),其中n为正整数。
本题目aM+bN=M+1,或M+2或M+3...N-1
借助上面的方法可证存在a b。
分享到:
相关推荐
- **ϕ(n)**:表示欧拉函数,即小于等于 n 的正整数中与 n 互质的数的数量。 - **τ(n)**:表示 n 的正因子的数量。 - **σ(n)**:表示 n 的正因子之和。 这些符号和定义构成了理解初等数论基础概念的关键部分。...
- **基本概念**:给定一个正整数m,如果两个整数a和b除以m得到相同的余数,那么a和b在模m下是同余的,记作a ≡ b (mod m)。反之,如果余数不同,则称a与b模m不同余,记作a ≢ b (mod m)。 - **同余类**:所有除以m...
- **加密过程**:明文m(0<m<n)通过公式c = m^e mod n进行加密,c为密文。 - **解密过程**:密文c通过公式m = c^d mod n解密回原始明文。 2. **C语言实现**: - **大数处理**:C语言标准库没有内置的大数支持,...
3. **分母的质因数分解**:如果n可以分解为2、5或这两个数的幂的乘积和其他质数的乘积,那么m/n的结果将是有限小数;如果还有其他非2和5的质因数,那么结果可能是循环小数。 4. **构造等式**:对于m/n,可以构造一...
- **N皇后问题的描述:** 在N×N的棋盘上放置N个皇后,使得任意两个皇后都不在同一行、同一列或同一斜线上。 - **解决方法:** 如递归、回溯等。 **13.3 布尔母函数** - **布尔母函数的定义:** 一种用于描述布尔...
- **除法算法**:在整数集合中,对于任意两个正整数 a 和 b(b ≠ 0),存在唯一的一对整数 q 和 r 满足 a = bq + r,其中 0 ≤ r < |b|。 - **m 进制表示**:每个正整数 n 都可以唯一地写成 m 进制形式,即 \(n = a...
- **互质数**:两个数的最大公约数为1。 15. **最小公倍数**: - **几个数共有的最小倍数**。 16. **通分与约分**: - **通分**:将不同分母的分数转化为相同分母的分数。 - **约分**:将分数化为最简形式,...
- **最大公约数**:欧几里得算法是最常用的计算最大公约数的方法,时间复杂度为O(n),适用于两个大数相除直到余数为0的情况。 - **Stein算法**:也称为二进制GCD算法,其时间复杂度为O(log(max(a,b))),比欧几里得...
- **性质**: 对于任意两个正整数\(a\)和\(b\),有\(\text{GCD}(a, b) \cdot \text{LCM}(a, b) = a \cdot b\)。 #### 1.2 快速筛选素数 - **超快、超小空间的素数筛法**: 基于**埃拉托斯特尼筛法**的改进版本。 - ...
1. **初始化:** 对于两个数 m 和 n,假设 m > n。 2. **除法:** 将 m 除以 n 得到余数 r。 3. **检查余数:** 如果 r = 0,则 n 是 m 和 n 的最大公约数;否则进入下一步。 4. **更新变量:** 将 m 更新为 n,n 更新为...
- **互质**: 若两个整数的最大公约数为1,则称这两个整数互质。 - **辗转相除法**: 求解两个整数的最大公约数的一种方法。 ### 4. 知识点:关系及其性质 #### 4.1 关系的定义 - **关系**: 在集合A到集合B之间建立...
5. **mim.m文件**:该文件可能包含了计算乘法逆元的函数,即求解x,使得x * e ≡ 1 mod φ(n)。这是找到私钥d的关键步骤。 6. **highmod.m文件**:这个文件可能用于执行高次幂模运算,即计算M^e mod n。在加密和...
- **裴蜀定理**:如果有整数a, b和正整数n,那么存在整数x使得ax ≡ b (mod n),当且仅当gcd(a, n) | b。 - **逆元**:在模n下,如果存在整数x使得ax ≡ 1 (mod n),则x称为a关于模n的逆元。 - **扩展中国剩余...
3. **线性组合**:如果`a|b`且`a|c`,则`a|(bx + cy)`,其中`x`和`y`为任意整数。 4. **倍数规则**:如果`a|b`,那么对于任意非零整数`m`,有`am|bm`。 5. **互为相反数或相同**:如果`a|b`且`b|a`,则`b = ±a`,即...
- **选取加密指数e**:e应满足1 < e < φ(n)且gcd(e, φ(n))=1,即e和φ(n)互质。通常选择e为65537,这是个常用且效率较高的值。 - **计算解密指数d**:d是e的模φ(n)的逆元,即e*d ≡ 1 (mod φ(n))。d是私钥的一...
10. **判断互质**:通过试除法,检查m和n是否有共同因子,若没有则互质。 11. **十进制转k进制**:使用除k取余的方法将十进制数转化为k进制。 12. **统计实数分布**:遍历50个实数,计数正数、负数和零的数量。 ...
- **解析**:这部分内容主要讨论了当两个数(a,c)互质时,一定存在整数x和y使得ax+cy=1成立。 - **扩展知识点**: - **线性组合**:理解线性组合的基本概念及其在信息安全中的应用。 - **线性组合的性质**:掌握...