彰師大105年度離散數學問題6?

gcd ( 2^345 - 1 , 2^543 - 1 )
= gcd ( 2^345 - 1 , 2^543 - 1 - (2^345 - 1) )
= gcd ( 2^345 - 1 , (2^345)(2^198 - 1) )
因 2^345 與 2^345 - 1 互質 , 故
= gcd ( 2^345 - 1 , 2^198 - 1 )
類似地
= gcd (2^(345 - 198) - 1 , 2^198 - 1)
= gcd (2^147 - 1 , 2^198 - 1)
= gcd (2^147 - 1 , 2^(198 - 147) - 1)
= gcd (2^147 - 1 , 2^51 - 1)
= gcd (2^(147 - 51×2) - 1 , 2^51 - 1)
= gcd (2^45 - 1 , 2^51 - 1)
= gcd (2^6 -1 , 2^45 - 1)
= gcd (2³ - 1 , 2^6 - 1)
= gcd (2³ - 1 , 2³ - 1)
= 7