质数.md

一个正整数，如果不等于$1$而且除了自己和$1$没有其他正因数，则称其为一个质数（也称为素数）。否则称其为合数。

定理

1. 质数$p$和$a$互质，当且仅当$p\not\mid a$

   证明：若$p\mid a$，则$p$与$a$存在公因数$\pm p$，两者不互质，矛盾。若$p\not\mid a$，则$\pm p$不是$p,a$的公因数，而$p$除了$\pm p$只有因数$\pm1$，因此只有$\pm 1$才可能是$p,a$的公因数，即二者互质。

2. 显然，两个不同的质数互质

3. 若质数$p$整除$a_1a_2\cdots a_n$，则$p$整除$a_1,a_2,\cdots,a_n$之一

   证明：如果不是这样，$p$不能整除$a_1,a_2,\cdots,a_n$中的任意一个，于是根据定理一，$p$与$a_1,a_2,\cdots,a_n$互质，于是根据互质的这个定理，$p$与$a_1a_2\cdots a_n$互质，然而$p\mid a_1a_2\cdots a_n$，矛盾