Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n^3) keine Zweierpotenz (einschließlich 1) ist.

Question

Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n^3) keine Zweierpotenz (einschließlich 1) ist.

3 Antworten

Beste Antwort

Hässlich aber geht:

1. $ n $ kann keine Primzahlpotenz sein:

Ist $ n = p^e$, dann ist $ n^3 = p^{3e} $. Die Teilerzahlen sind $ e + 1 $ und $ 3e + 1 $. Ist $ t $ ein gemeinsamer Teiler dieser Anzahlen, so gilt auch $ t \mid 3 \cdot (e+1) $ und folglich teilt $ t $ auch die Differenz $ 3(e+1) - (3e + 1) = 2 $ $ \implies t \in \{ 1, 2 \} $.

=> n muss mindestens 2 Primfaktoren besitzen.

2. $ n = p^e \cdot q^f $ mit p, q Primzahlen, e, f > 0. Man kann annehmen, dass $ e \ge f $ ist, um sich doppelte Rechnungen zu sparen. Wir machen eine Tabelle:

$$ \begin{array}{c|c|c|c|c|c} e & f & (e+1)(f+1) & (3e+1)(3f+1) & \text{ggT} & \\\hline 1 & 1 & \color{red} 4 & - & - & \\ 2 & 1 & 6 & 28 & 2 & \\ 2 & 2 & 9 & 49 & 1 & \\ 3 & 1 & 8 & 40 & 8 & \\ 3 & 2 & 12 & 70 & 2 & \\ 3 & 3 & \color{red} {16} & - & - & \\ 4 & 1 & 10 & 52 & 2 & \\ 4 & 2 & 15 & 91 & 1 & \\ 4 & 3 & 20 & 130 & 10 & \checkmark \rightarrow 2^4 \cdot 3^3 = 432 \\ 5 & 1 & 12 & \color{red}{64} & - & \\ 5 & 2 & 18 & 112 & 2 & \\ 6 & 1 & 14 & 76 & 2 & \\ 6 & 2 & 21 & 133 & 7 & \checkmark \rightarrow 2^6 \cdot 3^2 = 576 \\ 7 & 1 & \color{red}{16} & - & - & \\ 8 & 1 & - & - & - & \color{red}{2^8 \cdot 3^1 > 432} \\ \end{array} $$

Alle überflüssigen Zeilen habe ich ausgelassen. Wenn du weißt, dass $ e = 4 $, $ f = 3 $ funktioniert musst du z.B. nicht mehr $ e = 5,f = 3,4,5$ versuchen, da diese Zahlen größer ein müssen als bei $ e = 4 $, $ f = 3 $. Wenn du bei einer der Teileranzahlen eine Zweipotenz erhältst, ist auch der ggT eine Zweierpotenz, die restlichen Zellen kann man sich also sparen. Bei einem Treffer setzen wir $ p = 2 $ und $ q = 3 $ um die kleinste Zahl zu diesen Exponenten zu erhalten.

=> 432 ist die kleinste solche Zahl mit 2 Primfaktoren.

Selbes Spiel für 3 Faktoren

$ n = p_1^{e_1} p_2^{e_2} p_3^{e_3} $ mit $ e_1 \ge e_2 \ge e_3 $

$$ \begin{array}{c|c|c|c|c|c} e_1 & e_2 & e_3 & (e_1+1)(e_2+1)(e_3+1) & (3e_1+1)(3e_2+1)(3e_3+1) & \text{ggT} & \\\hline 1 & 1 & 1 & 8 & - & - & \\ 2 & 1 & 1 & 12 & 112 & 4 & \\ 2 & 2 & 1 & 18 & 196 & 2 & \\ 2 & 2 & 2 & 27 & 343 & 1 & \\ 3 & 1 & 1 & 16 & - & - & \\ 3 & 2 & 1 & 24 & 280 & 8 & \\ 3 & 2 & 2 & 36 & 490 & 2 & \\ 3 & 3 & 1 & 32 & - & - \\ 3 & 3 & 2 & 48 & 700 & 4 & \\ 3 & 3 & 3 & 64 & - & - & \\ 4 & 1 & 1 & 20 & 208 & 4 & \end{array}$$

