初等數論 整除, 最大公因數, 素數, 数論函數[x], {x}]

索引

• 定理1.1：q\ne 0,\text{ }a=bq+c\text{ }\Rightarrow \text{ }\gcd \left( a,b \right)=\gcd \left( b,c \right)
  • 辗转相除法
  • 定理1.2：\gcd \left( a,c \right)=1,\text{ }\left. c \right|ab\text{ }\Rightarrow \text{ }\left. c \right|b
  • 应用：验证a\in {{\mathbb{Z}}_{\ge 0}}是否为素数。
  • 定理1.3：令a\in {{\mathbb{Z}}_{\ge 1}}的最小非1因子为q，则存在以下结论：1）q是素数；2）若a不是素数，则q\le \sqrt[{}]{a}。
  • 定理1.4：对于a\in {{\mathbb{Z}}_{>1}}，若满足a整除\left( a-1 \right)!+1，则可推得a为素数。
  • 定理1.5：设p是一个素数，则对于任意整数a，有p整除a或\gcd(p,a)=1二者必居其一。
  • • 推论1.5.1：若p是某个素数，且${{a}{1}},{{a}{2}},\cdots ,{{a}_{n}}\in \mat