Bestimme den größten gemeinsamen Teiler aller Zahlen

((3m)!(3n)!(3p)!)/(m!n!p!(m+n)!(m+p)!(n+p)!)\.,

wobei m,n,p alle positiven ganzen Zahlen durchlaufen.

\
Es gilt, dass der Exponent t, sodass für eine Primzahl q die Potenz q^t genau n! teilt, d.h. q^t teilt n!, aber q^(t+1) ist kein Teiler mehr von n!, folgende Gleichung erfüllt:

t=\sum(\gauss(n/q^s),s=1,\inf)

Dabei sind in dieser Summe fast alle Summanden 0.

Setzt man dies an, so kann man die potenz von 3, die den Term der Aufgabenstellung teilt \(ich nenne diese Zahl mal t\) berechnen:

t=\sum(\gauss(3n/3^s),s=1,\inf)+\sum(\gauss(3m/3^s),s=1,\inf)+\sum(\gauss(3p/3^s),s=1,\inf)
 -(\sum(\gauss(n/3^s),s=1,\inf) + \sum(\gauss(m/3^s),s=1,\inf)+\sum(\gauss(p/3^s),s=1,\inf))
-(\sum(\gauss((n+m)/3^s),s=1,\inf)+\sum(\gauss((n+p)/3^s),s=1,\inf)+\sum(\gauss((m+p)/3^s),s=1,\inf))



Diese Summe kann man nun vereinfachen:
Da 3n/3^s=n/3^(s-1) ist, gilt \sum(\gauss(3n/3^s),s=1,\inf)-\sum(\gauss(n/3^s),s=1,\inf)=\sum(\gauss(n/3^s),s=0,\inf)-\sum(\gauss(n/3^s),s=1,\inf)=\gauss(n/3^0)=n.

Also ist die Summe der ersten 6 Summen gleich n+m+p, d.h.

t=m+n+p -(\sum(\gauss((n+m)/3^s),s=1,\inf)+\sum(\gauss((n+p)/3^s),s=1,\inf)+\sum(\gauss((m+p)/3^s),s=1,\inf)).

Nun ist gauss(x)<=x, d.h.

t>=m+n+p -( \sum((n+m)/3^s,s=1,\inf)+\sum((n+p)/3^s,s=1,\inf)+\sum((m+p)/3^s),s=1,\inf ) )

=m+n+p - \sum(((n+m)+(m+p)+(n+p))/3^s,s=1,\inf)

=m+n+p - 2*(m+n+p)*\sum(1/3^s,s=1,inf)

=(m+n+p) * (1-2*1/4) = (m+n+p)*1/2.

Da m,n,p jeweils größer oder gleich 1 sind, erhalten wir also t>=3/2. Da aber t notwendigerweise eine ganze Zahl ist, folgt also t>=2, und damit, dass der Term der Aufgabenstellung für jede Belegung m,n,p mit positiven ganzen Zahlen durch 3^2=9 teilbar ist, d.h. dies ist auch der gesuchte ggT.

Grüße,
Cyrix

sum(1/3^s,s=1,\inf)=1/2 und nicht 1/4

\
Da die Summe \sum(\gauss(x/3^s),s=1,\inf) endlich ist, und natürlich immernoch \gauss(x/3^s)<=x/3^s (für x>0) ist, ist die Summe \sum(\gauss(x/3^s),s=1,\inf)< \sum(x/3^s,s=1,\inf)=x/2.

Da die Summe eine ganze Zahl ist, ist also \sum(\gauss(x/3^s),s=1,\inf)<=\gauss((x-1)/2)<=x/2-1/2; wenn x eine positive natürliche Zahl ist.


Wendet man dies nun an, so erhält man die bessere Abschätzung

t=m+n+p -(\sum(\gauss((n+m)/3^s),s=1,\inf)+\sum(\gauss((n+p)/3^s),s=1,\inf)+\sum(\gauss((m+p)/3^s),s=1,\inf))

>= m+n+p - ((m+n)/2-1/2+(m+p)/2-1/2+(n+p)/2-1/2)=3/2.

Da t aber ganzzahlig sein muss, gilt also wieder t>=2.

( ((na_1))!\.((na_2))!...\.((na_n))! ) / ( (a_1)!\.(a_2)!...\.(a_n)! (a_1+a_2)!^((n-1)/2)\.(a_2+a_3)!^((n-1)/2)...\.(a_n+a_1)!^((n-1)/2) )

