n|999...999000...000

09.01.2010, 14:45

schmara

Auf diesen Beitrag antworten »

n|999...999000...000

Hallo,
ich grüble gerade über eine Aufgabe nach:
"Jede natürliche Zahl ist Teiler einer Zahl der Form 999...999000...000"
Meine erste Frage ist: Was ist die kleinste Zahl? 90 oder 999000?
Na auf jeden Fall kann man diese Zahl ja folgendermaßen aufschreiben:
$\begin{eqnarray*} 999...999000...000 = (\sum\limits_{i=0}^{a} (10^{i+1}-10^{i}))\cdot 10^{a+1} \end{eqnarray*}$
und jede natürliche Zahl lässt sich so aufschreiben:
$\begin{eqnarray*} n=2^{\alpha}\cdot 3^{\beta} \cdot 5^{\gamma} \cdot m \end{eqnarray*}$ wobei der ggT(m,30)=1 ist.
Jetzt denke ich eigentlich bei einem Beweis für jede natürliche Zahl an die vollständige Induktion, aber weiß jetzt nicht, wie ich das machen soll.
Hat jemand einen Tipp für mich oder hab ich bei meinen Vorüberlegungen schon einen Denkfehler? Bin über jede Hilfe dankbar!
Lg

09.01.2010, 15:08

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Die allgemeine Form dieser Zahlen ist jedenfalls

$\begin{eqnarray*} (10^n-1)10^m \quad (m,n \in \mathbb N) \end{eqnarray*}$

wobei nicht ganz klar ist, ob m=n angenommen wird und ob m=0 bzw. n=0 auch zugelassen sind... 90 ist aber so und so mit dabei...

In jedem Fall ist die Aufgabe trivial, denn man kann ja jede positive ganze Zahl als Produkt uv darstellen, wobei ggT(u,10)=1 und v keine anderen Primfaktoren als 2 und 5 enthält...

09.01.2010, 15:59

wisili

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Den Beweis habe ich noch nicht.
Eine Idee, in welcher Richtung ich suchen würde, allerdings schon.
Und zwar hat es mit Dezimalbrüchen zu tun.

Bekanntlich ist
1/6 = 15/90. 6 ist Teiler von 90 und 90 hat die Form 99...9900..00.
1/55 = 0.018181818... = 18/990, Periodenlänge 2 -> 2 Neunen, Periode beginnt 1 Stelle hinter dem Komma -> 1 Null.
1/52 = 0.01 923076 923076 923076 ... = 1923075 / 999 999 00, Periodenlänge 6 -> 6 Neunen, Periode beginnt 2 Stellen hinter dem Komma ->2 Nullen.

Diese Umwandlung eines Bruches in einen Bruch der Form ... /99...9900..00 ist immer möglich.
Diese Aussage ist offenbar äquivalent mit dem zu beweisenden Satz.

@mystic
Wieso besteht dein u aus lauter 9er-Ziffern?

09.01.2010, 16:48

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000
@wisili

Mein u besteht nicht aus lauter 9-er Ziffern, wohl aber ist richtig, dass eine Zahl u, welche zu 10 teilerfremd ist, eine gewisse Zahl

$\begin{eqnarray*} 10^n-1 \end{eqnarray*}$

teilen muss, wenn n die Ordnung von 10 mod u ist...

09.01.2010, 16:53

wisili

Auf diesen Beitrag antworten »

RE: n|999...999000...000
@mystic
Das ist (im wesentlichen) der zu beweisende Satz der Aufgabenstellung von schmara.
Wenn man ihn kennt, bzw. weiss, wessen Abkömmling er ist, dann kann man ihn subjektiv als trivial abtun.
Ich erkenne ihn aber so noch nicht ...

09.01.2010, 17:20

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Hat das denn was mit dem Satz von Euler (Fermat) zu tun? Wenn ja, ich hab ihn zwar mal nachgelesen, versteh ihn aber noch nicht so richtig.
@mystic:
dein v muss dann aber auch zum beispiel die form 2^0 oder 2*5 haben, oder?

Anzeige

09.01.2010, 17:32

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000
@schmara

Mein v hat die Form

$\begin{eqnarray*} v= 2^e5^f \quad ( e \ge 0, f \ge 0) \end{eqnarray*}$

und mein u ist zu 10 teilerfremd, d.h., man hat nach dem Satz von Euler-Fermat insbesondere

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

Es gibt aber im allgmeineren noch kleinere Hochzahlen, welche diese Bedingung erfüllen, die kleinste ist per definitionem die Ordnung von 10 mod u...

@wisili

