素数

一、素数

素数(又称质数)是指在大于1的自然数中,除了1和它本身,没有其他正因数的数。

例如,2、3、5、7和11是素数,而4、6和8则不是素数,因为它们可以被1和它本身之外的其他整数整除。

注意:最小的素数为2。

算术基本定理

二、算术基本定理

算术基本定理(Fundamental Theorem of Arithmetic),也称为素数分解定理,是数论中的一个核心定理。它描述了任何大于1的整数都可以唯一地表示为素数的乘积(不考虑素数的顺序)。具体表述如下:

定理表述

对于任意大于1的整数 n,它可以唯一地表示为有限个素数的乘积形式:

$$n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}$$

其中,p1, p2, …, pk是互不相同的素数,α1, α2, …, αk 是正整数。这个表示法是唯一的,除了素数的排列顺序外。

费马小定理

三、费马小定理

费马小定理(Fermat’s Little Theorem)是数论中的一个重要定理,描述了在特定条件下的整数幂的同余性质。具体来说,对于一个质数 p 和一个整数 a,如果 a 不是 p 的倍数,那么 ap-1 次方减去1总是能够被 p 整除。用数学语言表达为:

$$a^{p-1} \equiv 1 \ (\text{mod} \ p)$$

这句话可以读作:“a 的 (p-1) 次方与 1 在模 p 下同余”

定理内容:

如果 p 是一个素数,且 a 是一个整数,且 a 不被 p 整除(即 ap 互质),那么:

$$a^{p-1} \equiv 1 \ (\text{mod} \ p)$$

更一般地,对于任何整数 a,费马小定理可以表述为:

$$a^p \equiv a \ (\text{mod} \ p)$$

这意味着,当你将整数 ap 次方除以 p 时,其余数是 a 本身。