5X＋7Yで表せない素数全て列挙せよ。ただし、XとYは0以上の整数とする。 この問題を教えてください

5X＋7Yで表せない素数全て列挙せよ。ただし、XとYは0以上の整数とする。

この問題を教えてください！

No.4 回答者： lon_donburi_dge 回答日時： 2020/02/02 10:20

すみません。

人の回答に茶々を入れるのもなんですが…

#3様の解答だと、35以下の数字は(X,Y)=(1,0),(0,1)を除き、
5X+7Yで表せない、というスタンスになっていませんか。

実際に、答えで出していただいた数字のうち、17、29、31は
5X+7Yで表せますし。

ちなみに自分が24以上の数字は5X+7Yで表せるとした根拠は、#3のようなかっこいい方法ではなく、
以下のような泥臭い方法になります。

***
5の倍数の数字の一の位は0または5となる。
なので、一の位が1となる数字を5X+7Yで表すためには、7Yの一の位が1または6でなければならない。
よって、ある数字が5X+7Yで表せるかを調べるためには、一の位で場合分けすればよい。

ここで、一の位が1となる数字が5X+7Yで表せるとすれば、その数字よりも大きい一の位が1となる数字は
5X+7Yで表すことができる（∵10の倍数は5Xで表せる）
よって、一の位で場合分けをして、5X+7Yで表される最小の数字（通常7Y）を列挙すれば、
ある数字以上のすべての数字が5X+7Yで表される最小の数字を求めることができる。
ただし、一の位が6については、5×0+7×8=56だが、5×1+7×3=26であるため、5+7Yについても
考慮に入れなければならない。

i)一の位　1,6　21、26以上の数字は5X+7Yで表される
ii)一の位　2,7　7、12以上の数字は5X+7Yで表される
iii)一の位　3,8　28、33以上の数字は5X+7Yで表される
iv)一の位　4,9　14、19以上の数字は5X+7Yで表される
v)一の位　5,0　すべての数字は5X+7Yで表される

上記より、23は5X+7Yで表せない。逆に言えば24以上の数字は5X+7Yで表すことができる。

No.3 回答者： drjoyhistory 回答日時： 2020/02/01 23:20

5X+7Y=Ｎ（N: 整数）とする。

１つの整数解は(X,Y)=(3N,-2N)
よって5(X-3N)=-7(Y+2N)
ということは、
X-3N=-7k, Y+2N=5k (k:整数)とおける
したがって、
X=3N-7k, Y=-2N+5k (k:整数)
X>0, Y>0として
3N-7k>0, -2N+5k>0
だから2N/5<k<3N/7
kは整数だから
3N/7-2N/5=N/35>1
N>35のとき、つまりN≧36のときは整数kが必ず存在する
5X+7Yは36以上は表せるということだから、35までの素数が答えだが、
(X,Y)=(1,0),(0,1)のときを除外すると
2, 3, 11, 13, 17, 23, 29, 31

No.2 回答者： lon_donburi_dge 回答日時： 2020/02/01 18:29

これって23より小さい素数を列挙して、その中から5X+7Yを満たす数を除外すれば

良いのでは？

確かに素数は限りなくあるけど、24以上の数字はすべて5X+7Yで表現できるでしょ。

No.1 回答者： 銀鱗 回答日時： 2020/02/01 17:36

＞素数全て列挙せよ。

「無茶言うな」と回答欄に書いておきましょう。
23,249,425【桁】の素数を書けとか、洒落にならないぞ。

・・・余談・・・

たぶん条件が書かれた箇所をすっとばして投稿しちゃったんだろうね。
素数の桁数がどこかに書かれているはずだ。
それを「補足」に書いてみよう。

設問の意味を正しく理解していないのだろうと思う。
だから設問の一部だけを取り出して投稿しちゃうんだ。
用語や単語の意味が分からなければ調べる！
これ、当たり前のことですよ。