互质自然数
 
两个非零自然数的最大公约数是1——>两个数互质
 
1和任何非零自然数都是互质的。
 
互质整数
 
互质是公约数只有1的两个整数，叫做互质整数。公约数只有1的两个自然数，叫做互质自然数，后者是前者的特殊情形。
 
1和-1与所有整数互素，而且它们是唯一与0互素的整数。
 
互质判断方法：
 
两个数互质的情况：
 
性质一：两个不同的质数是互质的。 
 性质二：一个质数，另一个不为它的倍数，这两个数为互质数。（较大数是质数的两个数是互质数） 
 性质三：相邻的两个自然数是互质数。 
 性质四：相邻的两个奇数是互质数。 
 性质五：最大公约数是1，两个数互质。
 
三个或三个以上自然数互质有两种不同的情况：
 
一种是这些成互质数的自然数是两两互质的。如2、3、5。 
 另一种不是两两互质的。如6、8、9。
 
编程判断互质
 
常使用性质五：判断两个数的最大公约数是否是1 
 c语言：
 
#include <stdio.h>
#include <stdlib.h>
void exchange(int &a,int &b){//为辗转相除初始化 
    if(a>b){
        int c = a;
        b = c;
        a = b;
    }
}
int gcd(int a,int b){//辗转相除求最大公约数 
    if(b==0){
        return a;
    }else{
        return gcd(b,a%b); 
    }
} 
int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    exchange(a,b);
    if(gcd(a,b)==1){//最大公约数是1，互质 
        printf("YES,互质！"); 
    }else{
        printf("NO,不互质！");
    }
    system("pause");
    return 0;
}

 
文章目录
 
写在前面
素数、合数
定理：带余除法
   
整除、因数
$★$命题：除数整除被除数的倍数和
   
公因数、最大公因数
除数与被除数的最大公因数等于除数与余数的最大公因数
辗转相除法:求两整数最大公因数的统一方法
   
互素
$★★$定理：两整数互素的充要条件
证明
    
互素整数的重要性质及推广
   
素数的重要性质
证明
   
算术基本定理
 

 
写在前面
 
最近学习了丘维声教授的课程《数学的思维方式与创新》，总结一下课程中关于素数的一些主要性质及证明。
 
素数、合数
 
设$m$是大于$1$的整数，如果$m$的正因数只有$1$和$m$自身，那么称$m$是一个素数（或质数），否则称$m$是合数。
 
定理：带余除法
 
任给$a,b\in \mathbb{Z}$，且$b\ne 0$，则存在唯一的一对整数$q,r$，使得
 $$a=qb+r,0⩽r<|b|,$$
 其中，$q$和$r$分别称为$a$被$b$除所得的商和余数。
 
整除、因数
 
对于整数$a,b$，如果存在整数$c$，使得
 $$a=cb,$$
 那么称$b$整除$a$，记作$b|a$，否则，称$b$不能整除$a$，记作$b\nmid a$。当$b|a$时，$b$称为$a$的一个因数，$a$称为$b$的一个倍数。
 
任给$a\in \mathbb{Z}$，由于$0=0a$，因此$a|0$，特别地，$0|0$。
整除具有反身性，传递性，但是没有对称性。
 
$★$命题：除数整除被除数的倍数和
 
在$\mathbb{Z}$中，若$b|a_i,i=1,2,\cdots ,s$，则对任意整数$u_1,u_2,\cdots ,u_s$，有
 $$b|u_1{a}_1+u_2{a}_2+\cdots +u_s{a}_s.$$
 
公因数、最大公因数
 
 
如果$c|a$且$c|b$，那么称$c$是$a$与$b$的一个公因数（公约数）。
 
 
整数$a$与$b$的一个公因数$d$如果满足：$a$与$b$的任一公因数都能整除$d$，那么称$d$是$a$与$b$的一个最大公因数（最大公约数）。
 
 
约定： 用$(a,b)$表示两整数间正的最大公因数。
 
 
任给$a\in \mathbb{Z}$，由于$a|a$且$a|0$，所以$a$是$a$与$0$的一个公因数，任取$a$与$0$的一个公因数$c$，显然$c|a$，所以$a$是$a$与$0$的一个最大公因数。
 
 
特别地，$0$是$0$与$0$的最大公因数。
 
 
除数与被除数的最大公因数等于除数与余数的最大公因数
 
