整数問題です。お願いします。

質問

m,nは正整数とする。

5以上のすべての素数pは
p=2^m+3^n　　または
p=2^m-3^n　　または
p=3^m-2^n　　の形で表せるか。

回答No.3

FT56F001 · ベストアンサー

>法の取りかたに工夫がいるんですね。
2が原始根になって，2^nがmod　pのすべてを回ると証明になりません。
2^n≡1，3^m≡1がなるべく小さなn,mでなりたつpを探しました。

回答No.5

staratras

No.4です。3^nの末尾の数を考察している部分の右辺と左辺の表記が逆になっていました。失礼しました。

なお、64の代わりに128(2^7)を法とすれば、No.4のやり方で71の場合も反例となることが示せます。

2^mと3^nの和で表せないことは容易に分かりますが、差の場合のポイントは3^nを128で割った余りが
3→9→27→81→115→89→11→33→99→41→123→113→83→121→107→65→67→73→91→17→51→25→75→97→35→105→59→49→19→57(n=30)→43→1→3→(以下繰り返す）→9→27…周期32で循環することです。（ここに71がないことにも注意）

このことから2^m=3^n+71を満たすｎがあるとすれば128=71+57より、n=32p+30の場合に限られることがわかりますが、3^(32p+30)の末尾の数は常に9なので、3^n+71の末尾の数は常に0になり、2^mの末尾がとり得る数にはなりません。よって2^m=3^n+71、すなわち71=2^m-3^nは成り立たず、また余りに71がないことから71=3^m-2^nも成り立ちません。

回答No.4

staratras

すべての素数pが
p=2^m+3^n …（１） または
p=2^m-3^n　…（２）　または　
p=3^m-2^n　…（３）　の形で表せるか
あまりエレガントな証明ではありませんがp=53が反例であることを示します。

53=2^1+51=2^2+49=2^3+45=2^4+37=2^5+21<2^6=64 なので（１）の形式では表せません。

次に（２）の形式で表せたとすると、53=2^m-3^n より　
2^m=3^n+53…（２’） となります。m≦５のときこれを満たす正の整数nはないのでm≧６とします。ここで（２’）の両辺を64=2^6で割った余りを考えますと、m≧6より左辺は割りきれて余りは０なので,右辺も割りきれるためには3^nを64で割った余りが64-５３=11にならなければなりません。
ここで3^nを64で割った余りを考えますと、n=1,2,3…のとき次の通りです。
3→9→27→１７→51→25→11(n=7）→33→35→41→59→49→19→57→43→1→3(以下繰り返す）→9→27…（４）このように周期16で繰り返しますので題意を満たすのはn=16p+7(p:負でない整数）のときです。

一方3^nの末尾の数を計算すると、3^2=9,3^3=27,3^4=81,3^5=243だから
３→９→７→１→３→９→７(n=7）→１→３…と周期４で循環するため、常に3^(16p+7)の末尾の数は７です。したがってこれに53を加えた（２’）の左辺3^n+53の末尾の数字は０となりますが、０は右辺の2^mがとり得る末尾の数字ではありません。よって（２’）は成立せず、５３は（２）の形式では表せないことがわかります。

また（3）の形式で表せたとすると、53=3^m-2^n より　
3^m=2^n+53 …（３’）となりますが、ここでn≦5のときこれを満たす正の整数mはないのでn≧6とします。このとき両辺を64=2^6で割った余りを考えますと、n≧6より2^nは６４で割りきれ右辺の余りは５３です。左辺の3の累乗を64で割った余りは上記（４）で示したように循環し、５３にはなりません。したがって（３’）は成立せず、５３は（３）の形式でも表せません。

よって素数５３は２の累乗と3の累乗の和や差では表せません。

回答No.2

FT56F001

「正の整数n,mに対して，
2^m+3^n，2^m-3^n，3^n-2^mのどの形でも53にならない」
ことを示します。
(以下，もっとスマートに証明できるかもしれませんが，とりあえず思いついた形です)

まず，53=3+50=9+44=27+26なので，53=3^n+2^mの形にはなりません。

次にmod73の剰余系合同式を考えます。
2^m(m=0,1,2,3・・・)をとると，
1,2,4,8,16,32,64,55,37,1となり，
2^9≡1(mod73)になってその後は繰り返します。

3^n(n=0,1,2,3・・・)をとると，
1,3,9,27,8,24,72,70,64,46,65,49,1となり，
3^12≡1となってその後は繰り返します。

3^n-2^m=53になるとすると，2^m+53=3^nになります。
2^m+53≡54,55,57,61,69,12,44,35,17,54,55(mod73)と繰り返すので，
3^nの中にmod73で一致する物がありません。

2^m-3^n=53になるとすると，2^m-53≡2^m+20≡3^nになります。
2^m+20=21,22,24,28,36,52,11,2,57,21,22と繰り返すので
3^nの中で一致するのは2^2+20=24≡3^5だけです。

すなわち，mod73で考えると，
2^(2+9k)-3^(5+9k')=53の形しかありえないことになります。

続いて，mod7の剰余系合同式を考えます。
2^m(m=0,1,2,3,・・・)をとると，
1,2,4,1,2,4の繰り返しになり，2^3≡1(mod7)です。
しかし，2^(2+9k)の形しかないので，2^m≡4(mod7)
となります。しかし，53≡4(mod7)ですから
2^(2+9k)-3^n=53がなりたつためには，4-0=4，すなわち
3^nが7の倍数にならなければなりません。これはありえないので，
この形は存在しないことになります。

よって，2^m+3^n，2^m-3^n，3^n-2^mのどの形でも53にならないことがわかりました。

お礼

ありがとうございます。
なるほど理解できました。
法の取りかたに工夫がいるんですね。

回答No.1

FT56F001

ざっと数値実験してみました。
100以下の素数のうち，p=53,p=71が反例になるのではないかと思います。
(他の100以下の素数は，提案の形で表せます)

ただし，p=2^m-3^n，p=3^m-2^n　の形について，
n<20,m<20の範囲を調べただけなので，
それ以上の範囲にない，ということは確かめていません。

　 5 = 2^ 1 + 3^ 1
　7 = 2^ 2 + 3^ 1
11 = 2^ 3 + 3^ 1
13 = 2^ 2 + 3^ 2
17 = 2^ 3 + 3^ 2
19 = 2^ 4 + 3^ 1
23 = 3^ 3 -　2^ 2
29 = 2^ 1 + 3^ 3
31 = 2^ 2 + 3^ 3
37 = 2^ 6 - 3^ 3
41 = 2^ 5 + 3^ 2
43 = 2^ 4 + 3^ 3
47 = 2^ 7 - 3^ 4
53 ??
59 = 2^ 5 + 3^ 3
61 = 2^ 6 - 3^ 1
67 = 2^ 6 + 3^ 1
71 ??
73 = 2^ 6 + 3^ 2
79 = 3^ 4 -2^ 1
83 = 2^ 1 + 3^ 4
89 = 2^ 3 + 3^ 4
97 = 2^ 4 + 3^ 4

補足

ありがとうございます。
やはり反例が証明できないです。