数论笔记本
发表于 2019-04-25 | 分类于 学习笔记 | 阅读次数:
数论是个好东西.
欧几里德算法(gcd)
欧几里德算法又称辗转相除法,用于计算两个正整数a,b的最大公约数.
$gcd(a,b)=gcd(b,a$ $mod$ $b)$
特别的:$gcd(a,0)=a$
充分性
设c为a,b的公约数
$\because a|c$,$b|c $ (|:整除)
又$\because a=kb+(a$ $mod$ $b),$即$a$ $mod$ $b = a-kb$
$\therefore (a$ $mod$ $b) | c$
设$c$为$b$,$a$ $mod$ $b$的公约数
$\because b|c,