Ja, den Begriff der Ordnung, welcher für die prime Restklassengruppe mod u ja gleich definiert ist wie allgemein für Gruppen, hab ich hier tatsächlich vorausgesetzt... Man kann sich aber auch direkt auf den Satz von Euler-Fermat (s.o.) berufen...

10.01.2010, 18:23

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Ich hab mir den Satz von Euler auch schon paar Mal angeschaut, aber leider versteh ich ihn noch nicht so richtig.
Was heißt das zum Beispiel:
$\begin{eqnarray*} 10^{\phi(u)}\equiv 1\, mod\, u \end{eqnarray*}$
Ich weiß, das ist für euch wahrscheinlich alles einfach, aber wär trotzdem toll, wenn ihr mir das noch erklären könntet..

10.01.2010, 19:34

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000
$\begin{eqnarray*} \varphi(u) \end{eqnarray*}$ (schau dir bite die LaTeX-Notation dazu an!) ist die Anzahl der natürlichen Zahlen x mit 0<x<u, welche zu u teilerfremd sind. Z.B. ist $\begin{eqnarray*} \varphi(3)=2 \end{eqnarray*}$ und tatsächlich gilt

$\begin{eqnarray*} 3|10^2-1 \end{eqnarray*}$

Allerdings ist auch

$\begin{eqnarray*} 3|10^1-1 \end{eqnarray*}$

sodass $\begin{eqnarray*} \varphi(u) \end{eqnarray*}$ also i.allg. nicht die kleinste Hochzahl mit der gewünschten Eigenschaft ist, was aber hier keine Rolle spielt...

11.01.2010, 19:30

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
hmm ok, dachte ich hab das jetzt gecheckt, aber wenn du sagst, dass $\begin{eqnarray*} \varphi (u) \end{eqnarray*}$ die Anzahl der natürlichen Zahlen sind, die zu u teilerfremd sind, dann ist das doch bei u=3 nur die 2, oder? Also wäre doch die Anzahl 1. Wo liegt denn jetzt mein Denkfehler?

11.01.2010, 19:36

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
hab grad auch gelesen, dass $\begin{eqnarray*} \varphi(10)=4 \end{eqnarray*}$ ist. aber für mich wären das nur die 3, 7 und 9.

11.01.2010, 19:43

AD

Auf diesen Beitrag antworten »

Du darfst die Zahl 1 nicht vergessen, die ist teilerfremd zu allen natürlichen Zahlen, inklusive sich selbst. Klingt vielleicht im ersten Moment komisch, ist aber streng nach Definition so.

Also:

Teilerfremd zu 3 sind {1,2}, und teilerfremd zur 10 sind {1,3,7,9}.

11.01.2010, 19:50

schmara

Auf diesen Beitrag antworten »

Ah super. Das nehm ich einfach mal so hin. Wobei ich das schon komisch finde, da 1 ja dann ein gemeinsamer Teiler ist. Naja, wenn die Definition das sagt..

11.01.2010, 21:00

wisili

Auf diesen Beitrag antworten »

Teilerfremdheit ist mit ggT=1 definiert ...

12.01.2010, 10:20

schmara

Auf diesen Beitrag antworten »

Oh Mann, das ist ja schon fast peinlich ;-) Ich hatte die Definition im Kopf, hab aber nicht weiter gedacht, dann ist das natürlich klar. Vielen Dank

15.01.2010, 15:15

schmara

Auf diesen Beitrag antworten »

Hallo,
ich habe zu der Aufgabe, die ich am Anfang vorgestellt habe einen neuen Ansatz.
Und zwar habe ich mittlerweile in Erfahrung gebracht, dass die Anzahl der Neunen nicht der Anzahl der Nullen entsprechen müssen, also würde ich sagen:

$\begin{eqnarray*} & 999...999000...000&= (10^n-1)\cdot 10^m \, \text{mit n,m} \in \mathbb{N}\\<br /> & &= (10-1)(10^{n-1}+10^{n-2}+ \ldots +1)\cdot 2^m\cdot 5^m\\<br /> & &= 9(10^{n-1}+10^{n-2}+ \ldots +1)\cdot 2^m\cdot 5^m \end{eqnarray*}$

und für jede natürliche Zahl:

$\begin{eqnarray*} & n&= a_n\cdot 10^n + a_{n-1} \cdot 10^{n-1} + \ldots +a_1 \cdot 10 + a_0\\<br /> & &= a_n \cdot 10^n + (a_{n-1} + \ldots + a_1 + a_0)(10^{n-1}+ \ldots +1) \end{eqnarray*}$

Wenn ich jetzt aufschreiben möchte, dass jede nat. Zahl Teiler einer Zahl der Form 999...999000...000 ist, kann ich dann einfach

