Dowód złożoności pewnej sumy - wariant II

[Majeskas]

Wykaż, że jeśli dla pewnych \(\displaystyle{ a, b, c, d\in\mathbb{N}_+}\) zachodzi \(\displaystyle{ ab=cd}\), to liczba \(\displaystyle{ a+b+c+d}\) jest złożona.

[norwimaj]

Spróbuj pokazać, że przy danych założeniach liczba \(\displaystyle{ a+b+c+d}\) dzieli się przez \(\displaystyle{ \gcd(a,c)+\gcd(b,d)}\). W razie problemów pytaj.

[virtue]

1. Jeśli \(\displaystyle{ a=c}\) i \(\displaystyle{ b=d}\) lub \(\displaystyle{ b=c}\) i \(\displaystyle{ a=d}\) to \(\displaystyle{ a+b+c+d=2(a+b)}\)
2.Jeśli nie są równe to \(\displaystyle{ a=mk}\) i \(\displaystyle{ b=pq}\) \(\displaystyle{ m, k, p, q\in\mathbb{N}_+}\) to \(\displaystyle{ a+b+c+d=(m+p)(p+q)}\)

[Majeskas]

Z założenia mamy:

\(\displaystyle{ t=a+b+c+d=\frac{cd}b+b+c+d}\)

\(\displaystyle{ tb=cd+b^2+cb+cd=(b+c)(b+d)}\)

Teraz dzieląc obie strony kolejno przez wszystkie czynniki pierwsze \(\displaystyle{ b}\) można sprowadzić tę równość do postaci

