すでに解決していますが, 役に立つところもあると思うので回答したいと思います.
16=2^4で割り切れる. これは少なくとも2で4回割り切れると考えることが出来ます.
あとはf(m, n)が2乗を含むことに着目して簡単にする方法も考えます.
***
まずf(m, n)=(m+1)n^2+am^2+8とも書けます.
ここで2を法とした剰余類を考えると, aは奇数なのでa≡1[(mod 2)は以下省きます.]です.
m≡0ならばf(m, n)≡n^2で条件を満たすためにはn≡0であればよいわけです.
m≡1ならばf(m, n)≡1なので条件を満たせません. 以上からmとnは少なくとも偶数です.
m=2m', n=2n'と書くと, f(m', n')=4{(2m'+1)n'^2+am'^2+2}
f(m', n')が8で割り切れるためにはam'^2+n'^2≡0 (mod 2)が必要です[2m'n'^2+2は偶数です].
これを満たすようなm', n'は2を法として, m'≡0, n'≡0あるいはm'≡1, n'≡1に限られます.
前者の場合は適当な整数m'', n''を用いてm=4m'', n=4n''と書けます. このとき
f(m'', n'')=16(4m''n''^2+am''^2+n''^2)+8となるので16では割り切れません.
後者の場合は適当な整数m'', n''を用いてm=2(2m''+1), n=2(2m''+1)と書けます.
このとき定数項以外は明らかに16の倍数になります. すなわち
f(m'', n'')=8(2m''+1)(2n''+1)^2+4a(2m''+1)^2+4(2n''+1)^2+8
=16N+4(a+1). 但しNは残りの項です.
したがってf(m, n)が16で割り切れることと(a+1)が4で割り切れることは同値です.
以上から求めるべきaの条件は, aを4で割ったとき3余るような整数, ということになります.
ほぼ写しただけで申し訳ないですが、ここまでできました。ここからどうすればいいでしょうか?