Zeigen Sie, dass zu jeder natürlichen Zahl n ∈ ℕ eine Zahl a ∈ ℕ existiert, die durch n teilbar ist und nur aus den …

Question

Aufgabe:

Zeigen Sie, dass zu jeder natürlichen Zahl n ∈ ℕ eine Zahl a ∈ ℕ existiert, die durch n teilbar ist und nur aus den Ziffern 0 und 1 besteht.

Versteht wer die Aufgabe, checke sie nicht und würde mich freuen, wenn ihr mir helfen könntet..

Answer 1

Hallo Sandra,

Versteht wer die Aufgabe, checke sie nicht ...

Viele schreiben, dass sie die Aufgabe nicht verstehen. Und ich frage mich dann immer ob sie wirklich die AufgabenSTELLUNG nicht verstehen. Aber das sollte doch hier nicht das Problem sein - oder?

Schwieriger wird es, wenn man nicht weiß wie man die Aufgabe angehen soll. Klar ist, dass das hier irgendwas mit Zahlentheorie und Teilbarkeit zu tun hat.

Und da gibt es diesen berühmten Satz von Euler-Fermat:$$\text{ggT}(b,n) = 1, \quad b,n \in \mathbb N \quad \implies b^{\varphi(n)} \equiv 1 \mod n$$Wobei $\varphi$ die Eulersche-Phi-Funktion ist.

Die Zahl $a$, die wir suchen, bzw. deren Existenz bewiesen werden soll, bildet sich aus$$a = \sum_{k=1}^{m} c_k \cdot 10^k \quad c_k \in \{0,\,1\}$$D.h. das $a$ ist als Summe darstellbar. Und wenn ich zunächst alle $n$ betrachte, die teilerfremd zu $10$ sind, so existiert eine Potenz von $10$ für die gilt$$10^{\varphi(n)} \equiv 1 \mod n, \quad \text{ggT}(10,n) = 1$$Gleiches gilt natürlich auch für eine Vielfaches des Exponenten. Dies ist ja unterm Strich nur eine Multiplikation obiger Gleichung mit $1$ - also$$10^{v \cdot \varphi(n)} \equiv 1 \mod n, \quad v \in \mathbb N$$Wenn man nun eine Zahl $a$ konstruiert, mit$$a = \sum_{v=1}^n 10^{v \cdot \varphi(n)} \implies n \mid a$$dann ist dieses $a$ durch $n$ teilbar, da sich alle Reste (die 1'en) zu $n$ auf addieren.

Ist $\text{ggT}(10,n) > 1$, so konstruiert man zunächst ein $a'=\sum_{v=1}^{n'} 10^{v \cdot \varphi(n')}$ mit $$n = 2^{e_2} \cdot 5^{e_5} \cdot n', \quad \text{ggT}(n',10) = 1 \land e_2,e_5 \in \mathbb N_0$$anschließend multipliziert man $a'$ mit einer Zehnerpotenz, die den fehlenden Faktor von $2^{e_2} \cdot 5^{e_5}$ enthält$$a = a' \cdot 10^{\max(e_2,e_5)}$$Damit ist gezeigt, dass sich für jedes $n$ ein $a$ aus 0'en und 1'en konstruieren lässt, welches durch $n$ teilbar ist.

Answer 2

Wenn man den Sachverhalt nur für Primzahlen zeigen kann, gilt er auch allgemein. Für Primzahlen p>9 gilt nach Fermat:

(10^p-1-1)/9 ist durch p teilbar.