Hier können wir stoppen, denn $ 2^4 \cdot 3^2 \cdot 5 > 432 $ und $ 2^5 \cdot 3 \cdot 5 > 432 $

und für 4 Faktoren:

$$ \begin{array}{c|c|c|c|c|c} e_1 & e_2 & e_3 & e_4 & \prod (e_i+1) & \prod (3e_i+1) & \text{ggT} & \\\hline 1 & 1 & 1 & 1 & 16 & - & - \\ 2 & 1 & 1 & 1 & 24 & 448 & 8 & \end{array}$$

Auch hier können wir stoppen, denn $ 2^3 \cdot 3 \cdot 5 \cdot 7 > 432 $ und $ 2^2 \cdot 3^2 \cdot 5 \cdot 7 > 432 $.

Mehr als 5 können es nicht sein, denn $ 2\cdot3\cdot 5 \cdot 7 \cdot 11 >432 $.

Insgesamt kommt man zu dem Schluss, dass 432 die kleinste dieser Zahlen sein muss.

Beantwortet 14 Okt 2020 von MatHaeMatician

Ein anderes Problem?

Stell deine Frage

Doesbaddel · Answer 1 · 2020-10-14T13:14:29+0000

Da die Potenz $2^0=1$ durch die Aufgabestellung ausgeschlossen ist, kann man die triviale Lösung für $n=1$ natürlich nicht verwenden.

Deshalb habe ich Mal ein kleines Java-Programm gemacht, womit man die kleinste natürliche Zahl, die die Aussage erfüllt, auch ganz schnell herausfinden kann. Das Programm ist relativ simpel. Die Scanner-Klasse dient zum Eingeben einer Zahl, ab die man mit dem Finden einer Zahl starten will. In der Funktion factor werden die Anzahl der Divisoren berechnet. Mit findGCD berechnen wir den ggT durch die Benutzung der Modulo-Operation. In findnumber werden schließlich iterativ alle Zahlen durchprobiert und zu jeder Zahl die Anzahl der Faktoren und der ggT berechnet. Wenn der ggT dann eine Zweierpotenz ist, bricht das Programm ab und gibt die Zahl n aus. In unserem Fall wird Die kleinste Zahl ist 432 ausgegeben.

Vorteil hiervon ist, dass du auch Zahlen größer als 432 eingeben kannst und so jeweils die nächsten möglichen Zahlen findest. So finden wir auch $576,648,1296,2000,\ldots$ heraus.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Zahl eingeben");

        double number = scanner.nextDouble();
        double smallestnumber = findNumber(number);
        System.out.println("Die kleinste Zahl ist " + smallestnumber);
    }

    public static double factor(double number) {
        int counter;
        counter = 0;
        for (int i = 1; i <= Math.sqrt(number); i++)
            if (number % i == 0 && i * i != number) {
                counter = counter + 2;
            } else if (i * i == number) {
                counter++;
            }
        return counter;
    }

    public static double findGCD(double a, double b) {
        if (b == 0)
            return a;
        return findGCD(b, a % b);
    }

    public static double findNumber(double number2) {
        double gcd;
        double fctr1;
        double fctr2;
        double number;

        for (number = number2; number < 10000; number++) {
            fctr1 = factor(number);
            fctr2 = factor(Math.pow(number, 3.0));
            gcd = findGCD(fctr1, fctr2);
            if (!(istZweierpotenz((int) gcd)) && gcd != 2.0 && gcd != 1.0) {
                return number;
            }
        }
        return number;
    }

    static boolean istZweierpotenz(long x) {
        double zweierLogarithmus = Math.log(x) / Math.log(2.0);
        int gerundeterZweierLogarithmus = (int) (zweierLogarithmus + 0.5); // runden
        return potenz(2, gerundeterZweierLogarithmus) == x;
    }

    static long potenz(int basis, int exponent) {
        if (0 >= exponent) {
            return 1;
        }
        if (istGerade(exponent)) {
            return potenz(basis * basis, exponent / 2);
        } else {
            return basis * potenz(basis * basis, (exponent - 1) / 2);
        }
    }

    static boolean istGerade(int x) {
        return 0 == x % 2;
    }
}

Ermittle die kleinste natürliche Zahl n, sodass der ggT von p(n) und p(n^3) keine Zweierpotenz (einschließlich 1) ist.

3 Antworten

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: