Problem:
Solution:
Suppose $ n = ab $ is not prime, then we can write $ 2^{ab} = (2^{a})^b $. Applying the identity we just proved in the previous problem, we have:
$ 2^{ab} - 1 = (2^{a})^b - 1 = (2^{a})^b - 1^b = (2^a - 1)(\cdots) $.
Therefore if $ a \ne 1 $, we have a non-trivial factor for $ 2^{ab} - 1 $.
The contradiction show $ n $ has to be prime.
Solution:
Suppose $ n = ab $ is not prime, then we can write $ 2^{ab} = (2^{a})^b $. Applying the identity we just proved in the previous problem, we have:
$ 2^{ab} - 1 = (2^{a})^b - 1 = (2^{a})^b - 1^b = (2^a - 1)(\cdots) $.
Therefore if $ a \ne 1 $, we have a non-trivial factor for $ 2^{ab} - 1 $.
The contradiction show $ n $ has to be prime.
No comments:
Post a Comment