$\begin{eqnarray*} a_n \cdot 10^n + (a_{n-1} + \ldots + a_1+ a_0)(10^{n-1}+ \ldots +1) \cdot k = 9(10^{n-1}+10^{n-2}+ \ldots +1)\cdot 2^m\cdot 5^m \, \text{mit k}\in \mathbb{N} \end{eqnarray*}$

schreiben und weiter rechnen?

17.01.2010, 13:49

schmara

Auf diesen Beitrag antworten »

ich habe gerade gemerkt, dass meine Umformung bei n falsch ist. Natürlich kann ich das nicht einfach so ausklammern...

17.01.2010, 16:24

schmara

Auf diesen Beitrag antworten »

Hi,
ich hab mir nochmal die Forenbeiträge genau angeschaut und hab jetzt einen neuen Lösungsansatz, bei dem ich glaube, dass der richtig sein könnte. Tut mir Leid, dass ich hier mal dies und mal das schreibe, aber das ist ja auch Sinn der Sache, sich neue Ideen zu holen und diese weiterzuentwickeln.
Also. Es geht immer noch um folgende Aufgabe:
"Jede natürliche Zahl ist Teiler einer Zahl der Form 999...999000...000"

Schreibe
$\begin{eqnarray*} 999...999000...000 = (10^y-1) \cdot 10^m \end{eqnarray*}$
mit $\begin{eqnarray*} y,m \in \mathbb{N} \end{eqnarray*}$

Ich habe jetzt eine Fallunterscheidung gemacht:

$\begin{eqnarray*} 1) ggT(n,10)=1\\<br /> 2) ggT(n,10)\neq1 \end{eqnarray*}$

Zu Fall 1):
Wendet man hier den Satz von Euler an, so gilt
$\begin{eqnarray*} 10^{\varphi(n)}\equiv \end{eqnarray*}$ 1 mod n.

Sei nun $\begin{eqnarray*} \varphi(n)=y \end{eqnarray*}$ . Dann gilt $\begin{eqnarray*} n|10^{y}-1. \end{eqnarray*}$

Dann gilt aber auch
$\begin{eqnarray*} n|(10^{y}-1)\cdot 10^m \end{eqnarray*}$

Die Aussage ist also für diesen Fall wahr.
Betrachten wir nun Fall 2):
In Fall 1 habe ich alle ungeraden Zahlen außer der 5 und ihre Vielfachen abgedeckt. Es bleiben also noch die geraden Zahlen und die Zahlen der Form $\begin{eqnarray*} m\cdot 5 \end{eqnarray*}$ mit $\begin{eqnarray*} m\geq1 \end{eqnarray*}$ zu zeigen.
Ich weiß nicht, wie ich das jetzt toll aufschreiben soll, aber für
$\begin{eqnarray*} m\geq 3 \end{eqnarray*}$
sind ja alle Fälle abgedeckt. Soll ich das im Einzelnen begründen? Und meint ihr, dass der Beweis so richtig ist?

17.01.2010, 16:41

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Ich kann mich hier leider nur selbst zitieren und zwar mit meinem allerersten Posting

Zitat:

Original von Mystic
Die allgemeine Form dieser Zahlen ist jedenfalls

$\begin{eqnarray*} (10^n-1)10^m \quad (m,n \in \mathbb N) \end{eqnarray*}$

[...]

In jedem Fall ist die Aufgabe trivial, denn man kann ja jede positive ganze Zahl als Produkt uv darstellen, wobei ggT(u,10)=1 und v keine anderen Primfaktoren als 2 und 5 enthält...

u ist Teiler von $\begin{eqnarray*} 10^n-1 \end{eqnarray*}$ , wie wir inzwischen schon des langen und breiten erörtert haben, und v ist offensichtlich Teiler von $\begin{eqnarray*} 10^m \end{eqnarray*}$ , jeweils für gewisse Werte von n und m...

Mehr ist dazu eigentlich nicht zu sagen, oder ist da jetzt wirklich noch etwas unklar daran? Was bringt es eigentlich, das Ganze, speziell den ersten Fall mit u, endlos wiederzukäuen? verwirrt

verwirrt

17.01.2010, 17:34

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
Vielleicht kannst du dich ja mal kurz von deine Idee lösen. Wollte ja nur wissen, ob meine Lösung vielleicht auch richtig ist!

17.01.2010, 18:07

Mystic

Auf diesen Beitrag antworten »

RE: n|999...999000...000

Zitat:

Original von schmara
Vielleicht kannst du dich ja mal kurz von deine Idee lösen. Wollte ja nur wissen, ob meine Lösung vielleicht auch richtig ist!

