这是为《A Computational Introduction to Number Theory and Algebra （Version 2）》（资源）中某些和ACM用数论有关的习题写的证明。还没看完，好难QAQ
EXERCISE 1.17
已知正整数$a,b,c$满足$\gcd(a,b)=1$，$c\ge(a-1)(b-1)$，
求证：总是存在非负整数$s,t$满足$c=as+bt$
证明1：
当$s\in[0,b-1]$时$as$模$b$的结果恰好构成$b$的完全剩余系，
所以存在$s\in[0,b-1]$使$n\equiv as\mod b$成立，
此时$bt=c-as\ge (a-1)(b-1)-as=(b-1-s)a-(b-1)\ge -b+1$，
即$t\ge\frac{-b+1}{b}>\frac{-b}{b}=-1$。$\Box$
证明2：
考虑其$c=as+bt$存在非整数解$(s,t)$的几何意义，
即直线$y=-\frac{b}{a}x+\frac{c}{a}$在第一象限（含坐标轴）过任意整点。
EXERCISE 1.27
已知$a,b\in Z$，
求证：$\gcd(a+b,\mathrm{lcm}(a,b))=\gcd(a,b)$
证明：
设$d=\gcd(a,b),s=\frac{a}{d},t=\frac{b}{d}$，
易知$\gcd(s,t)=1$，
$\gcd(a+b,\mathrm{lcm}(a,b))$
$=\gcd(d(s+t),\frac{ab}{d})$
$=d\gcd(s+t,st)$
又因$(s+t)\nmid s$且$(s+t)\nmid t$，$\gcd(s+t,st)=1$，
即$\gcd(a+b,\mathrm{lcm}(a,b))=d=\gcd(a,b)$。$\Box$
EXERCISE 2.10
求证：不存在$a,b$满足$7a^3+2=b^3$
证明：
若$7a^3+2=b^3$，
则有$7a^3+2\equiv b^3\mod7$，
即$2=b^3\mod7$
由于$(b+7)^3\equiv b^3\mod7$，
且$1^3\equiv2^3\equiv1,3^3\equiv5^3\equiv6^3\equiv6,4^3\equiv4,7^3\equiv0$，
因此$7a^3+2=b^3$不成立。$\Box$
EXERCISE 2.12
已知整数$a_1,a_2,..a_k,b$和正整数$n$，设$d=\gcd(a_1,…,a_k,n)$，
求证：$a_1x_1+a_2x_2+…+a_kx_k \equiv b\mod n$有解$\{x_i\}_{i=1}^{k}$当且仅当$d|b$
暂无想法，待证
EXERCISE 2.13
暂无想法，待证
EXERCISE 2.16
已知$\{n_i\}_{i=1}^{k}$两两互质，对于整数$\{a_i\}_{i=1}^k,\{b_i\}_{i=1}^k$，设$d_i=\gcd(a_i,n_i)$，
求证：存在$x$满足$\forall i \in [1,k], a_ix\equiv b_i\mod n_i$当且仅当$\forall i\in[1,k],d_i|b_i$
暂无想法，待证
EXERCISE 2.23
求证：$\varphi(nm)=\gcd(n,m)*\varphi(\mathrm{lcm}(n,m))$
证明：
$n=\prod p_{i}^{a_i},m=\prod p_{i}^{b_i}$，
$\gcd(n,m)=\prod p_{i}^{min(a_i,b_i)},\mathrm{lcm}(n,m)=\prod p_{i}^{max(a_i,b_i)}$，
$\gcd(n,m)\varphi(\mathrm{lcm}(n,m))=\prod p_{i}^{min(a_i,b_i)}\prod p_{i}^{max(a_i,b_i)-1}(p_i-1)$
$=\prod p_{i}^{a_i+b_i-1}(p_i-1)=\varphi(nm)$。$\Box$
EXERCISE 2.24
已知$n$有$r$个不同的奇质因子，
求证：$2^r|\varphi(n)$
证明：
$\varphi(n)=\prod p_{i}^{e_i-1}(p_i-1)$，
其中$r$个奇质因子的贡献为$\prod_{i=1}^{r} p_i^{e_i-1}(p_i-1)$，
又因$p_i^{e_i-1}\ge1$且$p_i-1\equiv0\mod2$，
因此$2^r|\varphi(n)$。$\Box$
EXERCISE 2.25
定义$\varphi_{2}(n)=\sum_{i=0}^{n-1}[\gcd(i,n)=1\land\gcd(i+1,n)=1]$，
求证：对于$n=\prod_{i=1}^{r}p_i^{e_i}$，$\varphi_2(n)=n\prod_{i=1}^r(1-2/p_i)$
证明：
考虑$n’=p^e$，对于所有的$a\in[0,n’-1]$，不满足$\gcd(a,n’)=1\land\gcd(a+1,n’)=1$的值有：
$0\times p,1\times p-1,1\times p,$
$2\times p-1,2\times p,$
$…,$
$(p^{e-1}-1)\times p-1,(p^{e-1}-1)\times p，p^e-1$
将$i\times p-1$与$i\times p$配对，将$0\times p$与$p^e-1$配对，
发现共有$p^{e-1}$对不满足条件的数，
因此$\varphi_2(p^e)=p^e-2p^{e-1}=p^e(1-2/p)$，
故$\varphi(n)=\prod_{i=1}^{r}p_i^{e_i}(1-2/p_i)=n\prod_{i=1}^r(1-2/p_i)$。$\Box$