在$\mathbb{Z}$中如果有等式
 $$a=qb+r$$
 成立，那么$d$是$a$与$b$的最大公因数当且仅当$d$是$b$与$r$的最大公因数。
 
辗转相除法:求两整数最大公因数的统一方法
 
任给两个整数$a,b$，都存在它们的一个最大公因数$d$，并且$d$可以表示成$a$与$b$的倍数和，即存在整数$u,v$，使得
 $$ua+vb=d.$$
 
互素
 
设$a,b\in \mathbb{Z}$，如果$(a,b)=1$，那么称$a$与$b$互素。
两个整数互素当且仅当它们的公因数只有$\pm 1$。
 
$★★$定理：两整数互素的充要条件
 
两整数$a,b$互素的充要条件是：存在整数$u,v$，使得
 $$ua+vb=1.$$
 
证明
 
 
必要性：由辗转相除法定理即可得到，下证充分性。
 
 
充分性：设$ua+vb=1$成立，只需证明整数$a,b$互素，即证明$(a,b)=1$。任取$a,b$的一个公因数$c$，则有$c|a,c|b$，由定理：除数整除被除数的倍数和，可以得到：$c|ua+vb$，所以$c|1$，证毕。
 
 
互素整数的重要性质及推广
 
 
在$\mathbb{Z}$中，如果$a|bc$，且$(a,b)=1$，那么$a|c$。
 
证明：
 
若$c=0$，$a|c$显然成立；若$c\ne 0$，利用整数互素的充要条件得到：存在整数$u,v$，使得$ua+vb=1$，两边同乘以$c$得到：$uac+vbc=c$，而显然有$a|a,a|bc$，根据命题：除数整除被除数倍数和，得到$a|(uc)a+v(bc)⟹a|c$.
 
  
 
   
性质1的简单应用
 
   
 
    
对于素数$p$, 有$$p|C_p^k,\forall k\in [1,p)$$
 证明:
 对组合数$C_p^k$显然有$(p-k)C_p^k=p{C}_{p-1}^k$, 而显然$(p,p-k)=1$,$p|(p-k)C_p^k$, 所以由性质1, 可得$p|C_p^k$.
 
   
 
  
 
 
在$\mathbb{Z}$中，如果$a|c,b|c$，且$(a,b)=1$，那么$ab|c$。
 
证明：
 
根据$a|c$，有整数$h$使得$c=ha$。由于$b|c$，因此$b|ha$。又由于$(a,b)=1$，因此由性质1得到$b|h$，从而有整数$g$使得$h=gb$，所以有$c=g(ba)$，即得到$ab|c$。
 
推广：
 
在$\mathbb{Z}$中，如果$a_i|c,i=1,2,\cdots ,s$，且$a_1,a_2,\cdots ,a_s$两两互素，那么$a_1{a}_2\cdots a_s|c$.
 
 
在$\mathbb{Z}$中，如果$(a,c)=1$，且$(b,c)=1$，那么$(ab,c)=1$。
 
证明：
 
