Teilbarkeit

20.07.2010, 13:08

iluminati

Teilbarkeit

Meien Aufgabe:
Beweise, dass es zu jeder positiven ganzen Zahl n eine Zahl der Gestalt

111...100...0

gibt, dich durch n teilbar ist.

Meine Vorschläge:
1. Für die Primzahlen beweisen, da jede natürliche Zahl ein Produkt dieser ist.
2. Für alle Teilbarkeitsregeln beweisen - die dümmste Variante
3. Beweisen, dass

$\begin{eqnarray*} \frac{10^{x+y+1} - 10^{y}}{9n} \in \mathbb N \end{eqnarray*}$

gilt.

Ich bedanke mich schon im voraus auf gute Tipps.

MFG

20.07.2010, 13:32

Mystic

Auf diesen Beitrag antworten »

RE: Teilbarkeit

Zitat:

Original von iluminati
Meien Aufgabe:
Beweise, dass es zu jeder positiven ganzen Zahl n eine Zahl der Gestalt

111...100...0

gibt, dich durch n teilbar ist.

Meine Vorschläge:
1. Für die Primzahlen beweisen, da jede natürliche Zahl ein Produkt dieser ist.

Falsch, denn nur quadratfreie Zahlen (also grob geschätzt ca. 61% aller natürlichen Zahlen) sind das Produkt von verschiedenen Primzahlen, und das ist die Voraussetzung, die du hier brauchen würdest (mal ganz abgesehen davon, dass für sie ja auch die Parameter x und y in Punkt 3 unten gleich sein müssten, was i.a. ja nicht der Fall ist!)...

Zitat:

Original von iluminati
2. Für alle Teilbarkeitsregeln beweisen - die dümmste Variante

Ja, ist wirklich sehr dumm, sodass ich nicht einmal verstehe, was du damit meinst... Noch dümmer finde aber ich persönlich deinen nächsten Vorschlag, nämlich

Zitat:

Original von iluminati
3. Beweisen, dass

$\begin{eqnarray*} \frac{10^{x+y+1} - 10^{y}}{9n} \in \mathbb N \end{eqnarray*}$

gilt.

Ich brauch ja hier nur das n im Nenner größer als den Zähler zu wählen, und schon stimmt's nicht nicht mehr, also irgendwas hast du da gewaltig verwechselt (vielleicht Allquantoren mit Existenzquantoren? verwirrt

)

Und, ach ja, Tipps wolltest du ja auch noch haben... Ich würde sagen, fang für den Anfang mal an mit dem Satz von Euler-Fermat

$\begin{eqnarray*} 10^{\varphi(n)} \equiv 1 \mod n \end{eqnarray*}$

für alle natürlichen Zahlen n, welche zu 10 teilerfremd sind...

Edit: Sehe gerade, dass dies unter "Schulmathematik" läuft und du angeblich erst 13 bist... So gesehen würde ich vielleicht manches milder formulieren...

20.07.2010, 15:28

Auf diesen Beitrag antworten »

Sofern Fermat bzw. Euler-Fermat nicht bekannt sind, bietet vielleicht das Schubfachprinzip eine (nicht notwendig bessere Augenzwinkern

) alternative Herangehensweise:

Ich üb mal wieder für die Olympiade

Allerdings bietet dieser Weg nur sehr dürftige Informationen über die genaue Anzahl an nötigen Einsen und Nullen.

21.07.2010, 10:33

iluminati

Auf diesen Beitrag antworten »

Danke euch beiden.

Ich bin zwar erst 13, dennoch bin ich ja nicht so dumm. Meine Frage nun an Mystic:

Meinst du mit deinem Modulogestell die eulersche Phi-Funktion?

also: phi(n)=(x-1)*(y-1)

Oder bin ich nicht so weit. Wenn du mir erklären könntest was das sein solle und vielleicht Links dazu geben könntest (oder Stichwort für die Google-Suche) dann würde ich dir sehr dankbar sein.

Aber ich kann auch gut und gerne die Version von Arthur Dent benutzen (Nochmals Danke).

MFG

21.07.2010, 11:13

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
Meinst du mit deinem Modulogestell die eulersche Phi-Funktion?

also: phi(n)=(x-1)*(y-1)

