Gibt es Möglichkeit zu berechnen, welche Teiler eine bestimmte Zahl hat? Und wenn ja, wie?

11 Antworten

Franz1957
11.08.2019, 23:50

Ohne mehr oder weniger systematisches Probieren geht das nicht. Bei mühsamen Rechenaufgaben, die aber schnell gehen sollen, ist der Computer hilfreich:

franzn@linux-tsns:~> maxima
Maxima 5.41.0 http://maxima.sourceforge.net
using Lisp CLISP 2.49.92 (2018-02-18)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) factor(924);
                                    2
(%o1)                              2  3 7 11
(%i2) factor(992244);
                                  2
(%o2)                            2  3 11 7517
(%i3) factor(999222444);
                               2  2
(%o3)                         2  3  11 37 47 1451
hypergerd  12.08.2019, 18:26

Hallo Franz, das ist leider die Primfaktorzerlegung und nicht die teilerbestimmende Funktion Divisors[x].

Divisors[992244] ergibt:

1, 2, 3, 4, 6, 11, 12, 22, 33, 44, 66, 132, 7517, 15034, 22551, 30068, 45102, 82687, 90204, 165374, 248061, 330748, 496122, 992244 (24 divisors)
1
Schachpapa
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Schule, Mathematik, rechnen
11.08.2019, 23:07
  • 924 = 2 * 462
  • 462 = 2 * 231
  • 231 = 3 * 77
  • 77 = 7 * 11

Also

924 = 2^2 * 3 * 7 * 11 (das ist die Primfaktorenzerlegung)

Teiler sind alle die Zahlen, die man als Produkt aus den Primfaktoren bilden kann, darin kann die 2 kein-, ein- oder zweimal vorkommen und die anderen Faktoren (3, 7 und 11) ein- oder keinmal, insgesamt erhältst du so 3*2*2*2 = 24 verschiedene Teiler.

1, 2, 3, 4, 6, 7, 11, 12, 14, 21, 22, 28, 33, 42, 44, 66, 77, 84, 132, 154, 231, 308, 462, 924
KarlRanseierIII
11.08.2019, 23:45

Gäbe es eine direkte einfache Möglichkeit der Faktorisierung, dann wären diverse Verschlüsselungsverfahren von heute auf morgen hinfällig.

Also nein, es gibt keinen einfachen direkten Weg zur Bestimmung. Aber man kann die Bestimmung natürlich geschickt durchführen, indem man z.b. das Sieb des Eratosthenes nutzt.
hypergerd
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik
12.08.2019, 18:19

Es fehlen 2 wichtige Randbedingungen in der Frage:

1) welche Größe & "Faktorisierbarkeit" hat die gegebene Zahl:

a) kleiner als 100 Stellen oder leicht faktorisierbar

b) größer als 200 Stellen oder schwer faktorisierbar

2) welche Funktion kann als "bekannt" angesehen werden

a) Grundrechenarten

b) Primfaktorzerlegung

c) Divisors[x]

Für 1) a) und 2) b) hat mihisu bereits gut geantwortet.

Für 1) b) gibt es RSA-Zahlen ab etwa 250 Stellen, die selbst mit 100 Computern bis zum heutigen Tage nicht in ihre Primfaktoren zerlegt werden konnten.

Dann gibt es leicht faktorisierbare Zahlen mit 1 Mio. Stellen, die sehr leicht zerlegbar sind... (z.B. die Form 2^n )

zu 2) c)

Relativ kleine Zahlen (kleiner 50 Stellen oder leicht faktorisierbar) können mit der Funktion Divisors[x] berechnet werden:

https://www.wolframalpha.com/input/?i=Divisors%5B924%5D

ergibt

1, 2, 3, 4, 6, 7, 11, 12, 14, 21, 22, 28, 33, 42, 44, 66, 77, 84, 132, 154, 231, 308, 462, 924 (24 divisors)
Halbrecht
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Mathematik, rechnen, Stochastik
11.08.2019, 22:58

924

2 462

2 231

3 77

7 11

11 11 

jetzt kommt wieder handarbeit:

Man muß alle Kombis bestimmen

2 * 2 / * 3 / * 7 / * 11

4 (2*2) * 3 / * 7 / * 11 

6 (2*3) * 7 / * 11

12 (2*2*3) * 7 / *11

usw. Da fällt es schon schwierig, keinen Teiler zu vergessen.

Das überlässt man dann besser einem Programm