a+b+c+abc (OMCB043-A)

OMCB043-A

　 Y0ne 氏による以下の問題をアレンジしてみよう。

$\mathrm{mod}p$バージョンを考える。

　$a$と$b$を決めたら$c$が決まるみたいな方向性で考えよう。$a+b+c+abc=a+b+(ab+1)c$ なので、$a$と$b$を固定したとき、$(ab+1)c\equiv -a-b$ を満たす$c$が存在するか考えればよい。$ab+1\equiv 0$かどうかで場合分け。

　(1) $ab+1\equiv 0$のとき
　$-a-b\equiv 0$でなければ$c$は存在しない。つまり、$ab+1\equiv 0$かつ$a+b\equiv 0$を満たす$(a,b)$の個数を求めればよい。$b\equiv -a$なので$a^2\equiv 1$、よって$a=1$または$a=p-1$である。$a$と$b$は$(a,b)=(1,p-1),(p-1,1)$の$2$通り。$c$は何でもいいので、$(a,b,c)$は$2p$個ある。

　(2) $ab+1\not\equiv 0$のとき
　$p$は素数なので、$(ab+1)c\equiv -a-b$ を満たす$c$が唯一存在する。
　$ab\equiv -1$となる$(a,b)$は$p-1$個ある（$a\ne 0$なら、$ab\equiv -1$となる$b$が一意に定まる。$a=0$なら$ab\equiv -1$なる$b$は存在しない）ので、$ab+1\not\equiv 0$となる$(a,b)$は$p^2-(p-1)=p^2-p+1$個ある。したがって、$(a,b,c)$は$p^2-p+1$個である。

　以上より、問題の解答は$p^2+p+1$個である。

一般化

　次の問題を考える。

　先ほどと同じように考えられる。
　$a$と$b$を固定したとき、$(ab+1)c\equiv k-a-b$ を満たす$c$が存在するか考える。$ab+1\equiv 0$かどうかで場合分け。

　(1) $ab+1\equiv 0$のとき
　$k-a-b\equiv 0$でなければ$c$は存在しない。つまり、$ab+1\equiv 0$かつ$k-a-b\equiv 0$を満たす$(a,b)$の個数を求める。$b\equiv k-a$なので、
　$a^2-ka\equiv 1$
$p$は奇素数であるから、これは
　$(2a-k{)}^2\equiv k^2+4$
と同値。よって、$k^2+4$が平方剰余であるかどうかで場合分け。

　(ア) $k^2+4$が平方剰余で、$k^2+4\not\equiv 0$のとき
　$a$は$2$つ存在し、それぞれについて$b$が$1$つに定まる。$c$は何でもいいので、$(a,b,c)$は$2p$個ある。
　(イ) $k^2+4\equiv 0$のとき
　$a$は$1$つだけ存在し、$b$も$1$つに定まる。$c$は何でもいいので、$(a,b,c)$は$p$個ある。
　(ウ) $k^2+4$が平方剰余でないとき
　$a$は存在しないので、$(a,b,c)$は$0$個。

　(2) $ab+1\not\equiv 0$のとき
　$(ab+1)c\equiv -a-b$ を満たす$c$が唯一存在する。したがって、$(a,b,c)$は$p^2-p+1$個である。

　以上より、問題の解答は、
　・$k^2+4$が平方剰余で、$k^2+4\not\equiv 0$のとき：$p^2+p+1$個
　・$k^2+4\equiv 0$のとき：$p^2+1$個
　・$k^2+4$が平方剰余でないとき：$p^2-p+1$個
である。

　ちなみに、$p=2$としても上の解答に符合する。

等式なら？（5/24追記）

　 umezo 氏によるOMCB012-Cも同じ形の式である

　一般化した問題を考えてみる。

　さて、……。どうすんのこれ？
　わからなかったので、解が存在するかどうかだけ愚直に調べてみることにする。

　まず、$x\le y\le z$ と仮定しておく。
　$x=1$ のとき、$(y+1)(z+1)=n$ となるので、$n$が素数なら解は存在しない。$n$が合成数なら、$n$の約数の個数の$1/2$個くらいの解がありそうである。

　$x\ge 2$ のときは、$y$にも具体的な数を代入して調べるしかないか……。

　$x=y=z=2$ のとき $n=14$ であるから、$n\le 13$ のときは、$x\ge 2$ の解は存在しない。よって、特に$n$が$13$以下の素数であるとき、正整数解 $(x,y,z)$ は存在しない。あと、$n=1$も無理やね。

　$14\le n\le 25$ のとき、$x\ge 2$ なら $x=y=2$ とならざるを得ない（$x=2,y=3,z=3$のとき$n=26$）。このとき、$5z=n-4$ となる。つまり、$n=14,19,24$ のときは $x\ge 2$ の解が存在し、それ以外のときは $x\ge 2$ の解が存在しない。特に、$n=17,23$ のときは正整数解 $(x,y,z)$ が存在しないことがわかる。

　$26\le n\le 35$ のとき、$x\ge 2$ なら $x=y=2$ または $x=2,y=3$ である。$x=y=2$ のときは $5z=n-4$ であり、$x=2,y=3$ のときは $7z=n-5$ である。よって、$n=26,29,33,34$ のときは $x\ge 2$ の解が存在し、それ以外のときは $x\ge 2$ の解が存在しない。特に、$n=31$ のときは正整数解 $(x,y,z)$ が存在しないことがわかる。

　$36\le n\le 58$ のとき、$x\ge 2$ なら $x=y=2$ または $x=2,y=3$ または $x=y=3$ または $x=2,y=4$ である。
　$x=y=2$ のときは $5z=n-4$
　$x=2,y=3$ のときは $7z=n-5$
　$x=y=3$ のときは $10z=n-6$
　$x=2,y=4$ のときは $9z=n-6$
である。
　よって、$n=37,41,43,53$ のときは正整数解 $(x,y,z)$ が存在しないことがわかる。

　$n$が与えられたときに $x\ge 2$ の解が存在するか判定するには、考えられる $(x,y)$ すべてに対して $xy+1$ が $n-x-y$ を割り切るかを調べればよい。のだが、うーん……。それ以上はわからない。

終

　等式になった瞬間難しいな。$\mathrm{mod}p$ の場合については、この調子で $a+b+c+d+abcd$ をやるぞ、と思って考えてみたけど、よくわからなかった(>_<)