Ja und nein, ich meinte die eulersche Phi-Funktion, das ist schon richtig, aber deine Formel würde jetzt nur stimmen, wenn n das Produkt der beiden verschiedenen Primzahlen x und y wäre...Die wirkliche Formel - welche du allerdings gar nicht wirklich brauchst für deine Aufgabe, da genügt die Definition - kannst du leicht ergooglen... Womit wir bei anderen Sache wären, nämlich

Zitat:

Original von iluminati
Oder bin ich nicht so weit. Wenn du mir erklären könntest was das sein solle und vielleicht Links dazu geben könntest (oder Stichwort für die Google-Suche) dann würde ich dir sehr dankbar sein.

Ich habe dein eigenes Stichwort, nämlich eulersche phi-Funktion in Google eingeben, was du ja auch selbst hättest machen können, und bereits der erste Treffer war der aufschlußreiche Link oben...

21.07.2010, 11:51

iluminati

Auf diesen Beitrag antworten »

Stimmt, könnte ich eigentlich selber nachsuchen.
Bis jetzt habe ich alles verstanden was dort steht bei WIKIPEDIA, jedoch kriege ich keine Lampe über den Kopf, wie und warum ich das bei meinem Problem anwenden kann.

21.07.2010, 15:20

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
Bis jetzt habe ich alles verstanden was dort steht bei WIKIPEDIA, jedoch kriege ich keine Lampe über den Kopf, wie und warum ich das bei meinem Problem anwenden kann.

Hm, wenn diu sowas siehst wie

$\begin{eqnarray*} n | \underbrace{11\ldots1}_{\varphi(n)-mal} \cdot \ 9 \end{eqnarray*}$

wobei | "ist Teiler von" bedeutet und n hier noch nicht durch 2 oder 5 teilbar sein darf, und das dann mit deiner Aufgabe vergleichst, dann klingen noch nicht alle Glocken bei dir? verwirrt

21.07.2010, 15:49

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
Ich bin zwar erst 13, dennoch bin ich ja nicht so dumm.

Also ich gebe freimütig zu, dass ich mit 13 noch so "dumm" war, weder die Eulersche Phi-Funktion noch Euler-Fermat zu kennen. Ist schon eine Weile her, aber ich schätze mal, dass ich das erst so mit ca. 16 kennengelernt habe.

Von einer auch nur irgendwie angenommenen "Dummheit" kann bei meinem Einwurf oben also keine Rede sein. Augenzwinkern

Entschuldigt die Störung, das war alles, was ich klarstellen wollte. Wink

21.07.2010, 20:27

iluminati

Auf diesen Beitrag antworten »

@Arthur Dent:
Ja ich habe es auch nicht so gemeint.

@Mystic:
Und wo ist die Erklärung? Schließlich ist das Ergebnis 999...99 und nicht 111...1000..00

Allgemeine Frage an alle:
Ich weiß es ist vielleicht trivial aber dennoch:
Habt ihr mit euren Methoden auch wirklich ein klares Ergebins (in diesem Fall ein Beweis) bekommen?

Könnt ihr nicht eure Methoden detailierter erklären, ich bin ja ein Neueinsteiger in Kombinatorik und Funktionen.

Ich will aber nicht gegen das Mathe-online-Prinzip verstoßen, keine komplette Lösung.

21.07.2010, 23:18

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
@Mystic:
Und wo ist die Erklärung? Schließlich ist das Ergebnis 999...99 und nicht 111...1000..00

Man muss da eine kleine Fallunterscheidung machen, wo ich dachte, du könntest wenigstens ein paar Ideen dazu beisteuen, was aber offensichtlich nicht der Fall ist...

Also folgendes:

Sei n zunächst mal nicht durch 2 oder 5 teilbar, und sei weiter $\begin{eqnarray*} m=\min\{2,\nu_3(n)\} \end{eqnarray*}$ , wobei $\begin{eqnarray*} \nu_3(n) \end{eqnarray*}$ die Vielfachheit von 3 in der Primfaktorzerlegung von n ist. Es gilt dann

$\begin{eqnarray*} 3^m n | \underbrace{111\ldots1}_{\varphi(3^m \cdot n)-mal} \cdot \ 9 \Rightarrow n | \underbrace{111\ldots1}_{\varphi(3^m \cdot n)-mal} \cdot 3^{2-m} \Rightarrow n | \underbrace{111\ldots1}_{\varphi(3^m \cdot n)-mal} \end{eqnarray*}$

Ist aber nun n nicht zu 10 teilerfremd, so muss man obiges Argument zuerst auf

