初等數論中判斷質數的方法

if p≡1 mod3 then 3|(p+2)，很顯然p+2是質數，矛盾！

同理p≡2 mod3不成立

p被3整除，p是質數，只能是3

模幾是幾乎沒有定數的，很靈活，一般是一般化，模3，5，7，11等又是題目也會有所暗示，對於二次式，以5為例，你寫一下他的完全剩餘系，就知道一個數平方後模5只有寥寥幾種情況，7也是。有時候3次方要模9（如果需要的話），4次方模16.

但是沒有定論，數論就是很靈活的，要活學活用。

質數的判斷

試除法： 檢查所有可能成為n的因子的數，若沒有找到因子，則證明這個數是一個質數

一種樸素的做法就是從2遍歷到N-1觀察有無N的因子，若沒有則説明N為質數，依據的想法是N的因子必然在1~N的範圍內