Podzielność - zagwozdka

[Elayne]

Określ wszystkie pary dodatnich liczb całkowitych \(\displaystyle{ (m, n)}\), takich, że \(\displaystyle{ (1 + x^n + x^{2n} + \ldots + x^{mn})}\) jest podzielne przez \(\displaystyle{ (1 + x + x^2 + \ldots + x^m).}\)

[arek1357]

po zwinięciu mamy:

\(\displaystyle{ x^{nm+n+1}-x^{nm+n}-x+1=w(x)\left( x^{n+m+1}-x^{m+1}-x^n+1\right)}\)

niech:

\(\displaystyle{ w(x)=p(x)+ax+b}\)

\(\displaystyle{ A(x)= x^{nm+n+1}-x^{nm+n}-x+1}\)

\(\displaystyle{ B(x)=x^{n+m+1}-x^{m+1}-x^n+1}\)


\(\displaystyle{ w'(x)=p'(x)+a}\)

\(\displaystyle{ w''(x)=p''(x)}\)

(*)\(\displaystyle{ A''(x)=w''(x)B(x)+2w'(x)B'(x)+w(x)B''(x)}\)


\(\displaystyle{ A'(x)=(nm+n+1)x^{nm+n}-(nm+n)x^{nm+n-1}-1}\)

\(\displaystyle{ A''(x)=(nm+n)(nm+n+1)x^{nm+n-1}-(nm+n-1)(nm+n)x^{nm+n-2}}\)


\(\displaystyle{ B'(x)=(n+m+1)x^{n+m}-(m+1)x^m-nx^{n-1}}\)

\(\displaystyle{ B''(x)=(n+m)(n+m+1)x^{n+m-1}-m(m+1)x^{m-1}-(n-1)nx^{n-2}}\)

musi być:

\(\displaystyle{ n>1}\)

Po wymnożeniu (*) mamy stronę lewą i prawą.

Interesują nas tylko jednomiany o najmniejszych potęgach...

więc zapisujemy jednomian o najmniejszej potędze ze strony lewej:

jest to jednomian:

\(\displaystyle{ dx^{nm+n-2}}\)

po stronie prawej mamy natomiast cały rząd jednomianów o potencjalnie najniższym stopniu:

\(\displaystyle{ p''(x)+c_{1}x^{m-2}+c_{2}x^{n-2}}\)

Może się zdarzyć, że:

1.\(\displaystyle{ m}\) jest najmniejsze

znaczy:

\(\displaystyle{ nm+n-2=m-2}\)

rozwiązanie:

\(\displaystyle{ (n,m)=(0,0)}\)

2.\(\displaystyle{ n}\) jest najmniejsze

znaczy:

\(\displaystyle{ nm+n-2=n-2}\)

rozwiązanie:

\(\displaystyle{ n=0 \vee m=0}\)

Może się jeszcze zdarzyć jak widać, że:

\(\displaystyle{ nm+n-2=0}\)

co daje nam rozwiązanie:

\(\displaystyle{ (n,m)=(1,1) \vee (2,0)}\)

Teraz trzeba sprawdzić dla których przypadków to ma sens...

\(\displaystyle{ (n,m)=(0,0)(0,m)(n,0)(1,1)}\)

Dwa pierwsze i ostatnie jak widać trzeba odrzucić i zostanie:

\(\displaystyle{ (n,m)=(n,0)}\)


I przypadek gdy:

\(\displaystyle{ n=1}\)

mamy \(\displaystyle{ m}\) dowolne

Czyli rozwiązanie:

\(\displaystyle{ (1,m)}\)

Czyżby \(\displaystyle{ 1+x^2=1+x}\)

jest to prawda tylko dla:

\(\displaystyle{ x=0 \vee 1}\)

[Slup]

Rozpatrzmy wielomiany

\(\displaystyle{ f(x) = 1+x+x^2+...+x^m,\,g(x) = 1+x^n+x^{2n}+...+x^{nm}}\)

Zauważmy, że

\(\displaystyle{ g(x) = \begin{cases}\frac{x^{n\cdot (m+1)}-1}{x^n-1}&\mbox{ dla }x^n\neq 1\\ n\cdot m+1& \mbox{ dla }x^n = 1\end{cases}}\)

Z racji, że \(\displaystyle{ f(x)}\) nie ma pierwiastków wielokrotnych i oba wielomiany mają najstarszy współczynnik równy 1, warunek \(\displaystyle{ f(x) | g(x)}\) zachodzi wtedy i tylko wtedy, gdy

\(\displaystyle{ \forall_{\xi \in\mathbb{C}}\, f(\xi)=0 \Rightarrow g(\xi) =0}\)

co jest równoważne na mocy powyższej (klamrowej) formuły na \(\displaystyle{ g(x)}\) ze zdaniem

\(\displaystyle{ \forall_{\xi \in\mathbb{C}}\, f(\xi)=0 \Rightarrow \xi^{n\cdot (m+1)}-1 = 0\mbox{ oraz }\xi^n-1\neq 0}\)

Zauważmy, że zachodzi implikacja

\(\displaystyle{ \forall_{\xi \in\mathbb{C}}\, f(\xi)=0 \Rightarrow \xi^{n\cdot (m+1)}-1 = 0}\)

Zatem warunek \(\displaystyle{ f(x) | g(x)}\) jest równoważny implikacji

\(\displaystyle{ \forall_{\xi \in\mathbb{C}}\, f(\xi)=0 \Rightarrow \xi^n \neq 1}\)

Jak wiadomo \(\displaystyle{ f(\xi) = 0}\) wtedy i tylko wtedy, gdy \(\displaystyle{ \xi = e^{i\cdot \frac{2k\pi}{m+1}}}\) dla \(\displaystyle{ k \in \{1, 2,...,m\}}\). Zauważmy, że dla takiego \(\displaystyle{ \xi}\) mamy

\(\displaystyle{ \xi^n = e^{i\cdot \frac{2k\cdot n\pi}{m+1}}}\)

i ta wielkość jest różna od \(\displaystyle{ 1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ m+1}\) nie jest dzielnikiem \(\displaystyle{ k\cdot n}\). Ostatecznie więc warunek \(\displaystyle{ f(x)|g(x)}\) jest równoważny temu, że \(\displaystyle{ m+1}\) nie dzieli \(\displaystyle{ k\cdot n}\) dla każdego \(\displaystyle{ k\in \{1,2,...,m\}}\). To ma miejsce wtedy i tylko wtedy, gdy \(\displaystyle{ m+1}\) i \(\displaystyle{ n}\) są względnie pierwsze..