gcd(24^13;423) berechnen

28.09.2019, 15:13

WelcomeGCD

gcd(24^13;423) berechnen

Hallo,

Ich würde gerne den größten gemeinsamen Teiler von $\begin{eqnarray*} 24^{13} \end{eqnarray*}$ und $\begin{eqnarray*} 423 \end{eqnarray*}$ berechnen. Für gewöhnlich würde ich den euklidschen Algorithmus verwenden, ich habe nur keinen Dunst, wie ich das mit der Potenz anstellen soll. Hier gibt es sicherlich einen Trick, den ich bis jetzt noch nicht gesehen habe...

Ich würde mich freuen, wenn mir hier weitergeholfen würde smile

28.09.2019, 15:23

WelcomeGCD

Auf diesen Beitrag antworten »

RE: gcd(24^13;423) berechnen
Ich glaube ich habe es:
Also die Primfaktoren von 423 sind 3, 3 und 47 --> $\begin{eqnarray*} 423 = 3^2\cdot 47 \end{eqnarray*}$
Die 24 hat als Primfaktoren 2,2,2,3 -> $\begin{eqnarray*} 24 = 2^3\cdot 3 \end{eqnarray*}$
$\begin{eqnarray*} 24^(13) = (2^3\cdot 3)^(13) \end{eqnarray*}$

Die Schnittmenge ist also $\begin{eqnarray*} 3^2 = 9 \end{eqnarray*}$

Ist das richtig gedacht?

28.09.2019, 16:23

mYthos

Auf diesen Beitrag antworten »

Ja, richtig!

mY+

28.09.2019, 16:26

G280919

Auf diesen Beitrag antworten »

Was soll der Reiz/Witz an der Aufgabe sein?
Das ist doch kein Uni-niveau.

28.09.2019, 16:31

WelcomeGCD

Auf diesen Beitrag antworten »

Ok sagen wir mal, ich habe jetzt keine Potenz und mochte gcd(14262992844;45) herausfinden. Bei der Potenz konnte man diesen Trick ja fast erahnen. Aber wie sehe das hier aus? Gibt es hier eine Möglichkeit per Hand?

28.09.2019, 16:45

mYthos

Auf diesen Beitrag antworten »

Ich habe den Thread mal verschoben.
----------
Das jetzt ist auch nicht viel schwerer.
Du hast lediglich zu schauen, ob die große Zahl durch die Primfaktoren von 45 teilbar ist.
(Sind eh nur zwei; 5 fällt mal flach und was ist mit 3 bzw. 9?)
Oder es bietet sich dazu auch die Kettendivision an .....

mY+

28.09.2019, 16:47

G280919

Auf diesen Beitrag antworten »

Du musst eine Primfaktorenzerlegung machen, also alle möglichen Teiler suchen.
Dabei kann man Teilbarkeitsregeln anwenden.

28.09.2019, 16:52

mYthos

Auf diesen Beitrag antworten »

Zitat:

Original von G280919
Du musst eine Primfaktorenzerlegung machen, ...

Sicher nicht von 14262992844 (!), aber ja, von 45, Teilbarkeitsregeln, das ist der Punkt!

mY+

28.09.2019, 16:58

WelcomeGCD

Auf diesen Beitrag antworten »

Ja ok, aber was ist wenn ich eine große Potenz habe, die ich sage mal den Rahmen des Taschenrechners sprengt, oder noch besser GCD(24^123+1; 45)

Die Primfaktoren von 45 sind 3 und 5, soweit so gut. Eine Teilbarkeitsregel die mir zur 5 einfällt ist: Eine Zahl ist durch 5 teilbar, wenn ihre letzte Stelle eine 5 oder eine 0 ist... Das hilft mir bei der großen Potenz aber nicht wirklich weiter...

28.09.2019, 17:08

G280919

Auf diesen Beitrag antworten »

Dann wäre da noch die Modulo-Rechnung bei großen Potenzen.

28.09.2019, 17:12

WelcomeGCD

Auf diesen Beitrag antworten »

@G280919 kannst du das weiter ausführen?

28.09.2019, 17:32

rumar

Auf diesen Beitrag antworten »

$\begin{eqnarray*} GCD(24^{123}+1; 45) \end{eqnarray*}$

