你知道下面的梅森數, M1567271, M1567259, M1567103, M1567031, and M1566923,有下列的3134543, 3134519, 3134207, 31340633133847對應因子嗎?上例中的數字都是素數. 使得找的該數們的因子有其困難的程度. 尤其是當素數的值大到一定程度以上如前面所提的例子. 找他們的因子就很難了,甚至於用電腦來找. 相較下,2ab – 1, ab是素數, 證明它是素數且有 (2a– 1) (2b– 1) 的因子就比較容易了. Do you know the following Mersenne Numbers, M1567271, M1567259, M1567103, M1567031, and M1566923, 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 Mcomposite that has the form of 2ab – 1. Note that ab is not a prime.  The following is one of the proofs of 2ab – 1 that shows 2ab – 1 has (2a– 1) and (2b– 1) as its factors.

 

證明:

在二進位的系統中, (2a– 1) = 111...1112其中1重覆a例如 (22*2-1) = 112 * 1012,  (22*3-1) = 112 * 101012, (22*7-1) = 112 * 10101010101012. 其中1012, 101012, 10101010101012是有規律的. 又 (27*2-1) = 11111112 * 100000012 (27*3-1) = 11111112 * 1000000100000012 中的100000012 , 1000000100000012也有規律. 其規律是2ab – 1 = 11…12 (1 重覆a, = 2a – 1) * 10…010…01……12 (1 出現b次其中有0 重覆a – 1 ). 2ab – 1 = 2ba – 1 = 11…12 (1重覆b,= 2b – 1) * 10…010…01……12(1 出現a次其中0 重覆b – 1 ).  2ab– 1 (2a – 1) * (2b – 1) * x.  x 2ab– 1的另一個因子.  (2a – 1) * (2b – 1) 都是2ab– 1因子. 2ab– 1 是素數.

 

Proof: 

In the binary system, (2a– 1) is 1 repeated a times, for example (22-1) = 112, (25-1) = 111112, and (213-1) = 11111111111112.  Observe that  (22*2-1) = 112 * 1012,  (22*3-1) = 112 * 101012, and  (22*7-1) = 112 * 10101010101012.  There is a pattern on multiplicands 1012, 101012, and 10101010101012.  Moreover,  (27*2-1) = 11111112 * 100000012, and (27*3-1) = 11111112 * 1000000100000012.  There is another pattern on multiplicands 100000012 , and 1000000100000012. From the above two patterns, it is generalized that 2ab – 1 can be rewritten as 11…12 (1 repeated a times = 2a – 1) * 10…010…01……12(1 appeared b times in between 0 repeated a – 1 times ). Thus 2ab – 1 = 2ba – 1 can be rewritten as 11…12 (1 repeated b times = 2b – 1) * 10…010…01……12(1 appeared a times in between 0 repeated b – 1 times ).  Therefore, 2ab– 1 has both (2a – 1) * (2b – 1) * x. x is another factor of 2ab– 1.  (2a – 1) * (2b – 1) are the factors of 2ab– 1. Thus 2ab– 1 is not a prime.

 

 

創作者介紹
創作者 mcheng007 的頭像
mcheng007

啟蒙數學

mcheng007 發表在 痞客邦 留言(0) 人氣()