$\begin{eqnarray*} \tilde n :=\frac n {2^{\nu_2(n)}5^{\nu_5(n)}} \end{eqnarray*}$

anwenden, und dann anschließend die Beziehung

$\begin{eqnarray*} \tilde n | 111\ldots 1 \end{eqnarray*}$

mit

$\begin{eqnarray*} 10^{\max\{\nu_2(n),\nu_5(n)\}} \end{eqnarray*}$

multplizieren, woraus dann n |111...100...0 (mit geeignet vielen Einsen und Nullen) folgt...

Ich weiß, keine leichte Kost für einen 13-jährigen, aber wenn du willst, kannst du versuchen, das mal anhand von Beispielen nachzuvollziehen und ich kann dir dabei helfen... Augenzwinkern

23.07.2010, 11:53

iluminati

Auf diesen Beitrag antworten »

So, alles klar soweit, außer:
Dieses minimum {2,...} verstehe ich nicht.
Warum brauchst du das? Warum die 2? Was ist wenn n eine Primzahl ist? dann ist doch die Vielfachheit von den 3er-Primfaktoren gleich 0. Was hat es mit dem Zentralwert von n auf sich? Wenn n= 17, was meinst du dann mit Zentralwert von 17, ist doch dann 17, oder?

Ich versuche es also nun mit 7 als Beispiel nachzufolziehen:
Schritt 1: n soll nicht durch 2 oder/und 5 teilbar sein, ist es nicht => geschafft.
Schritt 2: m = min{2,0}, da 7 keine 3er-Primfkt. besitzt. => geschafft.
Schritt3: Jetzt kommen meine Probleme:
Was soll ich jetzt mit 3^m * 7 anfangen? Allgemeine Frage: Wie soll ich mit einer minimum-Ordnung umgehen?

23.07.2010, 13:56

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
So, alles klar soweit, außer:
Dieses minimum {2,...} verstehe ich nicht.
Warum brauchst du das? Warum die 2?

Im Primzip brauche ich das, weil der Schluß

$\begin{eqnarray*} n | 111\ldots 1 \cdot 9 \Rightarrow n | 111...1 \end{eqnarray*}$

nur zulässig ist, wenn n nicht durch 3 teilbar ist... Wenn n durch 3 (oder sogar durch 9) teilbar ist, hat man da ein Problem, das man irgendwie handlen muss, am besten so, wie ich das im vorigen Posting gemacht habe...

Zitat:

Original von iluminati
Was ist wenn n eine Primzahl ist? dann ist doch die Vielfachheit von den 3er-Primfaktoren gleich 0.

Falsch, für n=3 ist diese Vielfachheit 1 und nicht 0...Ansonsten ist der Fall, wo n eine Primzahl >5 ist, der einfachste überhaupt, denn in diesem Fall hat man ja ohne weitere Umstände $\begin{eqnarray*} n | \underbrace{111\ldots 1}_{\varphi(n)-mal} \end{eqnarray*}$ ...

Zitat:

Original von iluminati
Was hat es mit dem Zentralwert von n auf sich? Wenn n= 17, was meinst du dann mit Zentralwert von 17, ist doch dann 17, oder?

Wo habe ich da irgendwo von einem "Zentralwert" gesprochen? Kenne diesen Begriff gar nicht... verwirrt

Könntest du diese Stelle mal hier reinkopieren?

Zitat:

Original von iluminati
Ich versuche es also nun mit 7 als Beispiel nachzufolziehen:
Schritt 1: n soll nicht durch 2 oder/und 5 teilbar sein, ist es nicht => geschafft.
Schritt 2: m = min{2,0}, da 7 keine 3er-Primfkt. besitzt. => geschafft.
Schritt3: Jetzt kommen meine Probleme:
Was soll ich jetzt mit 3^m * 7 anfangen? Allgemeine Frage: Wie soll ich mit einer minimum-Ordnung umgehen?

Deine ganzen Probleme rühren hier daher, dass du m=min{2,0} nicht ausgerechnet hast... Warum nicht? verwirrt

Du musst also nur einfach das Minimum von 2 und 0 bilden - ich hoffe du schaffst das, trotz deines zarten Alters Big Laugh

- und den so erhalten Wert für m einsetzen... Weiter geht's dann so, wie ich das oben für den Fall, dass n eine Primzahl > 5 ist, schon ausgeführt habe...

23.07.2010, 16:39

iluminati

Auf diesen Beitrag antworten »

Ja, stimmt. Den Minimum rechnet man doch so aus:

