解決済み

せせせ整数論ですが

m,nm,nを自然数とする。32m13^{2m}-12n2^nで割り切れる時、3m+12n13^m+1≧2^{n-1}が成り立つことを示せる方はいらっしゃいますか?

ベストアンサー

ベストアンサー

(証明)nn2k2^k が割り切るような最大の整数 kkv2(n)v_2(n) と書く.仮定より,

v2(32m1)n v_2(3^{2m} - 1) \geqq n.

ここで lifting-the-exponent lemma(https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma)より,

v2(32m1)=v2(31)+v2(3+1)+v2(2m)1=v2(m)+3 v_2(3^{2m} - 1) = v_2(3 - 1) + v_2(3 + 1) + v_2(2m) - 1 = v_2(m) + 3

であるから

v2(m)+3n v_2(m) + 3 \geqq n.

したがって,

2n12v2(m)+22log2(m)+2=4m3m+1\begin{aligned}2^{n - 1} &\leqq 2^{v_2(m) + 2} \leqq 2^{\log_2(m) + 2} = 4m \leqq 3^m + 1.\end{aligned}

これが示すべきことであった.■


lifting-the-exponent lemma の証明は初等的ですが幾らか行数を要するので上のリンク先の記事へ説明を譲ります.


そのほかの回答(1件)

対偶を示す。

3m+1<2n13^m+1<2^{n-1}より、3m1<2n13^m-1<2^{n-1}

隣り合う偶数について、片方が4で割り切れ、もう片方は4で割り切れないことから、3m+1,3m13^m+1,3^m-1の片方は44で割り切れるが、もう片方は44で割り切れない偶数である。

このうち44で割り切れる方も2n12^{n-1}未満であることから、2n12^{n-1}未満の数でしか割り切れない。

よって、32m1=(3m+1)(3m1)3^{2m}-1=(3^m+1)(3^m-1)2n2^nで割り切れない。

対偶が真であるため、この命題も真である。