• 解決済み

    @Arsenic

    2023/9/30 21:30

    2 回答

    せせせ整数論ですが

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

    1. 高校生

    ベストアンサー

    ベストアンサー

    @kagomekagome

    2023/10/4 19:43

    （証明）nn を 2k2^k が割り切るような最大の整数 kk を v2(n)v_2(n) と書く．仮定より，

    v2(32m−1)≧n． v_2(3^{2m} - 1) \geqq n．

    ここで lifting-the-exponent lemma（https://en.wikipedia.org/wiki/Lifting-the-exponent_lemma）より，

    v2(32m−1)=v2(3−1)+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)+3≧n． v_2(m) + 3 \geqq n．

    したがって，

    2n−1≦2v2(m)+2≦2log⁡2(m)+2=4m≦3m+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件）

    @ontama_udon

    2023/10/6 22:22

    対偶を示す。

    3m+1<2n−13^m+1<2^{n-1}より、3m−1<2n−13^m-1<2^{n-1}。

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

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

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

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