1樓：lcatastrophe
@w2014 的證明應該說是比較完備了，其實個人覺得原題幾乎等同於裴蜀定理。
那就再原Bonus上再加個：如何找到最短的路徑實現兩者相等？
2樓：w2014
簡單回答：
在執行序列***後，a=b=67108864.
因為這麼說就太無聊了，我們給出下面問題的乙個證明：
不過我沒有給出太簡潔證明的能力，為了嚴謹性可能會囉囉嗦嗦，提前道個歉吧…
結論：對於任意正整數a,b，可以如上通過若干步，使得二者相等。
我們約定，能夠通過給出的四種操作所構成的有限長序列，變成相等的數對(a,b)為「好」的。（注：如無特殊說明，下文中「數對」均指「正整數數對」）
首先，我們知道乙個很顯然的結論。
如果有正整數k，那麼(a,b)是好的，等價於(ka,kb)是好的。
（此處記為引理1）
因此我們可以引入第五種操作：將a和b兩側同時除以其最大公因數。（以下記為"操作5"）
如無說明，「基本操作」為「四種操作」之任一；「擴充套件操作」為「五種操作」之任一。
「基本操作序列」和「擴充套件操作序列」分別為「基本操作」和「擴充套件操作」組成的有限長序列。
在這樣的定義下，「好」數對的定義，可以表述為「可以通過乙個『基本操作序列 』使得兩個分量相等的數對。」
很顯然地，我們有，數對為「好」數對的充要條件是：（引理2）
1)它的兩個分量相等；
2)或者存在乙個基本操作op，使得這個數對在經過op後得到的結果是「好」的。
於是我們可以證明，乙個數對是「好」的，等價於這個數對可以通過乙個擴充套件操作序列，使得兩個分量相等。（引理3）
更進一步，等價於乙個數對可以經過若干步擴充套件操作之後，變成數對（1,1）。(引理4)
那麼，我們希望將數對(a,b)變為數對(1,1)，乙個很明顯的方向是將它的各個分量減小。
我們取a+b作為「指標」
對於數對(a,b),如果(a,b)就是(1,1)，顯然是「好」的。
如果a和b不互質，進行操作5，可以使得a和b減小。新得到的數對的兩個分量之和嚴格小於原來的。
如果a,b互質，且不同時為1，那麼：
1）a和b都是奇數。
很明顯a≠b，不妨令a>b，進行a+=b;b+=b;之後再進行操作5.
很明顯，在前兩步後，數對的兩個分量都是偶數，所以操作5約去的公因子不小於2.
於是這幾步操作後，得到的數對的第乙個分量不超過(a+b)/22) a和b一奇一偶
不妨令a為奇數。進行a+=a;之後再進行操作5.
同樣，進行操作5之前，數對的兩個分量都是偶數，操作5約去的公因子不小於2。
新得到的數對的第乙個維度不超過a，第二個維度不超過b/2。新得到的數對的兩個分量之和嚴格小於原數對的。
注意到，正整數數對的分量和也是正整數，而且不小於2；當且僅當數對為(1,1)時，其分量和為2；對於(1,1)以外的任何正整數數對，都可以通過特定的擴充套件操作序列，使得其分量和減小。
於是，對於任意正整數數對，都可以通過特定的擴充套件操作序列，使它變成(1,1)。
也就是，根據引理4，任意正整數數對，都是「好」的。
Q.E.D.
正文中未曾提及的引理0：
對於數對(a,b)，在基本操作序列seq後得到新的數對(a',b')。
那麼對於數對(ta,tb)，在seq後得到的，一定是(ta',tb')。其中，t是正實數。
引理0的證明：考慮只包含乙個基本操作的基本操作序列，易知滿足條件。接下來對序列長度歸納即可。
引理1：(a,b)是「好」的，等價於(ka,kb)是「好」的
引理1的證明：
如果(a,b)是「好」的，經過基本操作序列seq後變成兩個分量相等的數對(x,x)。根據引理0，(ka,kb)在經過seq後變成(kx,kx)，所以(ka,kb)是好的。
如果(ka,kb)是「好」的，經過基本操作序列seq後變成數對(x,x)，那麼(a,b)在經過seq後變成(x/k,x/k)，所以(a,b)也是好的。
引理1得證。
引理2：數對為「好」數對的充要條件是：
1)它的兩個分量相等；
2)或者存在乙個基本操作op，使得這個數對在經過op後得到的結果是「好」的。
證明：若右側1)成立，根據定義自然是「好」數對；
若右側2)成立，經過op後得到的數對可以經過乙個基本操作序列 seq得到分量相等的數對。因此將op新增至seq的開頭，得到的基本操作序列 記為seq2，原數對在經過seq2後兩個分量相等。根據定義，原數對是「好」的。
至此，必要性得證。
若左側成立，且右側1)不成立，則存在乙個基本操作序列 seq，使得原數對經過seq後兩個分量相等，且seq長度不為0.
取seq中第乙個操作為op，原數對經過op後得到的數對記為x。x在經過seq中其它操作後，兩個分量相等。因此x是「好」的。右側2)成立。
至此，充分性也得證。
於是，引理2得證。
引理3：
乙個數對是「好」的，等價於，這個數對可以經過某個擴充套件操作序列，使得兩個維度相等。
引理3的證明：
首先，數對是「好」的，根據定義等價於它可以經過乙個基本操作序列，使得兩個分量相等。根據定義，這樣的序列自然也是擴充套件操作序列，充分性顯然。
如果數對可以經過乙個擴充套件操作序列使得兩個維度相等。
最後得到的數對的兩個維度相等，這一數對顯然是「好」的。
根據定義，以及引理1，如果某個數對是「好」的，那麼經過某個「擴充套件操作」能夠變成它的數對，也是「好」的。
歸納即可知，可以經過乙個擴充套件操作序列，使得兩個維度相等的數對，都是「好」的。
必要性也得證。
引理4：
乙個數對是「好」的，等價於，這個數對可以經過乙個擴充套件操作序列，變成數對(1,1)。
充分性：如果乙個數對是「好」的，根據引理3，它可以經過乙個擴充套件操作序列，變成兩個分量相等的數對。
接下來進行操作5，即可變成數對(1,1)。
必要性：因為(1,1)也是兩個分量相等的數對。根據引理3，必要性顯然。
現有計算機不能解決哪些問題？
計算機 包括圖靈機等類似計算模型 只是二階邏輯的物理實現，二階邏輯上不可判定的問題計算機當然也做不出來。至於人工智慧之類的問題不是做不出來，只是不能在可行時間內計算出來。 楊個毛 Turing Church Thesis 凡是能用物理裝置算出來的，計算機都能算出來。注意這東西是個形式上不嚴密的猜想，...
計算機轉專業問題？
娉婷依依 先客觀的回答幾個問題 1.女生高技術精力和體力的優勢問題。無可厚非，論體力精力，女生比不過男生，客觀的身體原因，但你可以通過運動 健身來不斷提高自己的體力，規劃好時間，把精力用到最重要的地方。2.第二個問題，性別和年齡的問題，女性技術就業比男性好，相信我，男生做技術的太多，辦公室當然也希望...
怎樣學好計算機？
乙個真誠的意見給題主，要想學好任何東西前先問問自己，學好這個東西是要幹什麼，要非常精確，不能泛泛。也許你會想，我學好計算機為了找乙份不錯的工作，但是這其實就是乙個泛泛的目標。具體下來，你要考慮，你想要去什麼級別的企業，心理預期的月薪是多少，這些企業設定的什麼崗位是你感興趣的，它們的職位要求是什麼。也...