根据$(a,c)=1,(b,c)=1$，得到：有整数$u_i,v_i,i=1,2$，使得
 $$\{\begin{array}{l}{u}_{1}a+v_{1}b=1\\ u_{2}b+v_{2}c=1\end{array}$$
 将上述两式左右两边分别相乘，得到
 $$(u_1{u}_2)ab+(u_{1}a{v}_2+v_1{u}_{2}b+v_1{v}_{2}c)c=1$$
 于是由整数互素的充要条件得到：$(ab,c)=1$.
 
推广：
 
在$\mathbb{Z}$中，如果$(a_i,c)=1,i=1,2,\cdots ,s$，那么$(a_1{a}_2\cdots a_s,c)=1$。
 
 
素数的重要性质
 
设$p$是大于$1$的整数，则下列命题等价：
 
$p$是素数；
对任意整数$a$，都有$p|a$或者$(p,a)=1$；
对整数$a,b$，从$p|ab$可以推出：$p|a$或者$p|b$；
$p$不能分解成两个比$p$小的正整数的乘积。
 
证明
 
1->2：由于$p$是素数，所以有$(p,a)=1$或者$(p,a)=p$，而后者可得出$p|a$.
2->3：由于$p|ab$，假设$p\nmid a$，则由性质2，有$(p,a)=1$，再由整数互素的性质1，得到$p|b$。
3->4：假设$p=p_1{p}_2,0<p_1<p,0<p_2<p$，则由整除的反身性得到$p|p_1{p}_2$，由性质3得到：$p|p_1$或者$p|p_2$，矛盾。
4->1：任取$p$的一个正因数$a$，则存在正整数$b$，使得$p=ba$，根据性质4，$b=p$或者$a=p$，当$b=p$时，$a=1$，因此$p$的正因数只有$1,p$，从而$p$为素数。
 
算术基本定理
 
任一大于$1$的整数$a$都能唯一地分解成有限多素数地乘积。
 
其中，唯一性是指：如果$a$有两个这样的分解式：
 $$a=p_1{p}_2\cdots p_s=q_1{q}_2\cdots q_t,$$
 则一定有$s=t$，且适当排列因数地次序之后有：
 $$p_i=q_i,i=1,2,\cdots ,s.$$

题目描述：

 
点击打开链接
 
求第k个与n互素的数。就是小用一下互素的性质，如果x与n互素，那么x*t+n肯定与n也互素，所以我们只需算出n以内m个与n互素的数就行了，剩下的数就是m个一循环。
 
AC代码：
 

 
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
const int MOD=21252;

int a[10000010];

int gcd(int x,int y)
{
    return y==0? x:gcd(y,x%y);
}
int main()
{
    int m,k;
    while(cin>>m>>k)
    {
        int j=0;
        for (int i=1;i<=m;i++)
            if (gcd(m,i)==1) a[j++]=i;
        if (k%j!=0)
            printf("%d\n",k/j*m+a[k%j-1]);
        else printf("%d\n",(k/j-1)*m+a[j-1]);
    }
    return 0;
}
 
 
 
 

Description
 
Two positive integers are said to be relatively prime to each other if the Great Common Divisor (GCD) is 1. For instance, 1, 3, 5, 7, 9…are all relatively prime to 2006.
 
Now your job is easy: for the given integer m, find the K-th element which is relatively prime to m when these elements are sorted in ascending order.
 
Input 
 The input contains multiple test cases. For each test case, it contains two integers m (1 <= m <= 1000000), K (1 <= K <= 100000000).
 
Output 
 Output the K-th element in a single line.
 
Sample Input 
 2006 1 
 2006 2 
 2006 3
 
Sample Output 
 1 
 3 
 5 
 
代码与解释
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int pri[1000000];
int gcd(int a, int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int m,k;
    while (~scanf("%d%d",&m,&k))
    {
        int i,t;
        t = 0;
        for (i = 1; i <= m; i++)
        {
            if (gcd(m, i) == 1)
                pri[t++] = i;
/*
先找出比m小的且与m互素的数，且记录总个数t;
当k可以整除t时，也就是第n*t个数，此时为(k/t-1)个m加上比m小的最大素数。
当k不可以整除t时，k/t*个m加上第k%t-1个与m互素且比m小的数就是所求
例如m=9
比m小且与之互素的数为1,2,4,5,7共5个数。
若求第10个与m互素的数就是m+7=16
1,2,4,5,7,10,11,13,14,16是前十个与m互素的数。
若求第7个则是m+prime[1]=11;
*/
        }
        if (k % t)
            printf("%d\n",k/t*m+pri[k%t-1]);
        else
            printf("%d\n",(k/t-1)*m+pri[t-1]);
    }
    return 0;
}