若 p235 1 则 p是25 1 = 31或27 1 = 127的素因数 或者 p 1 (mod 70)
由于 31和127是素数 并且 235 1 = 31*127*8727391
所以，235 1的另外的素因数p只可能在数列
71，211，281， (5) 中 经检验，得到8727391 = 71*122921. 显然，122921的素因数在31，127或者数列(5)中 说明，122921不能被31和127整除，也不能被数
呢，这就是下面要讲的欧拉定理.
欧拉定理 设m为正整数，ɑ为
任意整数，且（ɑ， m ）=1，则
aφm 1modm,其中φm表示1，2，...，m
中与m互素的正整数的个数.
证明：
( 1 ) 令Z n = {x1,x2,...,xφn}
S = {a×x1（m od n）,a×x2（m od n）,...,a×xφn（ m od n）}
（2）
aφn x1 x2...xφn (m odn) ≡(ax1) (ax2 ) ... (a xφn )(m od n) ≡(ax1(m od n))×(ax2(m od n)) ... (axφn (m odn))(m od n)
对比等式的左右两端，因为 xi (1 ≤ i ≤ φ(n)) 与 n 互质，所以 aφ(n) ≡ 1 mod n （消去律）.
则 Zn = S .
① 因为 a 与 n 互质， xi (1 ≤ i ≤ φ(n)) 与 n 互质， 所
以 a * xi 与 n 互质，所以 a * xi mod n ∈ Zn .
② 若 i ≠ j ， 那么 xi ≠ xj，且由 a, n互质可得
a*
xi mod n ≠ a * xj mod n （消去律）.
