10=3+7
12=3×4
13=6+7
14=7×2
15=3×5
16=6+10
17=7+10
18=3×6
19=12+7
20=10+10
21=3×7
22=12+10
23=13+10
24=14+10
25=15+10
26=16+10
27=17+10
28=18+10
29=19+10
30=20+10
31=21+10
32=22+10
・・・
答えは「11円」。
👧ライフの腐った寿司。
問題番号18のこたえ。
gcd(p,q)=1であるとする。
N＞pq
であるとき、Nは正整数s,t≧1をつかって
ps+qt=Nとあらわせる。
なぜなら、
N＞pqに対して
N-p,N-2p,N-3p,・・・,N-qp
とq個の数を考えると
これらのどの二つもqで割った剰余が異なるので、
また剰余は
0,1,2,…,q-1のq種類のため、鳩ノ巣論法により
このどこかに「あまり0」となるs番目、
q｜(N-sp)
となる1≦s≦qがあり、その商であるk、
N-sp=kq,1≦k≦qが存在するからである。
よって
N≧pq+1なら正整数解s,tが存在するとわかる。
当然だが、これはN-p-q≧pq-p-q+1なら非負整数解s-1,t-1が存在する
ことを意味する。
そして「pq-p-q」には非負整数解はありえない
なぜなら整数解x,yをおいて
pq-p-q=px+qyとすると、
p(q-1-x)=q(y+1)となり
y+1=ps,q-1-x=qs、
つまり
x=q-qs-1
y=ps-1
となるが、パラメーターである整数sをどう選んでもxまたはyが＜0となってしまうからである。■
