数论——约数：算数基本定理及推论，欧几里得算法

一、算数基本定理及推论：

算数基本定理

任何一个大于1的自然数N，如果N不为质数，都可以唯一分解成有限个质数的乘积  ，这里均为质数，其诸指数 是正整数。

这样的分解称为N的标准分解式。

推论1

算数基本定理中N的正约数个数为： 。

　　简单证明一下：根据算数基本定理    可知，对于其中的任意一个pi（i∈[1，n]）,其指数取0~ai范围任何值均能组成N的不同的约数，故pi的指数取法就有（ai+1）种，所以N的约数总个数即为所有质因子p的指数取法之积（乘法原理）。

　　模板题链接：约数个数

　　代码如下：

#include 
#include 
#include 
#include 
#include 
#include 

推论2

算数基本定理中N的所有正约数的和为： 

　　也简单证明一下：要求N的所有正约数之和，只需要组合出所有N的正约数即可，不难发现，将上式展开后的所有项即是N的所有正约数。

　　模板题链接：约数之和

　　代码如下：

#include 
#include 
#include 
#include 
#include 
#include 

二、欧几里得算法

对于任意的a,b∈N，b≠0，gcd(a,b) = gcd(b,a mod b)，其中gcd(a,b)表示a和b的最大公约数。

　　下面给出证明：

证明：

　　要证明gcd(a,b)=gcd(b,a mod b)，只要证明gcd(a,b)≤gcd(a,a mod b)，且gcd(a,b)≥gcd(b,a mod b)。

　　下面证明gcd(a,b)≤gcd(b,a mod b)：

　　设d是a和b的最大公约数，所以d | a且d | b，可以推出 d | a mod b。

　　假设a=k*b+r（k,r均是整数，且0≤r＜b），因为d | b，所以d | kb，又因为d | a，所以d | (a - kb)，即d | (a mod b)。

　　相当于我们有了这样的结论：d是a和b的最大公约数，且d又是(a mod b)的约数，所以d是b和(a mod b)的公约数，于是便可推出gcd(a,b)≤gcd(b,a mod b)。

　　下面证明gcd(a,b)≥gcd(b,a mod b):

　　设d是b和(a mod b)的最大公约数，所以d | b且d | (a mod b)，可以推出 d | a。

　　假设a=k*b+r（k,r均是整数，且0≤r＜b），因为d | b，所以d | kb，又因为d | (a - kb)，所以 d | (kb + (a - kb))，即 d | a。

　　相当于：d是a和(a mod b)的最大公约数，且d又是a的约数，所以d是a和b的公约数，于是便可推出gcd(a,b)≥gcd(b,a mod b)。

　　证毕！

　　模板题链接：最大公约数

　　代码实现：

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}