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

OMCB043-A

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

$\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 \neq 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 \leq y \leq z$ と仮定しておく。
　$x=1$ のとき、$(y+1)(z+1)=n$ となるので、$n$が素数なら解は存在しない。$n$が合成数なら、$n$の約数の個数の$1/2$個くらいの解がありそうである。

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

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

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

　$26 \leq n \leq 35$ のとき、$x \geq 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 \geq 2$ の解が存在し、それ以外のときは $x \geq 2$ の解が存在しない。特に、$n=31$ のときは正整数解 $(x,y,z)$ が存在しないことがわかる。

　$36 \leq n \leq 58$ のとき、$x \geq 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 \geq 2$ の解が存在するか判定するには、考えられる $(x,y)$ すべてに対して $xy+1$ が $n-x-y$ を割り切るかを調べればよい。のだが、うーん……。それ以上はわからない。

終

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