Als ggT in Frage kommen da mal überhaupt nur die Teiler von 45 , also die Werte 1, 3, 5, 9, 15, 45.

Die Zahl $\begin{eqnarray*} 24^{123} \end{eqnarray*}$ ist offensichtlich durch 3 und durch 9 teilbar (sogar ziemlich oft). Addieren wir dazu noch eins, so ist die entstehende Summe also bestimmt weder durch 3 noch durch 9 teilbar.
Damit müssen wir nur noch die Teilbarkeit durch 5 abklären. Nun endet jede Potenz der Form $\begin{eqnarray*} 24^n \end{eqnarray*}$ (mit natürlichem Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ ) entweder mit der Ziffer 4 (falls $\begin{eqnarray*} n \end{eqnarray*}$ ungerade) oder mit der Ziffer 6 (falls $\begin{eqnarray*} n \end{eqnarray*}$ gerade).
Da nun der vorliegende Exponent 123 ungerade ist, endet also die Dezimaldarstellung von $\begin{eqnarray*} 24^{123} \end{eqnarray*}$ mit der Ziffer 4 und die von $\begin{eqnarray*} 24^{123}+1 \end{eqnarray*}$ mit einer 5. Daraus ist sofort ersichtlich, dass $\begin{eqnarray*} 24^{123}+1 \end{eqnarray*}$ durch 5 teilbar ist (aber eben, wie schon festgestellt, weder durch 3 noch durch 9).
Insgesamt wird also ersichtlich:

$\begin{eqnarray*} GCD(24^{123}+1; 45)\ =\ 5 \end{eqnarray*}$

Kleine Ergänzung zur Abrundung des Ganzen:

$\begin{eqnarray*} LCM(24^{123}+1; 45)\ =\ 525079713935784551004342048413861524609354360767519915560852900730831757394<br /> 319352358216705927007667239752138040364735948481961516693221405292438058641<br /> 027914152918873276425 \end{eqnarray*}$

28.09.2019, 17:43

WelcomeGCD

Auf diesen Beitrag antworten »

@rumar das beeindruckt mich jetzt schon!

Die Zahl 24123 ist offensichtlich durch 3 und durch 9 teilbar...

Hast du das allein an der Basis und der Betrachtung von versch. geraden/ungeraden Potenzen festgemacht? Ganz so offensichtlich finde ich das nicht smile

28.09.2019, 21:06

rumar

Auf diesen Beitrag antworten »

Das ist einfach.

Da 24 durch 3 teilbar ist, ist jede hohe Potenz von $\begin{eqnarray*} 24 \end{eqnarray*}$ durch $\begin{eqnarray*} 3 \end{eqnarray*}$ und durch $\begin{eqnarray*} 9 \end{eqnarray*}$ teilbar !
Genauer: weil $\begin{eqnarray*} 24=3\cdot 8 \ =\ 3 \cdot 2^3 \end{eqnarray*}$ , ist

$\begin{eqnarray*} 24^n = 3^n \cdot 2^{3 \cdot n} \end{eqnarray*}$

Für $\begin{eqnarray*} n\ge 1 \end{eqnarray*}$ ist dies durch $\begin{eqnarray*} 3 \end{eqnarray*}$ und für $\begin{eqnarray*} n \ge 2 \end{eqnarray*}$ auch durch $\begin{eqnarray*} 9 \end{eqnarray*}$ teilbar.

28.09.2019, 21:22

rumar

Auf diesen Beitrag antworten »

Zitat:

Die Zahl 24123 ist offensichtlich durch 3 und durch 9 teilbar...

Du hast offenbar noch nicht gemerkt, wie man hier Formeln (z.B. Potenzen mit Grundzahl und Hochzahl) eingeben kann. Im vorliegenden Beispiel sähe das so aus:

$\begin{eqnarray*} \qquad 24^{123} \end{eqnarray*}$

Für die Eingabe tippst du zuerst:

$\begin{eqnarray*} \qquad \end{eqnarray*}$ 24^{123}

markierst diesen Text und aktivierst dann den Button "f(x)" , um daraus eine Formel zu machen. Für die weitere Verwendung des Formeleditors (mittels LaTeX) kannst du im Menu "Tools" und im dortigen Submenu "Formeleditor" mal etwas weiter stöbern.

Neue Frage »

Antworten »

gcd(24^13;423) berechnen

Verwandte Themen