Übungstest

Dieser Übungstest besteht aus 8 Fragen zu Elementare Zahlentheorie.
Die Schwierigkeitsstufe ist leicht bis schwer.
Es können bei jeder Frage eine oder mehrere Antworten korrekt sein, aber nie alle.

Test als PDF ausgeben (Kann je nach Länge einige Minuten dauern)

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl derjenigen Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Welche Aussagen über die Phi-Funktion treffen zu? Nr. 4697
	$\varphi(3) = 2$
	$\varphi(6) = 2$
	$\varphi(8) = 3$
	$\varphi(10) = 4$
Lösungsweg $\varphi(3) = 2$ , denn ggT(3,1) = ggT(3,2) = 1. Es gibt also 2 Zahlen zwischen 1 und 3, die teilerfremd zu 3 sind (ggT: größter gemeinsamer Teiler). $\varphi(6) = 2$ , denn ggT(6,1) = ggT(6,5) = 1, ggT(6,2) = ggT(6,4) = 2 und ggT(6,3) = 3. Es gibt also 2 Zahlen zwischen 1 und 6, die teilerfremd zu 6 sind. $\varphi(8) = 4$ , denn ggT(8,1) = ggT(8,3) = ggT(8,5) = ggT(8,7) = 1, ggT(8,2) = ggT(8,6) = 2 und ggT(8,4) = 4. Es gibt also 4 Zahlen zwischen 1 und 8, die teilerfremd zu 8 sind. $\varphi(10) = 4$ , denn ggT(10,1) = ggT(10,3) = ggT(10,7) = ggT(10,9) = 1, ggT(10,2) = ggT(10,4) = ggT(10,6) = ggT(10,8) = 2 und ggT(10,5) = 5. Es gibt also 4 Zahlen zwischen 1 und 10, die teilerfremd zu 10 sind.

4 erreichbare Punkte

Welche dieser Mengen ist eine Gruppe? Nr. 4666
	$(\mathbb{Z}_4, +)$
	$(\mathbb{Z}^*_4, +)$
	$(\mathbb{Z}_4, \cdot)$
	$(\mathbb{Z}^*_4, \cdot)$
