Tübitak Lise 2. Aşama 2000 Soru 2

[geo]

Her $n$ pozitif tamsayısı için $$P_{n}(x)=x^{n-1}+x^{n-2}+x^{n-3}+\ldots +x+1$$ şeklinde tanımlanıyor. Her $a$ pozitif tamsayısı için, $$P_{n}(x)=(1+ax+x^{2}R(x)) Q(x)$$ olacak şekilde bir $n$ pozitif tam sayısı ile, katsayıları tam sayılar olan $R(x)$ ve $Q(x)$ polinomlarının bulunduğunu gösteriniz.

[geo]

$n$, ilk $k$ asal sayının çarpımı olsun.
$k=2$ için, $n=6$ dır.
$$P_6\left(x\right)\left(x-1\right)=x^6-1=\left(x-1\right)\underbrace{\left(x+1\right)\left(x^2+x+1\right)}_{x^2R\left(x\right)+2x+1}\cdot\underbrace{\left(x^2-x+1\right)}_{Q\left(x\right)}.$$
$a=2$ için $n=6$, $R\left(x\right)=x+2$ ve $Q\left(x\right)=x^2-x+1$ olarak bulunabiliyor.
Genel olarak $\left(\dots +x+1\right)$ şeklinde $a$ ifadeyi yan yana çarpasak, $ax$ li bir terim elde ederiz.
$k=3$ için, $n=2\cdot 3\cdot 5=30$.
$$P_{30}\left(x\right)\left(x-1\right)=x^{30}-1$$
polinomunun $x^2-1$, $x^6-1$, $x^{10}-1$ polinomları ayrı ayrı böler. Ama hep birlikte bölmez.
Benzer şekilde $x-1$, $x+1$, $x^3-1$, $x^3+1$, $x^5-1$, $x^5+1$ polinomları da $x^{30}-1$ i ayrı ayrı böler. Ama hep birlikte bölmez.
Bu durumda $x^2+x+1$ ile $x^4+x^3+x^2+x+1$ polinomları da $x^{30}-1$ i ayrı ayrı böler. Bu iki polinomun $\text{ebob}$ ları $1$ ise $x^{30}-1$ i ikisi birlikteyken böler. Yani $$\left(x^2+x+1\right)\left(x^4+x^3+x^2+x+1\right)|x^{30}-1$$ Bu iki polinomun aralarında asal olduğu $$x^4+x^3+x^2+x+1=x^2\left(x^2+x+1\right)+x^2+x+1-x^2=\left(x^2+x+1\right)\left(x+1\right)-x^2$$ şeklinde gösterilebilir. Bu durumda $$x^{30}-1=Q\left(x\right)\left(x-1\right)\underbrace{\left(x+1\right)\left(x^2+x+1\right)\left(x^4+x^3+x^2+x+1\right)}_{\dots +3x+1}$$ şeklinde $n$ sayısı ile $R\left(x\right)$ ve $Q\left(x\right)$ polinomları bulunabilir.

İddia:
$p>q$ asal sayıları için, $$\text{ebob}\left(x^p-1,x^q-1\right)=x-1$$
İspat:
$(p,q)=1$ olduğu için, Öklid algoritması uyguladığımızda $(x^p-1, x^q-1)=(x^{p \mod q}-1, x^q-1)=\ldots=(x^{r}-1, x^{\text{ebob}(p,q)}-1)=x-1$ olacaktır. $\blacksquare$

Soruya geri dönersek,
$k=a$ için, $n$ sayısı ilk $a$ asal sayının çarpımı olacak.
Her $p|n$ asal sayısı için $x^p-1|x^n-1$ olacağı aşikar. Bu durumda $1+x+\dots +x^{p-1}|x^n-1$.
Bu şekilde asal sayılardan $a$ tane olduğu için, en az $a$ tane $\left(1+x+\dots \right)$ şeklinde bölen vardır. Bu $a$ bölenin hepsinin ikişerli olarak aralarında asal olduğunu yukarıdaki iddiada gösterdik. Bu durumda bu $a$ bölenin hepsi birlikte çarpandır. Bu durumda $$x^n-1=\left(x-1\right)\underbrace{\ \dots \ }_{Q\left(x\right)}(1+ax+\underbrace{\ \dots \ }_{x^2R\left(x\right)})$$ elde edilir.


