【２】初等的整数論的アプローチ

　　３ｎ＋１＝２^m

は，ｍｏｄｎあるいはｍｏｄ３として，

　　１＝２^m

を得るが，ｍ＝０，ｎ＝０となり，これらはあまり有効ではない．

　そこで，ｍｏｄ２として

　　３ｎ＋１＝０

を得る．この場合，ｎは奇数になるから，ｍｏｄ４として

　　ｍ＞１のとき，３ｎ＋１＝０→ｎは４ｋ＋１となることが必要

　　（ｎ，ｍ）＝（５，４）では，５→１６→８→４→２→１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

　ｍｏｄ８として

　　ｍ＞２のとき，３ｎ＋１＝０→ｎは８ｋ＋５となることが必要

　　ｍ＝２のとき，３ｎ＋１＝４→ｎ＝１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

　ｍｏｄ１６として

　　ｍ＞３のとき，３ｎ＋１＝０→ｎは１６ｋ＋５となることが必要

　　ｍ＝３のとき，３ｎ＋１＝８→ＮＧ

　　ｍ＝２のとき，３ｎ＋１＝４→ｎ＝１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

これより

　３ｎ＋１＝２^m

を満たすための必要条件は，ｎが４ｋ＋１，８ｋ＋５，１６ｋ＋５・・・型整数であることである．（ｎ，ｍ）＝（５，４）はひとつの解であるが，他の解を探してみよう．

［１］３ｎ＋１＝１２ｋ＋４　（ｋ＝０は除く）

　ｋ＝１，ｎ＝５→１６＝２^4，ｍ＝４

　ｋ＝５，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝２１，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝８５，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝３４１，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

［２］３ｎ＋１＝２４ｋ＋１６　（ｋ＝０は除く）

　ｋ＝２，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝１０，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝４２，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝１７０，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

　ｋ＝６８２，ｎ＝５４６１→１６３８４＝２^14，ｍ＝１４

［３］３ｎ＋１＝４８ｋ＋１６　（ｋ＝０は除く）

　ｋ＝１，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝５，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝２１，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝８５，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

　ｋ＝３４１，ｎ＝５４６１→１６３８４＝２^14，ｍ＝１４

以上より，

　　３ｎ＋１＝２^m

の解が（ｎ，ｍ）＝（５，４），（２１，６），（８５，８），（３４１，１０），（１３６５，１２），（５４６１，１４），・・・となる．

　すなわち，ｍ＝２ｋのとき，

　　３ｎ＋１＝２^m=２^2k

　　３ｎ＝２^2k−１＝（２^2−１）（２^2k-2＋２^2k-4＋・・・＋２^0）

　　ｎ＝２^2k-2＋２^2k-4＋・・・＋２^2＋２^0＝（２^2k−１）／３

　ｎは２進数表示で，１０１０・・・０１０１と表されることがわかる．

　５2＝１０１

　２１2＝１０１０１

　８５2＝１０１０１０１

　３４１2＝１０１０１０１０１

　１３６５2＝１０１０１０１０１０１

　５４６１2＝１０１０１０１０１０１０１

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