\(\displaystyle{ t=(b'+c')(b"+d')}\), gdzie \(\displaystyle{ b',c',b",d'\in\mathbb{N_+}}\), co oznacza, że istotnie, liczba \(\displaystyle{ t}\) jest złożona. Jednak uzyskany rozkład ma się chyba nijak do tej sumy największych wspólnych dzielników. Przypuszczam, że trzeba to podejść od jakiejś innej strony, żeby uzyskać taki wynik. Mógłbyś uchylić rąbka tajemnicy?-- 15 marca 2014, 15:57 --

1. Jeśli \(\displaystyle{ a=c}\) i \(\displaystyle{ b=d}\) lub \(\displaystyle{ b=c}\) i \(\displaystyle{ a=d}\) to \(\displaystyle{ a+b+c+d=2(a+b)}\)
2.Jeśli nie są równe to \(\displaystyle{ a=mk}\) i \(\displaystyle{ b=pq}\) \(\displaystyle{ m, k, p, q\in\mathbb{N}_+}\) to \(\displaystyle{ a+b+c+d=(m+p)(p+q)}\)

Kompletnie nie rozumiem, skąd taki rezultat w drugim kroku. Chyba trochę zbyt skrótowo. Nie wiem nawet, jak się mają te rozkłady \(\displaystyle{ a}\) i \(\displaystyle{ b}\) do liczb \(\displaystyle{ c}\) i \(\displaystyle{ d}\).

[norwimaj]

\(\displaystyle{ tb=cd+b^2+cb+cd=(b+c)(b+d)}\)

Teraz dzieląc obie strony kolejno przez wszystkie czynniki pierwsze \(\displaystyle{ b}\) można sprowadzić tę równość do postaci

\(\displaystyle{ t=(b'+c')(b"+d')}\), gdzie \(\displaystyle{ b',c',b",d'\in\mathbb{N_+}}\),

Tutaj by się przydało uzasadnienie, w jaki sposób dzielimy po prawej stronie i dlaczego możemy to zrobić tak, że \(\displaystyle{ b',c',b",d'\in\mathbb{N}_+}\).

Ja to robię tak:
\(\displaystyle{ a=\alpha\cdot\gcd(a,c)\\
c=\gamma\cdot\gcd(a,c)\\
b=\beta\cdot\gcd(b,d)\\
d=\delta\cdot\gcd(b,d).}\)

Z równości \(\displaystyle{ ab=cd}\) wynika, że \(\displaystyle{ \alpha\beta=\gamma\delta}\), a skoro pary: \(\displaystyle{ \alpha}\) i \(\displaystyle{ \gamma}\) oraz \(\displaystyle{ \beta}\) i \(\displaystyle{ \delta}\) są względnie pierwsze, to \(\displaystyle{ \alpha=\delta}\) i \(\displaystyle{ \beta=\gamma}\). Teraz wiemy, że

\(\displaystyle{ a+b+c+d=(\alpha+\gamma)\gcd(a,c)+(\beta+\delta)\gcd(b,d)=(\alpha+\gamma)(\gcd(a,c)+\gcd(b,d)).}\)

[Majeskas]

\(\displaystyle{ tb=cd+b^2+cb+cd=(b+c)(b+d)}\)

Teraz dzieląc obie strony kolejno przez wszystkie czynniki pierwsze \(\displaystyle{ b}\) można sprowadzić tę równość do postaci

\(\displaystyle{ t=(b'+c')(b"+d')}\), gdzie \(\displaystyle{ b',c',b",d'\in\mathbb{N_+}}\),

Tutaj by się przydało uzasadnienie, w jaki sposób dzielimy po prawej stronie i dlaczego możemy to zrobić tak, że \(\displaystyle{ b',c',b",d'\in\mathbb{N}_+}\).

Jasna sprawa. Nie uzasadniałem tego tutaj, bo to w końcu ja miałem problem z tym zadaniem, więc tylko skrótowo naszkicowałem rozwiązanie, które znalazłem.

a skoro pary: \(\displaystyle{ \alpha}\) i \(\displaystyle{ \gamma}\) oraz \(\displaystyle{ \beta}\) i \(\displaystyle{ \delta}\) są względnie pierwsze, to \(\displaystyle{ \alpha=\delta}\) i \(\displaystyle{ \beta=\gamma}\).

Tego prostego stwierdzenia mi zabrakło! Wobec niego zadanie robi się banalne. Dzięki!

[norwimaj]

Jeśli dodatkowo założymy, że \(\displaystyle{ \gcd(a,b,c,d)=1}\), czyli \(\displaystyle{ \gcd(\gcd(a,c),\gcd(b,d))=1}\), to z równości:

\(\displaystyle{ a=\alpha\cdot\gcd(a,c)}\) i \(\displaystyle{ d=\alpha\cdot\gcd(b,d)}\)

możemy wywnioskować, że \(\displaystyle{ \alpha=\gcd(a,d)}\). Analogicznie \(\displaystyle{ \beta=\gcd(b,c)}\). Wówczas

\(\displaystyle{ a+b+c+d = (\gcd(a,d)+\gcd(b,c))(\gcd(a,c)+\gcd(b,d)).}\)

W ogólnym przypadku

\(\displaystyle{ a+b+c+d = \frac{ (\gcd(a,d)+\gcd(b,c))(\gcd(a,c)+\gcd(b,d))}{\gcd(a,b,c,d)}.}\)


Jeśli chodzi o rozwiązanie Virtue, to jest ono bardzo słabo zapisane, ale domyślam się, jaki mógł być pomysł. Liczbę \(\displaystyle{ ab=cd}\) zapisujemy jako iloczyn liczb pierwszych (niekoniecznie różnych): \(\displaystyle{ ab=p_1\cdot p_2\cdot\ldots\cdot p_n}\). Możemy wybrać podzbiór indeksów \(\displaystyle{ X\subset \{1,\ldots,n\}}\) taki, że \(\displaystyle{ \prod_{i\in X}p_i=a}\). Wówczas \(\displaystyle{ \prod_{i\in X'}p_i=b}\). Analogicznie znajdujemy taki \(\displaystyle{ Y\subset \{1,\ldots,n\}}\), że \(\displaystyle{ \prod_{i\in Y}p_i=c}\) oraz \(\displaystyle{ \prod_{i\in Y'}p_i=d}\). Wtedy możemy zdefiniować \(\displaystyle{ m=\prod_{i\in X\cap Y}p_i}\), itd.