$\begin{eqnarray*} min(x,y)= \frac{x+y-|x-y|}{2} \end{eqnarray*}$

okay.. habe jetzt alles verstanden.

Jetzt noch ein Beispiel: n=15
Dann gilt: m = min(2,1) = 2+1-1/2 = 1
3^1 * 15 = 45
die Phi-Funktion von 45 ist 18. ->
45|111111111111111111 * 9 -> 45|11..11 * 3^-1

soo ist das denn zulässig oder habe ich was falsch gemacht?
denn 3^-1 ist 1/3 oder?

Desweiteren möchte ich auch verstehen was ich mache. Wie kommst du zum Beispiel auf die Idee das minimum anzuwenden?

23.07.2010, 17:27

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
Den Minimum rechnet man doch so aus:

$\begin{eqnarray*} min(x,y)= \frac{x+y-|x-y|}{2} \end{eqnarray*}$

Zweifelsohne ist diese Formel richtig - aber ob man das bei zwei konkret vorliegenden Zahlen x,y so ausrechnet, kommt sicher drauf an, wer "man" ist. Mir wäre das jedenfalls zu aufwändig. Big Laugh

Zu deinem Beispiel n=15:

15 ist durch 5 teilbar, und was die Primfaktoren 2 und 5 betrifft, liegen die Dinge ja ein wenig anders (s.o.).

24.07.2010, 00:04

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von iluminati
[quote]Original von iluminati
okay.. habe jetzt alles verstanden.

Leider nein, dein n=15 ist ja durch 5 teilbar, du musst also zuerst mit

$\begin{eqnarray*} \tilde n :=\frac {15}5 \end{eqnarray*}$

arbeiten, dh., Potenzen von 2 oder 5, welche in n enthalten sind, müssen vorher aus n herausdividiert werden... Das hast du ganz offensichtlich überlesen oder nicht verstanden... Indem du also zunächst mit $\begin{eqnarray*} \tilde n =3 \end{eqnarray*}$ arbeitest, erhältst du wegen $\begin{eqnarray*} \varphi(3 \cdot 3) =3^2-3=6 \end{eqnarray*}$ , dass

$\begin{eqnarray*} 3 \cdot 3 | 111111 \cdot 9 \Rightarrow 1 | 111111 \end{eqnarray*}$

sicherlich nichts umwerfend Neues, aber es stimmt... Nun gilt aber auch

$\begin{eqnarray*} 3 | 111111 \end{eqnarray*}$

wegen der Teilbarkeitsregeln durch 3, und daher insgesamt

$\begin{eqnarray*} kgV(1,3)=3 | 111111 \end{eqnarray*}$

Dieser Weg mag dir etwas absonderlich und umständlich scheinen, aber im allgmeinen Fall, der nicht mehr so einfach ist wie hier, musst du genau so vorgehen...

Okay, als letztes müssen wir das mit der Potenz von 5, welche wir aus n herausdividiert hatten, wieder in Ordnung bringen und dies geschieht, indem wir mit der genau gleichen Potenz von 10 multiplizieren (s.o.), also

$\begin{eqnarray*} 3 | 111111 \Rightarrow 30 | 1111110 \Rightarrow 15 | 1111110 \end{eqnarray*}$

Wie man sieht, haben wir eine Darstellung der behaupteten Art erhalten, wenngleich sie nicht die kürzeste ist, denn es gilt ja offenbar auch

$\begin{eqnarray*} 15 | 1110 \end{eqnarray*}$

24.07.2010, 07:32

Mystic

Auf diesen Beitrag antworten »

Hier nochmals, und wie ich hoffe, etwas klarer als oben, die einzelnen Schritte, welche für n mit der Primfaktorzerlegung

$\begin{eqnarray*} n=\prod_p p^{\nu_p(n)}=2^{\nu_2(n)}3^{\nu_3(n)}5^{\nu_5(n)}\ldots \end{eqnarray*}$

im Einzelnen durchzuführen sind...

1. Entferne aus n die größtmöglichen Potenzen von 2 und von 5, d.h., gehe über zu

$\begin{eqnarray*} \tilde n := \frac n{2^{\nu_2(n)}5^{\nu_5(n)}}=3^{\nu_3(n)}7^{\nu_7(n)}11^{\nu_{11}(n)}\ldots \end{eqnarray*}$

wobei $\begin{eqnarray*} \tilde n \end{eqnarray*}$ nunmehr zu 10 teilerfremd ist, was wir ja brauchen, um den Satz von Euler-Fermat anwenden zu können...

