此頁面將包含與素數相關的證明。由於定義非常相似，與不可約數相關的證明也將出現在此頁面上。
素數 p>1 是其唯一正約數為 1 和 p 的數。
定理： p {\displaystyle p} 是素數，且 p | a b {\displaystyle p|ab} 意味著 p | a {\displaystyle p|a} 或 p | b {\displaystyle p|b} 。
證明：假設 p {\displaystyle p} 是素數，且 p | a b {\displaystyle p|ab} ，且 p ∤ a {\displaystyle p\nmid a} 。我們必須證明 p | b {\displaystyle p|b} 。
考慮 gcd ( p , a ) {\displaystyle \gcd(p,a)} 。因為 p {\displaystyle p} 是素數，它可以等於 1 {\displaystyle 1} 或 p {\displaystyle p} 。由於 p ∤ a {\displaystyle p\nmid a} ，我們知道 gcd ( p , a ) = 1 {\displaystyle \gcd(p,a)=1} 。
根據最大公約數恆等式，存在一些 x , y ∈ Z {\displaystyle x,y\in \mathbb {Z} } ，使得 gcd ( p , a ) = 1 = p x + a y {\displaystyle \gcd(p,a)=1=px+ay} 。
當我們將該式乘以 b {\displaystyle b} 時，得到 b = p b x + a b y {\displaystyle b=pbx+aby} 。
因為 p | p {\displaystyle p|p} 且 p | a b {\displaystyle p|ab} ，我們知道 p | ( p b x + a b y ) {\displaystyle p|(pbx+aby)} ，並且 p | b {\displaystyle p|b} ，如預期的那樣。