Not:
$n$ asalken $P(x) = x^{n-1} + x^{n-2} + \dots + x + 1$ polinomlarının indirgenemez olduğunu Eisenstein Kriteri ile de gösterebiliriz.

[geo]

$n,m\geq 2$ ve $(n,m)=1$ olsun.

$\begin{array}{lcl}
P_{nm}(x) &=& x^{nm - 1} + \dots + x + 1 \\
&=& \dfrac {x^{nm} - 1}{x-1} \\
&=& \dfrac {x^n - 1}{x-1}\cdot (1+x^n + x^{2n} + \dots + x^{(m-1)\cdot n}) \\
&=& P_n(x) \cdot P_{m}(x^n)
\end{array}$

İddia: $P_{m}(x) \mid P_{m}(x^n)$

İspat: $P_{m}(x^n)(x-1) = (x^{m} - 1)S(x) + 0$ olduğunu göstermemiz isteniyor.
$(1+x^n + \dots + x^{(m-1)n})(x-1) = (x + x^{n+1} + x^{2n+1} + \dots + x^{(m-1)\cdot n + 1}) - (1 + x^n + x^{2n} + \dots + x^{(m-1)n})$.
$P_{m}(x^n)(x-1)$ sayısının $x^{m}-1$ ile bölümünden kalanı bulmak için $x^{m}=1$ yazacağız.
$(n,m)=1$ olduğu için $0\cdot n, 1\cdot n, \dots, (m-1)\cdot n$ sayıları $\bmod {(m)}$ de tam kalan sistemi oluşturur. Yani, $0$ dan $(m-1)$ e tüm kalanları alır. (İspatı: $xn\equiv yn \pmod {m} \Longrightarrow (x-y)n\equiv 0 \pmod {m} \Longrightarrow x\equiv y \pmod {m}$)
Dolayısıyla bunların $1$ fazlaları da, $1+ 0\cdot n, 1+ 1\cdot n, \dots, 1+ (m-1)\cdot n$ sayıları da, $\bmod {(m)}$ de tam kalan sistemi oluşturur.
O halde $P_{m}(x^n)(x-1)$ polinomu $x^{m}-1$ ile kalansız bölünür.$\blacksquare$

İddianın sonucu olarak da $P_{nm}(x) = P_n(x) \cdot P_{m}(x^n) = P_n(x) \cdot P_{m}(x) Q(x)$ elde edilir.

Şimdi de sorunun çözümü için tümevarım uygulayalım.
$a=1$ için $n\geq 2$, $R(x)=1+x+\ldots + x^{n-3}$ ($n=2$ için $R(x)=0$), $Q(x)=1$ bulunur.
$a$ için $n, Q(x), R(x)$ bulunduğunu varsayalım.

$(n,m)=1$ ve $m\geq 2$ olmak üzere;
$\begin{array}{lcl}
P_{nm} &=& P_n(x) \cdot P_{m}(x)Q'(x) \\
&=& (1+ax+x^2R(x))(1+x+\dots + x^{m-1})Q'(x) \\
&=& (1+(a+1)x+R'(x))Q'(x)\end{array}$
olacağı için $a+1$ için de $nm$ sayısı, $R'(x)$, $Q'(x)$ polinomları bulunur.

$n$; her biri $1$ den büyük ve aralarında asal $a$ sayının çarpımı şeklinde alınabilir.

Kaynak: Barış Koyuncu'nun AoPS deki çözümü biraz değiştirilerek buraya taşınmıştır.
O çözümde $m=n+1$ olarak alınmıştır. Doğal olarak $(n,m)=1$ şartı sağlandığı için, yukarıdaki çözümün bir örneğidir.