2. Setze

$\begin{eqnarray*} m:=\min(\nu_3(n),2) \end{eqnarray*}$

d.h., m ist im wesentlichen die Vielfachheit $\begin{eqnarray*} \nu_3(n) \end{eqnarray*}$ , mit der 3 in der Primfaktorzerlegung von n vorkommt, sollte diese aber größer als 2 sein, so genügt es dann für unsere Zwecke einfach m=2 zu setzen (letzteres könnte man auch generell in jedem Fall tun, wenn man sich das Leben leicht machen möchte und nicht auf die optimale Darstellung aus ist)...

3. Als nächstes muss man nun den Satz von Euler-Fermat auf

$\begin{eqnarray*} N:=3^m \tilde n \end{eqnarray*}$

und die Basis 10 anwenden, woraus sich

$\begin{eqnarray*} N=3^m \tilde n | \underbrace{111\ldots1}_{\varphi(N)} \cdot \ 9 \Rightarrow \tilde n | \underbrace{111\ldots1}_{\varphi(N)} \end{eqnarray*}$

ergibt...Obiger Schluß ist dabei im Falle m=0 und m=2 trivial und geht im Fall m=1 so wie in deinem Beispiel oben mit n=15, nämlich

$\begin{eqnarray*} N=3 \tilde n | \underbrace{111\ldots1}_{\varphi(N)} \cdot \ 9 \Rightarrow \frac{\tilde n}3 | \underbrace{111\ldots1}_{\varphi(N)} \land 3 | \underbrace{111\ldots1}_{\varphi(N)} \Rightarrow \tilde n | \underbrace{111\ldots1}_{\varphi(N)} \end{eqnarray*}$

4. Zum Schluß müssen wir die Sache mit den Potenzen von 2 und 5, welche wir aus n entfernt hatten, noch regeln... Das ist aber der einfachste Schritt, da wir ja nur die zuletzt erhaltene Teilbarkeitsbeziehung mit einer "geeignten" Potenz von 10 multiplizieren müssen, genauer

$\begin{eqnarray*} \tilde n | \underbrace{111\ldots1}_{\varphi(N)} \Rightarrow n | 10^{\max(\nu_2(n),\nu_5(n))} \underbrace{111\ldots1}_{\varphi(N)} \Rightarrow n | 111...1000...0 \end{eqnarray*}$

wobei die Anzahl der Einsen und Nullen in der letzten Darstellung $\begin{eqnarray*} \varphi(N) \end{eqnarray*}$ bzw. $\begin{eqnarray*} 10^{\max(\nu_2(n),\nu_5(n))} \end{eqnarray*}$ beträgt...

5. Speziell was die Anzahl der Einsen betrifft, sollte man zuletzt noch prüfen, ob man nicht noch zu einem echten Teiler von $\begin{eqnarray*} \varphi(N) \end{eqnarray*}$ übergehen kann, um dann die optimale, d.h., kürzestmögliche Darstellung der betrachteten Form zu erhalten... Die Anzahl der Nullen ist aber bereits kürzestmöglich...

Tja, wie gesagt, starker Tobak für den Bereich Schulmathematik, aber ich habe das mal so zusammengeschrieben, damit man sich dann auf die einzelnen Punkte gut beziehen kann, soferne dir nicht inzwischen ohnehin die Lust, da weiterzumachen, vergangen ist, wofür ich vollstes Verständnis hätte.. Augenzwinkern

24.07.2010, 07:58

Auf diesen Beitrag antworten »

Und zur Not bleiben ja noch die guten alten Schubfächer. Augenzwinkern

24.07.2010, 12:13

iluminati

Auf diesen Beitrag antworten »

Hey, Lust vergeht mir nur dann, wenn ich alles verstehe. Solange ich noch was lernen kann ist das Leben nicht langweilig. Ich habe mir Deinen Beitrag ausfühlich (mehrmals) durchgelesen und bin eigentlich äußerst zufrieden. Jetzt habe ich wirklich alles verstanden, wie du vorgegangen bist und warum. Ich danke Dir sehr. Eigentlich habe ich zwar keine richtigen Ideen eingebracht (beinahe garkeine), dennoch denke ich habe ich eine Menge gelernt.

Danke nochmals, auch an Arthur Dent

Neue Frage »

Antworten »

Teilbarkeit

Verwandte Themen