--- title: 素数测试 费马小定理 辗转相除法 url: 'https://yayi.site/archives/素数测试费马小定理辗转相除法' categories: 算法与设计 cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/結城·友奈.png' tags: 'gcd,素数测试' abbrlink: c680ce7e date: 2020-09-23 20:37:24 updated: 2021-05-14 22:04:55 --- ## 素数测试 素数除了1和自己外没有除数的自然数 n\>1 可以整除意味着mod为0 --- ### 费马小定理 $$ p =prime number $$ $$ n