( ((na_1))!*((na_2))!*...*((na_n))! ) / ( (a_1)!*(a_2)!*...*(a_n)!*(a_1+a_2)!^(n-1)*(a_2+a_3)!^(n-1)*...*(a_n+a_1)!^(n-1) )

\
((n\.a_1)!*(n\.a_2)!* ... *(n\.a_n)!)/((a_1)!*(a_2)!* ... *(a_n)!*(a_1+a_2)!^(n-1)*(a_2+a_3)!^(n-1)* ... *(a_n+a_1)!^(n-1))

\
Hi, für den Exponenten e_3(r!) von 3 in der Primfaktorzerlegung von r! gilt auch

\stress\big\ e_3(r!)=(r-Q_3(r))/2

\(dabei ist Q_3(r) die Quersumme von r in der Darstellung zur Basis 3), was leicht aus

e_3(r*s)=e_3(r)+e_3(s)

und

e_3(k)=(Q_3(k-1)-Q_3(k)+1)/2

folgt \(und sich auch aus e_3(r!)=sum(floor(r/3^k),k=1,\inf) herleiten ließe):

e_3(r!)=e_3(prod(k,k=1,r))=sum(e_3(k),k=1,r)=sum((Q_3(k-1)-Q_3(k)+1)/2,k=1,r)=(r-Q_3(r))/2




Da im Dreiersystem 3*r aus r durch Anhängen einer 0 entsteht, gilt

Q_3(3r)=Q_3(r),

womit sich der \(analog zu Cyrix berechnete) Exponent

e_3(((3m)!(3n)!(3p)!)/(m!n!p!(m+n)!(n+p)!(p+m)!))=

(3m-Q_3(3m))/2+ ... -(m-Q_3(m))/2- ... -(m+n-Q_3(m+n))/2- ...

von 3 ganz elementar sofort zu

(Q_3(m+n)+Q_3(n+p)+Q_3(p+m))/2

vereinfacht. Weil m, n und p positive ganze Zahlen sind, gilt dasselbe für jede der drei Quersummen, was wieder zeigt, daß der Exponent von 3 nicht kleiner als 3\/2, also mindestens gleich 2 ist. Da der gesuchte ggT \(wie einfache Beispiele zeigen) 3^2 teilt, ist er gleich 9.


Darüberhinaus erkennt man daraus sofort, daß der Exponent von 3 genau dann \(nur) gleich 2 ist, wenn zwei der drei Summen m+n, n+p, p+m Dreierpotenzen sind und die dritte eine Summe von zwei Dreierpotenzen, was gleichwertig damit ist, daß sich 2m, 2n und 2p als

+3^a+3^b+3^c-3^d
+3^a+3^b-3^c+3^d
-3^a-3^b+3^c+3^d

darstellen lassen. Aber das gehört nicht mehr zur Lösung der Aufgabe.



Liebe Grüße, Franz

\
Hallo Darij!

Mit Deiner Verallgemeinerung aus dem Beitrag No. 9 stimmt etwas nicht, sie liefert i.A. nicht einmal ganzzahlige Werte.

Z.B. ergibt sich schon für n=3 und a_1=a_2=a_3=1:

3!^3/2!^(2*3)=(3/2)^3

Es reicht auch nicht, die Exponenten n\-1 durch n\-2 zu ersetzen,
wie n=7 \(wieder mit a_k=1) zeigt:

7!^7/2!^(5*7)=(315/2)^7


Liebe Grüße, Franz

Für eine Primzahl q ist der höchste Exponent h, für den n! durch q^h teilbar ist, bekanntlich gleich sum(gauss(n/q^k),k=1,\inf), damit ergibt sich für B(m,n,p) der Exponent sum((gauss(3m/q^k)+gauss(3n/q^k)+gauss(3p/q^k)-gauss(m/q^k)-gauss(n/q^k)-gauss(p/q^k)-gauss((m+n)/q^k)-gauss((m+p)/q^k)-gauss((n+p)/q^k)),k=1,\inf).
Man kann die Zahlen m/q^k=u+r, n/q^k=v+s, p/q^k=w+t in ganzen und gebrochenen Anteil zerlegen, dann ist der Ausdruck in Klammern gleich gauss(3r)+gauss(3s)+gauss(3t)-gauss(r+s)-gauss(r+t)-gauss(s+t).
Man darf 0<=r<=s<=t<1 annehmen und unterscheidet dann einige Fälle, je nachdem, ob r, s und t im Intervall [0\,1/3\.), [\.1/3\,2/3\.) oder [\.2/3\,1) liegen. Der Ausdruck ist in allen Fällen >=0, und somit ist B(m,n,p) ganzzahlig.