rainman's blog

学海无涯,回头是岸

数论笔记

数论这种东西还是比较玄学的,因此有做笔记的必要。本文除特殊说明,字母均表示整数。

整除

整除的定义: 设 $a,b$ 是给定的数, $b\ne 0$ 。若 $\exists c \in Z,\ni a=bc,$ 则称 $b$ 整除 $a,$ 记作 $b|a$ 。

整除的性质:

  • (传递性)若 $b|c$ ,且 $c|a$ ,则 $b|a$ 。证明:因为 $b|c$ ,所以有 $c=bk_1$ ,同理 $a=ck_2$ ,所以 $a=bk_1k_2$ ,符合定义,证毕。

  • (为某一整数的倍数的整数之集关于加减运算封闭)若 $b|a$ ,且 $b|c$ ,则 $b|(a\pm c)$ 。证明同样可以由整除的定义得到。反复运用这一结论可以得到一些拓展结论。

  • 若 $b|a$ ,则或者 $a=0$ ,或者 $|a|\geqslant |b|$ 。于是若 $b|a$ 且 $a|b$ ,则 $|a|=|b|$ 。

  • 1整除任何数,任何数都整除0。

带余除法:

$$a=bq+r,(0\leqslant r < b)$$

易知 $q=[\dfrac{a}{b}]$ ,其中 $f(x)=[x]$ 为高斯函数。在C++中,除法符号/得到的结果即是这里的 $q$ 。

例题:

“叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那复读的惆怅,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水,凝聚此 刻。为了把毕业晚会办得更好,想要挑出默契程度最大的k个人参与毕业晚会彩排。老师列出全班同学的号数1,2,……,n,并且相信k个人的默契程度便是他们的最大公约数(这不是迷信哦~)。输入正整数n和k(n>=k>=1),输出最大的默契值。

首先,若可能的最大公约数为 $a$ ,取出的 $k$ 个数为 $x_1,x_2,... ,x_k$ 且满足 $x_1<x_2<...<x_k$ ,那么有 $x_1\geqslant a,x_2\geqslant 2a,...,$ $x_ k\geqslant ka$ 。又 $x_k\leqslant n$ ,∴ $n\geqslant ka$ ,∴ $a\leqslant\dfrac{n}{k}$ ,又∵a为整数,∴ $a\leqslant [\dfrac{n}{k}]$ 。 另一方面,我们取 $[\dfrac{n}{k}],2[\dfrac{n}{k}],...,k[\dfrac{n}{k}]$ ,它们的最大公约数 $a=[\dfrac{n}{k}]$ ,且它们都小于等于 $n$ 大于等于1,且互不相等,满足条件。

答案即为 $[\dfrac{n}{k}]$ ,算法复杂度 $O(1)$ 。

例题:

任给 $n \geqslant 2$ ,求证存在 $n$ 个互不相同的正整数,其中任意两个的和,整除这 $n$ 个数的积。

考虑构造。我们先任取互不相同的数 $a_1,a_2,...a_n$ ,并选取一个参数 $K$ ,试图使得 $Ka_1,...,Ka_n$ 的积 $K^n \prod\limits_{i=1}^na_i$ 被任意两项的和 $Ka_m+Ka_n$ 整除。

玄学的得到(构造): $K=\prod\limits_{1\leqslant i<j \leqslant n}(a_i+a_j)$ ,符合要求。

最大公约数与最小公倍数

定义: 设a,b是不都为0的整数,c为满足c|a且c|b的最大整数,则称c是a,b的最大公约数。记为 $gcd(a,b)$ 或 $(a,b)$ 。 $GCD(Greatest \ Common \ Divisor)$

性质:

  • $gcd(\pm a,\pm b)=gcd(a,b)$

  • $gcd(a,b)=gcd(b,a)$

  • $gcd(a,a)=gcd(0,a)=a$

  • 若 $a|b$ ,则 $gcd(a,b)=a$

  • $gcd(a,b)=gcd(a,a+b)=gcd(a,ka+b)$

  • $gcd(ka,kb)=k·gcd(a,b)$

  • $gcd(a,b,c)=gcd(gcd(a,b),c)$

  • 若 $gcd(a,b)=1$ ,则称 $a,b$ 互质(互素)


参考资料


2019-06-10 20:18:36 in 数学