Lösungsweg $(\mathbb{Z}_4, +)$ ist eine kommutative Gruppe (neutrales Element 0, inverses Element a' = 4-a für jedes a in $\mathbb{Z}_4$ , Assoziativgesetz gilt). $(\mathbb{Z}^_4, +)$ ist keine Gruppe, da das neutrale Element fehlt: $0 \;\notin\; \mathbb{Z}^_4 = \left\{ 1,3 \right\}$ $(\mathbb{Z}_4, \cdot)$ ist keine Gruppe, da nicht jedes Element (z.B. 2) ein Inverses besitzt. $(\mathbb{Z}^_4, \cdot)$ ist eine kommutative Gruppe mit den Elementen $\mathbb{Z}^_4 = \left\{ 1,3 \right\}$ : Neutrales Element 1, Inverse $1^{-1} = 1$ und $3^{-1} = 3$ , Assoziativgesetz gilt.

4 erreichbare Punkte

Berechnen Sie $19^{73}\; mod\; 100$ durch schnelle Exponentiation! Nr. 4721
	39
	49
	59
	69
Lösungsweg Wir schreiben die Potenz 73 in Binärdarstellung: $73 = 64 + 8 + 1 = 2^6 + 2^3 + 2^0$ Somit ist $19^{73} = 19^{(2^6)} \cdot 19^{(2^3)} \cdot 19^{(2^0)} \;mod\; 100$ . Wir berechnen die einzelnen Faktoren modulo 100: $\begin{tabular}{r\|rrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64\\ 19^{(2^i)} & 19 & 61 & 21 & 41 & 81 & 61 & 21\\ \end{tabular}$ Somit ist $19^{73} = 19 \cdot 41 \cdot 21 = 59\;mod\; 100$ .

4 erreichbare Punkte

Berechnen Sie $43^{167} \;mod\; 113$ durch schnelle Exponentiation! Nr. 4723
	17
	49
	21
	97
Lösungsweg Wir schreiben die Potenz 167 in Binärdarstellung: $167 = 128 + 32 + 4 + 2 + 1 = 2^7 + 2^5 + 2^2 + 2^1 + 2^0$ Somit ist $43^{167} = 43^{(2^7)} \cdot 43^{(2^5)} \cdot 43^{(2^2)} \cdot 43^{(2^1)} \cdot 43^{(2^0)} \;mod \;113$ . Wir berechnen die einzelnen Faktoren modulo 113: $\begin{tabular}{r\|rrrrrrrr} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 2^i & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128\\ 43^{(2^i)} & 43 & 41 & -14 & -30 & -4 & 16 & 30 & -4\\ \end{tabular}$ Somit ist $43^{167} = 43 \cdot 41 \cdot (-14) \cdot 16 \cdot (-4) = 21\;mod\; 113$ .

4 erreichbare Punkte

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl der Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Ist $n=p\cdot q$ ein Produkt zweier verschiedener Primzahlen, so gilt: Nr. 4712
	$\varphi (pq) = pq-1$
	$\varphi (pq) = p+q-1$
	$\varphi (pq) = (p-1)(q-1)$
Lösungsweg Sei $a \in \left\{1,2,...,n \right\}$ . Die Zahlen a und n = pq können nur dann gemeinsame Teiler haben, wenn a ein Vielfaches von p oder q ist, denn p und q sind Primzahlen (und haben somit selbst keine echten Teiler). Es gibt q Vielfache von p in $\left\{1,2,...,n \right\}$ , und zwar p, 2p, 3p,..., qp. Ebenso gibt es p Vielfache von q in $\left\{1,2,...,n \right\}$ , und zwar q, 2q, 3q,..., pq. Bis auf pq sind diese wegen $p \neq q$ alle verschieden. Diese p+q Vielfachen müssen wir also von n abziehen, um die Anzahl der zu n teilerfremdem Zahlen zu ermitteln (und 1 addieren, da wir sonst den Kandidaten n=pq zweimal abziehen): $\varphi (n) = n - p - q +1 = pq-p-q+1 = (p-1)(q-1)$

3 erreichbare Punkte

Bestimmen Sie das additive Inverse zu 6 modulo 7! Nr. 4649
	0
	1
	2
	Es gibt kein additives Inverses zu 6 modulo 7.
Lösungsweg 6 + 1 = 7 = 0 mod 7 Also ist 1 das additive Inverse zu 6 modulo 7.

4 erreichbare Punkte

Berechnen Sie $2^{22} \;mod \;11$ ohne Taschenrechner! (Tipp: In einer Gruppe G gilt $g^{\|G\|} = 1$ für jedes Gruppenelement g.) Nr. 4703
	1
	2
	4
	8
Lösungsweg Die Ordnung von $\mathbb{Z}^*_{11}$ ist 10 (denn 11 ist eine Primzahl), somit ist $2^{10} = 1\; mod\; 11$ . Es folgt: $2^{22} = (2^{10})^2 \cdot 2^2 = 1 \cdot 2^2 = 4 \;mod \;11$

4 erreichbare Punkte

Die Eulersche $\varphi$ -Funktion ordnet jeder natürlichen Zahl n die Anzahl der Zahlen aus $\left\{1,2,...,n \right\}$ zu, die teilerfremd zu n sind. Was gilt im Falle einer Primzahl n=p? Nr. 4711
	$\varphi(p) = p$
	$\varphi(p) = p-1$
	$\varphi(p) = p-2$
	$\varphi(p) = (p-1)/2$
Lösungsweg Für jede Primzahl p ist $\varphi(p) = p-1$ , denn eine Primzahl hat nur 1 und sich selbst als Teiler. Somit ist ggT(p,1) = 1, ggT(p,p) = p und ggT(p,m) = 1 für alle ganzen Zahlen m mit $1<m<p$ .

4 erreichbare Punkte

Anmelden

Passwort vergessen
Registrieren

NEWS

Die Mathe Plattform des Technikum Wien gewinnt den eLearning Award 2019 als Projekt des Jahres in der Kategorie Hochschule.

Festigen Sie Ihre Grundkenntnisse und bereiten Sie sich auf Prüfungen vor.
Im Juli starten wieder die Warm-up Kurse - ein kostenloser Service für Aufgenommene und Studierende der FHTW.

Mathematik, Physik, Elektrotechnik, Informatik, Englisch und Deutsch in kompakten Kursen, geblockt bis September.

Anmeldung und Informationen
Warm-up-Kurse

Die Plattform wächst! Wir bauen im Moment den Bereich des Studienwissens aus. Bitte haben Sie Verständnis, dass die Inhalte dort erst nach und nach ergänzt werden. Ebenso kann es bei Design und Grafik noch zu Änderungen, Verbesserungen und kleinen Bugs kommen. Danke für Ihr Verständnis!

weitere News

Wussten Sie schon?

Wenn Sie einen Benutzer haben, vergessen Sie nicht, sich rechts oben anzumelden. Nur dann wird Ihr Lernfortschritt gespeichert.

Mathematik Übungsplattform

Übungstest

Anmelden

NEWS