啟蒙數學

你知道下面的梅森數, M_1567271, M_1567259, M_1567103, M_1567031, and M_1566923,有下列的3134543, 3134519, 3134207, 3134063和3133847對應因子嗎？上例中的數字都是素數. 使得找的該數們的因子有其困難的程度. 尤其是當素數的值大到一定程度以上如前面所提的例子. 找他們的因子就很難了,甚至於用電腦來找. 相較下，2^ab – 1, 其ab不是素數, 證明它不是素數且有 (2^a– 1) 和(2^b– 1) 的因子就比較容易了. Do you know the following Mersenne Numbers, M_1567271, M_1567259, M_1567103, M_1567031, and M_1566923, have factors as 3134543, 3134519, 3134207, 3134063 and 3133847, respectively?  The above numbers are all primes that contribute the difficulty nature for people to find their cofactors.  When the values of the prime numbers become large to some extend as the aforementioned examples, it is hard to obtain their cofactors, even with the aid of a computer. On the other hand, it is relatively easier to prove and find the cofactor of M_composite that has the form of 2^ab – 1. Note that ab is not a prime.  The following is one of the proofs of 2^ab – 1 that shows 2^ab – 1 has (2^a– 1) and (2^b– 1) as its factors.

證明:

在二進位的系統中, (2^a– 1) = 111...111₂其中1重覆a次.  例如 (2^2*2-1) = 11₂ * 101₂,  (2^2*3-1) = 11₂ * 10101₂, 和 (2^2*7-1) = 11₂ * 1010101010101₂. 其中101₂, 10101₂, 和1010101010101₂是有規律的. 又 (2^7*2-1) = 1111111₂ * 10000001₂ 和 (2^7*3-1) = 1111111₂ * 100000010000001₂ 中的10000001₂ , 和100000010000001₂也有規律. 其規律是2^ab – 1 = 11…1₂ (其中1 重覆a次, = 2^a – 1) * 10…010…01……1₂ (1 出現b次其中有0 重覆a – 1 次). 故2^ab – 1 = 2^ba – 1 = 11…1₂ (1重覆b次,= 2^b – 1) * 10…010…01……1₂(1 出現a次其中0 重覆b – 1 次).  故2^ab– 1有 (2^a – 1) * (2^b – 1) * x.  x 是2^ab– 1的另一個因子.  (2^a – 1) * (2^b – 1) 都是2^ab– 1的因子. 故2^ab– 1 不是素數.

Proof: 

In the binary system, (2^a– 1) is 1 repeated a times, for example (2²-1) = 11₂, (2⁵-1) = 11111₂, and (2¹³-1) = 1111111111111₂.  Observe that  (2^2*2-1) = 11₂ * 101₂,  (2^2*3-1) = 11₂ * 10101₂, and  (2^2*7-1) = 11₂ * 1010101010101₂.  There is a pattern on multiplicands 101₂, 10101₂, and 1010101010101₂.  Moreover,  (2^7*2-1) = 1111111₂ * 10000001₂, and (2^7*3-1) = 1111111₂ * 100000010000001₂.  There is another pattern on multiplicands 10000001₂ , and 100000010000001₂. From the above two patterns, it is generalized that 2^ab – 1 can be rewritten as 11…1₂ (1 repeated a times = 2^a – 1) * 10…010…01……1₂(1 appeared b times in between 0 repeated a – 1 times ). Thus 2^ab – 1 = 2^ba – 1 can be rewritten as 11…1₂ (1 repeated b times = 2^b – 1) * 10…010…01……1₂(1 appeared a times in between 0 repeated b – 1 times ).  Therefore, 2^ab– 1 has both (2^a – 1) * (2^b – 1) * x. x is another factor of 2^ab– 1.  (2^a – 1) * (2^b – 1) are the factors of 2^ab– 1. Thus 2^ab– 1 is not a prime.