Bu soruda bir sayının iki kare toplamının $3\pmod 4$ asallarının üstünün çift olması gerektirdiğini kullanacağız.
Lemma : $v_p(P(a))=r$, $p\equiv 3 \pmod 4$ , $N,a$ tamsayılar , $M>r$ eşitsizliğini sağlayan en küçük tamsayı ise
$$N\equiv a \pmod{p^M}$$ ise $$P(N)\equiv P(a) \pmod{p^M}$$ sağlanmalıdır. Çünkü polinomun açılım versiyonunda her terim için $2$ kuvvet farkı uygulanması yardımıyla $N-a\mid P(N)-P(a)$ olduğu söylenebilir. Buradan $p^M \mid N-a$ olduğundan dolayı ispat biter.
Buradan yola çıkarak $v_p(P(N))=r$ olduğunu gösterelim. $P(a)=p^r.u$ olacak şekilde $p \not \mid u$ tamsayısı vardır. Buradan yola çıkarsak $$P(N)=p^r.u+p^M.t$$ olacak şekilde bir $t$ tam sayısı bulunduğunu söyleyebiliriz. $r<M$ olduğundan dolayı $P(N)=p^r(u+p^{M-r}t)$ olarak yazılaiblir ve $p\not \mid u+p^{M-r}$ olduğundan dolayı $v_p(P(N))=r$ elde edilir.
Şimdi $a=p^ec$ ,$p \not \mid c$ ve $v_p(a)=e$ olacak şekilde $e,c$ , $M>e$ tam sayıları seçelim. $L$ bir tamsayı olmak üzere
$$x^2+y^2\equiv c \pmod p$$ olacak şekilde $x,y$ tam sayıları vardır. Bunu ispatlayalım. $A$ ve $B$ kümeler olmak üzere $\mid A \mid$ ve $\mid B \mid $ bu kümelerdeki eleman sayıları olsun. Şimdi karekalanlarla alakalı bazı özdeşlikler bulalım $x^2\equiv y^2 \pmod p$ sağlanabilmesi için
$$x^2-y^2\equiv 0 \pmod p$$ yani $$(x-y)(x+y)\equiv 0 \pmod p$$ olur. Buradan ya $x$ $y$ birbirine denk ya da $x$ ile $-y$ birbirine denk olması gerektiği görülür. Buradan yola çıkarsak $0$ dan $\frac{p-1}{2}$ ye kadar olan kalanlara bakmamız yeterlidir ve az önce yaptığımız ispat nedeniyle bu kalanların tamamı birbirinden farklı olmalıdır. Yani herhangi bir $2$ hariç $\pmod p$ altında $\frac{p+1}{2}$ adet kare kalan (x^2) oluştuğunu görürüz. Benzer şekilde $c-y^2$ için de $\frac{p+1}{2}$ karekalan oluşur. $| A|+ | B |= p+1$ olduğundan güvercin yuvası ilkesi gereğince bu iki kümenin en az $1$ ortak elemanı vardır. Varsayalım ki bu eleman $u$ olsun. Bu durumda $$u\equiv x^2 \pmod p$$ ve $$u\equiv c-y^2 \pmod p$$ yani $$x^2+y^2\equiv c \pmod p$$ elde ederiz. En baştaki $p \not \mid c $ kabulümüzden dolayı hensel liftingi sürekli uygulayabiliriz ve keyfi bir $L$ pozitif tam sayısı için $$x^2+y^2 \equiv c \pmod{p^L}$$ olacak şekilde $x,y$ tamsayılarının var olduğunu söyleyebiliriz.
$U=x^2+y^2$ ve $U \equiv c \pmod{p^{M-e}}$ olsun. Polinomda kullandığımız $a$ ya uygun $N$ seçmek için $N=p^e.U$ alalım. $N=p^eU\equiv p^ec=a \pmod{p^M}$ olur dolayısıyla bu $N$ seçimini yapabiliriz. Eğer $e$ çiftse $N\in S$ sağlanır. Eğer $e$ tekse $N\in S$ sağlanmaz.
$$v_p(P(a))\equiv v_p(a) \pmod 2$$ sağlanır.
i) $v_p(a)$ çift olsun. Çelişki yardımıyla ispatlamak için varsayalım ki $v_p(P(a))=r$ tek olsun. Ve $N\equiv a \pmod{p^{M}}$ , $N\in S$ olacak şekilde $N$ seçelim. $P(N)\equiv P(a) \pmod{p^{M}}$ ve buradan $v_p(P(N))=r$ elde edilir. Ancak $r$ tek kabul ettiğimiz için çelişki elde edilir.
ii) $v_p(a)$ tek olsun. Çelişki yardımıyla ispatlamak için varsayalım ki $v_p(P(a))=r$ çift olsun. $N$ tamsayısını $N \equiv a \pmod{ p^M}$ olacak şekilde ve $p$ nin üssü tek seçelim ve diğer $3\pmod4$ asallarının üstü çift olsun. (Bu seçimin yapılabileceğini $N=p^eU$ ile göstermiştik.) ($N\not \in S$) . Soruda verilen önermeden dolayı $P(N)\not \in S$ olmalıdır. Ancak $P(N)\equiv P(a) \pmod{ p^M}$ ve $M>r$ olduğu için $v_p(P(N))$ çift olmalıdır. Diğer $3\pmod 4$ asalları için de bu durum uygulanabileceği için $p(N)\in S$ olmasına neden olur. Çelişki.
Şimdi $P(0)=0$ olduğunu gösterelim. Varsayalım ki $P(0)\not = 0$ olsun. Bu durumda sorunun şartından $0\in S$ olduğundan $P(0) \in S$ olması gerektiği söylenebilir ve $v_3(P(0))$ çift olmalıdır $M>v_3(P(0))$ olacak şekilde seçelim. $k$ bir tamsayı, $2k+1\geq M$ olmak üzere $n=3^{2k+1}$ alalım. $v_3(n)$ tek olduğu için $v_3(P(n))$ de tektir. Ancak $3^{2k+1}\equiv 0 \pmod{3^M}$ ve $$P(3^{2k+1}) \equiv P(0) \pmod{3^M}$$ Buradan $v_3(P(3^{2k+1}))=v_3(P(0))$ elde edilir ve bu $P(0)\in S $ olmasıyla çelişir (sol tarafın paritesi tek iken sağ tarafın paritesi çift). $P(0)=0$ olmalıdır.
$P(x)=x^mR(x)$ , $m>0$ denklemin $0$ olan kökünün katı, $R(x) \not = 0$ olacak şekilde seçebiliriz. Şimdi $p\equiv 3 \pmod 4$ ve $p\not \mid R(0)$ olacak şekilde bir $p$ asalı seçelim. $n=p^{2k+1}$ alalım. $$R(p^{2k+1})\equiv R(0) \pmod p$$ ve $p \not \mid R(0)$ olduğundan $p \not \mid R(p^{2k+1})$ olur. $$P(p^{2k+1})=p^{m(2k+1)}R(p^{2k+1})$$ $n$ in üssü tek olduğu için $m$ tek olmalıdır.
Geriye $R(n)$ nin iki kare toplamı olarak yazılabileceğini göstermek kaldı. $P(n)=n^mR(n)$ $n>0$ ve $R(n)\not = 0$ olsun. Her $p\equiv 3 \pmod 4$ asalı için $$v_p(P(n))=m.v_p(n)+v_p(R(n))$$. Parite korunumundan $$v_p(P(n))\equiv v_p(n)\pmod 2$$ , $m$ tek olduğu için ve yukarıdaki eşitlik yardımıya $v_p(R(n)) \equiv 0 \pmod 2$ elde edilir. Bu da bize $\mid R(n) \mid \in S$ sonucunu verir. Geriye $\mid R(0) \mid \in S$ olduğunu göstermek kaldı.
$p\equiv 3 \pmod 4$ asal olsun. $p^{2k}\in S$ olduğundan $P(p^{2k})\in S $ $P(p^{2k})=p^{2km}R(p^{2k})$ olur ve bu da bize $v_p(R(p^{2k}))$ çift olduğunu verir.
$p^{2k} \equiv 0 \pmod{ p^{2k}}$ olduğundan dolayı $R(p^{2k}) \equiv R(0) \pmod{ p^{2k}}$ buradan $v_p(R(p^{2k}))=v_p(R(0))$ olması için $2k>v_p(R(0))$ olacak şekilde kısıtlama eklemeliyiz. Bu da bize $v_p(R(0))$ ın çift olduğunu verir.
$R(n)$ in negatif olamayacağını ispatlayalım.
Varsayalım ki bir $a\geq 0$ için $R(a)<0$ olsun. $R(a)=-B$ ve $B>0$ olacak şekilde $B$ tam sayısını seçelim. Az önce elde ettiğimiz $\mid R(n)\mid \in S$ sonucundan dolayı $B\in S$ olur.
$R$ polinomunun başkatsayısı pozitiftir. Bu yüzden uygun bir $t$ tam sayısı seçilerek
$$
N=a+4Bt
$$
ve aynı zamanda $R(N)>0$ olması sağlanabilir. Bu seçimden dolayı $N\equiv a \pmod{4B}$ olur. Polinom tam katsayılı olduğundan
$$
R(N)\equiv R(a)\equiv -B \pmod{4B}
$$
elde edilir. Buradan bir $u$ tam sayısı için $R(N)=B(4u-1)$ yazılabilir.
Öte yandan $R(N)>0$ ve $\mid R(N)\mid \in S$ olduğundan $R(N)\in S$ olur. Ayrıca $B\in S$ ve $B\mid R(N)$ olduğu için iki kare toplamı teoreminden bölümün de $S$ içinde olması gerekir. Yani $4u-1\in S$ olmalıdır. Ancak
$$
4u-1\equiv 3 \pmod 4
$$
olduğundan bu mümkün değildir. Çünkü iki karenin toplamı mod $4$ altında $3$ olamaz. Çelişki elde edilir. Dolayısıyla $R(n)$ negatif değer alamaz. Böylece
$$
R(n)\in S \qquad \forall n\geq 0
$$
elde edilir.
Şimdi son olarak şu lemmayı kullanalım. Eğer $F\in Z[X]$ ve her $n\geq 0 $ için $F(n) \in S$ ise $\deg F$ çift olmalıdır.
Bunu ispatlayalım. Varsayalım ki $\deg F$ tek olsun. Büyük pozitif $n$ değerleri için $F(n)\in S$ olduğundan $F(n)\geq 0$ olmalıdır. Bu yüzden $F$ nin başkatsayısı pozitiftir. Derece tek ve başkatsayı pozitif olduğundan negatif tarafta $F$ negatif değer alır. Yani negatif bir tam sayı $a$ için $F(a)<0$ seçilebilir. $F(a)=-B$ ve $B>0$ olsun.
Önce $B\in S$ olduğunu gösterelim. Eğer $B\notin S$ olsaydı, bir $p\equiv 3 \pmod 4$ asalı için $v_p(B)$ tek olurdu. $M>v_p(B)$ seçip $N\equiv a \pmod{p^M}$ ve $N\geq 0$ olacak şekilde $N$ seçelim. Bu durumda $F(N)\equiv F(a)\pmod{p^M}$ olur ve $v_p(F(N))=v_p(F(a))$ tek kalır. Bu da $F(N)\notin S$ demektir. Ancak $N\geq 0$ olduğundan varsayımdan $F(N)\in S$ olmalıydı. Çelişki. Demek ki $B\in S$.
Şimdi uygun bir $t$ seçerek
$$
N=a+4Bt\geq 0
$$
ve $F(N)>0$ olmasını sağlayalım. Bu durumda
$$
F(N)\equiv F(a)\equiv -B \pmod{4B}
$$
olur. Dolayısıyla bir $u$ tam sayısı için $F(N)=B(4u-1)$ yazılır. Burada $F(N)\in S$ ve $B\in S$ olduğundan yine iki kare toplamı teoreminden $4u-1\in S$ olmalıdır. Fakat $4u-1\equiv 3\pmod4$ olduğundan bu imkansızdır. Çelişki.
Demek ki $\deg F$ tek olamaz. Dolayısıyla $\deg F$ çifttir.
Bu lemmayı $F=R$ için uygularsak $\deg R$ çift olur. Daha önce $P(x)=x^mR(x)$ ve $m$ nin tek olduğunu göstermiştik. Sonuç olarak
$$
\deg P=m+\deg R
$$
tek $+$ çift olduğundan tektir.