Ok, dann kurz ein Statement zu deiner Fallunterscheidung

1. ggT(n,10)=1
2. ggT(n,10)>1

die ich als ziemlich sinnlos erachte... Den ersten Fall haben wir hier schon mehrfach erörtert, auf den zweiten gehst du aber kaum ein, jedenfalls sehe ich nicht den Ansatz eines ernsthaften Beweises... Ich habe aber den starken Verdacht, dass man an meiner Aufspaltung uv, wobei u die Voraussetzung ggT(u,10)=1, aber v die im Vergleich zu 2. weit stärkere Bedingung $\begin{eqnarray*} v=2^e5^f \end{eqnarray*}$ für irgendwelche $\begin{eqnarray*} e,f \ge 0 \end{eqnarray*}$ erfüllt, ohnehin nicht vorbeikommt... Eine essentiell neue Beweisidee wäre mich jedenfalls eine Riesenüberraschung, aber wie heißt es so schön: Alles ist möglich... Big Laugh

Big Laugh

18.01.2010, 12:17

schmara

Auf diesen Beitrag antworten »

RE: n|999...999000...000
@mystic
Ich habe nicht mit deinem uv weitergemacht, weil ich es nicht ganz hinbekomme. Vielleicht kannst du mir nochmal helfen.
Ich schreib mal auf, bis wohin ich es verstanden habe:

$\begin{eqnarray*} 999...999000...000 = (10^k-1)\cdot 10^m (n,m\in\mathbb{N}), n=uv, ggT(u,10)=1, v=2^e\cdot 5^f \end{eqnarray*}$ .

Daraus folgt nach dem Satz von Euler:

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

Sei nun $\begin{eqnarray*} \varphi(u)=k \end{eqnarray*}$

Dann gilt also: $\begin{eqnarray*} u|10^k-1 \end{eqnarray*}$

Wir sollen zeigen, dass $\begin{eqnarray*} n|(10^k-1)\cdot 10^m \end{eqnarray*}$

also $\begin{eqnarray*} uv|(10^k-1)\cdot 10^m \end{eqnarray*}$

Wir wissen, dass $\begin{eqnarray*} u|(10^k-1) \end{eqnarray*}$ und $\begin{eqnarray*} v|10^m \end{eqnarray*}$ , aber leider gibt es ja keine Rechenregel, die erlaubt, dass das ausreicht, also wie mache ich weiter?

18.01.2010, 13:20

AD

Auf diesen Beitrag antworten »

Zitat:

Original von schmara
aber leider gibt es ja keine Rechenregel, die erlaubt, dass das ausreicht, also wie mache ich weiter?

Was gibt es nicht? Aus $\begin{eqnarray*} a|b \end{eqnarray*}$ und $\begin{eqnarray*} c|d \end{eqnarray*}$ folgt $\begin{eqnarray*} ac|bd \end{eqnarray*}$ , das geht unmittelbar aus der Definition der Teilbarkeit hervor!

P.S.: Übrigens gibt es einen netten kurzen Beweis, der gänzlich ohne Fermat u.ä. auskommt:

Zitat:

Man betrachte die $\begin{eqnarray*} (n+1) \end{eqnarray*}$ Reste der Zahlen $\begin{eqnarray*} 10^0,10^1,\ldots,10^n \end{eqnarray*}$ modulo $\begin{eqnarray*} n \end{eqnarray*}$ . Nach Schubfachprinzip sind mindestens zwei dieser Reste gleich, sagen wir $\begin{eqnarray*} 10^a \bmod n \end{eqnarray*}$ und $\begin{eqnarray*} 10^b \bmod n \end{eqnarray*}$ für $\begin{eqnarray*} a<b \end{eqnarray*}$ .

Die Zahl $\begin{eqnarray*} 10^b-10^a = 10^a\left(10^{b-a}-1\right) \end{eqnarray*}$ erfüllt dann die Bedingung der Aufgabe. Augenzwinkern

Augenzwinkern

18.01.2010, 14:13

schmara

Auf diesen Beitrag antworten »

ach danke, ich hab die Regel von der falschen Richtung aus betrachtet, denn dann geht sie natürlich nicht...

18.01.2010, 14:57

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
P.S.: Übrigens gibt es einen netten kurzen Beweis, der gänzlich ohne Fermat u.ä. auskommt: [...]

Ja, ist tatsächlich sehr nett und wohl auch am einfachsten in Hinblick auf einen reinen Existenzbeweis, wie er hier nur gefordert war.... Augenzwinkern

Augenzwinkern

1

Verwandte Themen