Jacobisymbol ergibt nur 0 oder 1

Neue Frage »

Malcang Auf diesen Beitrag antworten »
Jacobisymbol ergibt nur 0 oder 1
Hallo zusammen,

ich weiß über das Jacobisymbol ja folgendes:
und . Es kann im Falle wenigstens eines Quadrates also nur 0 oder 1 herauskommen.

Nun frage ich mich folgendes:
Falls , ist dann eine Quadratzahl?

Ich weiß gerade keinen Beweisansatz dafür.

Edit:
Ein Skript untersützt meine Vermutung.
Alle Quadratzahlen n zwischen 1 und 10000 ergeben nur 0 oder 1 beim Jacobisymbol .

Andererseits erhalte ich bei jeder ungeraden Nichtquadratzahl in dieser Range immer irgendwann den Wert -1.
HAL 9000 Auf diesen Beitrag antworten »

Eigentlich gar nicht so schwer: Wenn keine Quadratzahl ist, dann gibt es eine Primzahl , die in der Primfaktorzerlegung von ungeradzahlig oft auftaucht, d.h., mit ungeradem sowie einer nicht durch teilbaren Zahl .

Dann gibt es ja sicher einen quadratischen Nichtrest von , während die lineare Kongruenz genau eine Lösung hat. Mit dieser Lösung setzen wir einfach und erhalten

sowie

zusammen also .
Malcang Auf diesen Beitrag antworten »

Hallo HAL 9000,

vielen Dank für deine Zeit. Ich gehe deine Antwort gerade durch, durchgestiegen bin ich allerdings noch nicht.
Der erste Absatz ist mir völlig klar.
Dann schreibst du

Zitat:
Original von HAL 9000
Dann gibt es ja sicher einen quadratischen Nichtrest von


Dies ist der Fall, da ich modulo genau so viele quadratische Reste wie Nichtreste finde.


Zitat:
Original von HAL 9000
...während die lineare Kongruenz genau eine Lösung hat.


Hier hänge ich gerade. Ich kann nichtmal genau sagen, warum. Ich verstehe den Gedankengang nicht, warum ich diese Kongruenz betrachten sollte verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Malcang
Ich verstehe den Gedankengang nicht, warum ich diese Kongruenz betrachten sollte verwirrt

Lies doch einfach weiter, dann sollte klar sein, warum man das braucht. Augenzwinkern


Sinn und Zweck dieser Überlegungen ist es, ein mit zu konstruieren, was letztlich ja auch gelingt. Und genau das ist doch der fehlende Baustein in deinen Überlegungen im Eröffnungsbeitrag, dass so ein für Nichtquadratzahlen stets existiert - und das eben war der Beweis dazu.
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von Malcang
Ich verstehe den Gedankengang nicht, warum ich diese Kongruenz betrachten sollte verwirrt

Lies doch einfach weiter, dann sollte klar sein, warum man das braucht. Augenzwinkern


Mein altbekanntes Problem Big Laugh
Ich schaue mir das in Ruhe jetzt an und schreibe dazu einiges auf. Das kann manchmal dauern, daher nicht wundern wenn hier keine Rückmeldung kommt. Danke auf jeden Fall dafür!

Könnte ich dieses Vorgehen dann nicht eigentlich in einen effizienten Test auf ungerade Quadratzahlen umsetzen?

Im Speziellen möchte ich das natürlich für den Bosmatest nutzen. Dort ist der Nenner des Jacobisymbols ja ohnehin ungerade. Sollte also jeweils nur 0 oder 1 herauskommen, kann ich den Test ja dort sogar beenden mit dem Ergebnis "Zusammengesetzt" (da ungerade Quadratzahl).
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Malcang
Dort ist der Nenner des Jacobisymbols ja ohnehin ungerade.

Ich hatte gemeint, das Jacobisymbol gibt es überhaupt nur für ungerade Nenner???
 
 
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zitat:
Original von Malcang
Dort ist der Nenner des Jacobisymbols ja ohnehin ungerade.

Ich hatte gemeint, das Jacobisymbol gibt es überhaupt nur für ungerade Nenner???


Ja, richtig. Mir gehen wieder 5 Gedanken gleichzeitig durch den Kopf.

Ich wollte auf die Effizienz als Test für ungerade Nichtquadratzahlen hinaus. Ich weiß nicht, wie man es sonst machen würde. Brute-Force natürlich mit
code:
1:
if math.sqrt(n) == math.round(math.sqrt(n))
, natürlich in sauberer programmiert.
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
...während die lineare Kongruenz genau eine Lösung hat


Ich habe nun alles verstanden bis auf diese Eindeutigkeit. Ist es so trivial und ich übersehe es? Wahrscheinlich, denn mein Ansatz das nachzuvollziehen ist:
Angenommen, es gibt und das ist doch schon wieder viel zu weit.... verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Verstehe ich das richtig? Du willst als Test dafür, ob eine Quadratzahl ist folgenden Algorithmus nehmen:

Zitat:
Berechne für bis man auf Wert -1 stößt oder bei angelangt ist. In ersterem Fall ist keine Quadratzahl, in letzterem dann doch.

Ich kenne jetzt nicht den algorithmischen Aufwand zur Bestimmung von , und möglicherweise kommt man bei Nichtquadratzahlen auch sehr bald zu einer -1. Aber sollte doch mal eine Quadratzahl damit geprüft werden, und dieses sehr groß sein, dann ist der Algorithmus-Aufwand mit ja der reinste Horror.

Da sollte man meinen, dass ein einfacher Wurzelalgorithmus schneller ist, zumal wir ja nicht mal , sondern nur die Integerzahl benötigen und dann auf prüfen.

-------------------------------------------------

Zu deiner letzten Nachfrage:

Also ein wenig Grundwissen in Modulrechnung bzw. der primen Restklassengruppe setze ich schon voraus:

Dass die LINEARE Kongruenz eindeutig bzgl. lösbar ist, weil die dazu notwendig und hinreichende Bedingung erfüllt ist.
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Zu deiner letzten Nachfrage:


Natürlich... das war mir nichtmal fremd und trotzdem hab ich daran nicht gedacht Hammer

HAL, ich danke dir vielmals für deine Mühen, das hat mich heute ein großes Stück weitergebracht.

Zitat:

Verstehe ich das richtig? Du willst als Test dafür, ob eine Quadratzahl ist folgenden Algorithmus nehmen:...


Ja, das war meine Idee. Aber wie du siehst, ist Komplexitätstheorie absolut nicht meine Stärke.
Ich war der Meinung, dass das Überprüfen auf Quadratzahlen mithilfe eines Skriptes doch fehleranfällig ist, da ja bei großen Zahlen (und deren Wurzeln) dann doch Fehler auftreten können.
HAL 9000 Auf diesen Beitrag antworten »

Über welche Zahlengrößen reden wir denn, und welche Programmiersprachen? Also Python rechnet z.B. sei Version 3 (oder gar noch etwas früher) mit beliebig genauen Integerzahlen, so dass die Überprüfung von kein Problem sein dürfte, eher schon das math.sqrt(n), weil dort die begrenzenden 53 Bit Mantisse des 64Bit-Floatingpointformats durchschlagen.

Eine reine Integerlösung, die letztgenanntes Problem umgeht:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
#!/usr/bin/python
# coding: utf-8

def heron(n):
  l = 0
  t = n
  while (t > 0):
    t >>= 2
    l+=1
  t = 1<<l
  a = t+1
  s = 0
  while (t < a):
      a = t
      t = ((n//a)+a)>>1
      s+=1
  return [a,s]

if __name__ == '__main__':
    print("Bitte natürliche Zahl eingeben:")
    try:
        n = int(input())
    except ValueError:
        n = 0
    if n>0:
        res = heron(n)
        m = res[0]
        r = n-m*m
        print("int(sqrt({})) = {} , Rest {}".format(n,m,r))
        print("Schrittzahl: {}".format(res[1]))
    else:
        print("Keine natürliche Zahl erkannt.")
Rest 0 heißt dann Quadratzahl, sonst eben keine.
Malcang Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Über welche Zahlengrößen reden wir denn, und welche Programmiersprachen? Also Python rechnet z.B. sei Version 3 (oder gar noch etwas früher) mit beliebig genauen Integerzahlen, so dass die Überprüfung von kein Problem sein dürfte, eher schon das math.sqrt(n), weil dort die begrenzenden 53 Bit Mantisse des 64Bit-Floatingpointformats durchschlagen.



Ich programmiere in python.
Über eine Zahlengröße habe ich nicht nachgedacht. Ich stelle meine Fragen gedanklich ja auf den Bosmatest ab, was ich sicherlich hier nochmal hätte nennen sollen. Daher habe ich mir keine Obergrenze in meinen Überlegungen gesetzt.
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Da sollte man meinen, dass ein einfacher Wurzelalgorithmus schneller ist, zumal wir ja nicht mal , sondern nur die Integerzahl benötigen und dann auf prüfen.

Python unterstützt wohl seit 3.8 genau so eine Funktion isqrt: Docs. Soweit ich gelesen habe unterstützt diese beliebig-großen Integer-Input. Bei StackOverflow gibt es auch einen Performance-Vergleich zwischen verschiedenen Implementationen. D.h. man muss es nicht selbst implementieren und kann diese direkt nutzen.
Malcang Auf diesen Beitrag antworten »
RE: Jacobisymbol ergibt nur 0 oder 1
Mir ist gerade noch etwas eingefallen.
Meine Frage war ja

Zitat:
Original von Malcang
Falls , ist dann eine Quadratzahl?


Jetzt ist mir eingefallen, dass 0 als Ergebnis doch ohnehin nicht rauskommt, was ja auch aus deinem Beweis hervorgeht, HAL.

Ich weiß aber ja auch, dass ich modulo jeweils quadratische Reste und Nichtreste finde, für p ungerade Primzahl.
Sollte ich also erhalten für , so kann ich doch die Primalität an dieser Stelle bereits ausschließen, oder?
HAL 9000 Auf diesen Beitrag antworten »

Peinlich, dabei habe ich 3.8.5 installiert. Bin aber wohl gedanklich noch oft bei früheren Versionen. Augenzwinkern

Gut, also einfach m=math.isqrt(n) ab Python 3.8, oder noch schneller m=gmpy2.isqrt(n). Für deinen Zweck der bloßen Feststellung "Quadratzahl oder nicht" scheint dann aber gmpy2.is_square(n) das optimale Mittel der Wahl zu sein. smile
HAL 9000 Auf diesen Beitrag antworten »
RE: Jacobisymbol ergibt nur 0 oder 1
Zitat:
Original von Malcang
Jetzt ist mir eingefallen, dass 0 als Ergebnis doch ohnehin nicht rauskommt, was ja auch aus deinem Beweis hervorgeht, HAL.

Erstaunt1

Wieso soll 0 nicht vorkommen können? Immer dann, wenn und nicht teilerfremd sind, kommt doch 0 heraus - ganz egal, ob Quadratzahl ist oder nicht.

Und mein Beweis befasst sich doch überhaupt nicht mit allen , sondern konstruiert ein ganz spezielles , welches per Konstruktion zu teilerfremd ist.
Malcang Auf diesen Beitrag antworten »
RE: Jacobisymbol ergibt nur 0 oder 1
Zitat:
Original von HAL 9000
Zitat:
Original von Malcang
Jetzt ist mir eingefallen, dass 0 als Ergebnis doch ohnehin nicht rauskommt, was ja auch aus deinem Beweis hervorgeht, HAL.

Erstaunt1

Wieso soll 0 nicht vorkommen können? Immer dann, wenn und nicht teilerfremd sind, kommt doch 0 heraus - ganz egal, ob Quadratzahl ist oder nicht.

Und mein Beweis befasst sich doch überhaupt nicht mit allen , sondern konstruiert ein ganz spezielles , welches per Konstruktion zu teilerfremd ist.


Ja, wieder mal unsauber gelesen. Ich war beim Fall n ist Primzahl. Sorry für das Durcheinander.
HAL 9000 Auf diesen Beitrag antworten »

Ursprünglich wollte ich die obige Methode "Quadratzahltest mit Jacobi-Symbolen" charakterisieren durch "mit Kanonen auf Mikroben schießen". Aber angesichts der Performance von gmpy2.isqrt ist diese Beschreibung wohl unzureichend drastisch. Big Laugh
Finn_ Auf diesen Beitrag antworten »

Die Bisektion kann man als eines der Arbeitspferde unter den numerischen Verfahren betrachten, verhält sie sich doch gutmütig, unkompliziert und einigermaßen schnell. Auch hier bietet sie eine leichter fassbare Alternative.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
# Berechnung vermittels Bisektion
def isqrt(n):
    a = 0; b = n + 1
    while a != b - 1:
        m = (a + b)//2
        if m*m <= n:
            a = m
        else:
            b = m
    return a

# Analyse des Verfahrens auf Korrektheit
# ======================================

import math

def isqrt_analysis(n):
    # Vorbedingung der Spezifikation:
    assert n >= 0

    assert 0**2 <= n
    assert n < (n + 1)**2
    a = 0; b = n + 1
    assert a**2 <= n < b**2
    while a != b - 1:
        # Schleifeninvariante:
        assert a**2 <= n < b**2
        m = (a + b)//2
        if m*m <= n:
            assert m**2 <= n
            a = m
            assert a**2 <= n
            assert n < b**2
        else:
            assert n < m**2
            b = m
            assert n < b**2
            assert a**2 <= n
        assert a**2 <= n < b**2
    assert a**2 <= n < b**2
    assert a == b - 1
    assert a**2 <= n < (a + 1)**2
    # sqrt ist streng monoton steigend.
    assert a <= math.sqrt(n) < a + 1
    assert 0 <= math.sqrt(n) - a < 1

    # Def. y == floor(x) gdw. y in Z und 0 <= x - y < 1.
    # Nachbedingung der Spezifikation (int = floor):
    assert a == int(math.sqrt(n))
    return a

def isqrt_naive(n):
    assert n >= 0
    a = 0
    assert a**2 <= n
    while not (n == a**2 or n < (a + 1)**2):
        assert a**2 < n
        assert (a + 1) <= n**2
        # Schleifeninvariante:
        assert a**2 <= n
        a += 1
        assert a**2 <= n
    assert a**2 <= n
    assert n == a**2 or n < (a + 1)**2
    if n == a**2:
        assert a**2 < (a + 1)**2
        assert n < (a + 1)**2
    if n < (a + 1)**2:
        assert n < (a + 1)**2
    assert a**2 <= n < (a + 1)**2
    assert a == int(math.sqrt(n))
    return a

N = 1000
assert all(isqrt_analysis(n) == isqrt_naive(n) for n in range(0, N))
assert all(isqrt_analysis(n) == math.isqrt(n)  for n in range(0, N))
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Finn_
und einigermaßen schnell.

Für große eher nicht. Hab mal paar Performancemessungen gemacht für :

gmpy2.isqrt : 0.00012s
math.isqrt : 0.00034s
heron (s.o.): 0.019s (18 Iterationen)
Bisektion : 4.92s (32223 Iterationen)
Finn_ Auf diesen Beitrag antworten »

Analyse des Heron-Verfahrens. Nachgewiesen wird die partielle Korrektheit. Zum Nachweis der totalen Korrektheit müsste man zusätzlich prüfen, dass das Verfahren terminiert, also nicht in eine endlose Schleife oder Ausnahme läuft.

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
# Berechnung vermittels Heron-Verfahren.
# Variante aus dem Faden "Integer square root in python".
# https://stackoverflow.com/questions/15390807/integer-square-root-in-python

def isqrt(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1 >> 1)
        while True:
            y = (x + n // x) >> 1
            if y >= x:
                return x
            x = y
    elif n == 0:
        return 0
    else:
        raise ValueError("math domain error")

# Analyse des Verfahrens auf Korrektheit
# ======================================

import math

def isqrt_analysis(n):
    if n > 0:
        x = 1 << (n.bit_length() + 1 >> 1)
        assert math.sqrt(n) < x + 1
        while True:
            # Schleifeninvariante:
            assert math.sqrt(n) < x + 1
            y = (x + n // x) >> 1
            if y >= x:
                assert x <= y
                assert math.sqrt(n) < x + 1
                assert x**2 <= n
                assert n < (x + 1)**2
                assert 0 <= math.sqrt(n) - x < 1
                # Nachbedingung der Spezifikation:
                assert x == int(math.sqrt(n))
                return x
            x = y
    elif n == 0:
        return 0
    else:
        raise ValueError("math domain error")

assert all(isqrt_analysis(n) == math.isqrt(n) for n in range(0, 1000))

Rechnung zu den Zusicherungen. Es sei



Die Gleichung erhält man als Spezialisierung und aus



Für gilt womit die Schleifeninvariante nach der Zuweisung erhalten bleibt. Durch äquivalente Umformung von erhält man nämlich die Ungleichung



Mit erhält man außerdem



Wir haben mit also die für äquivalent zu umgeformt wird.

Insgesamt gilt somit beim Verlassen der Funktion wie gewünscht



Schließlich ist noch zu prüfen, ob die Schleifeninvariante auch beim Eintritt in die Schleife gilt. Mit der Definition



ist das die Ungleichung



Wir logarithmieren sie zu



Wegen genügt die Bestätigung von



Sie wird äquivalent umgeformt zu



Die ist ja wegen erfüllt.
HAL 9000 Auf diesen Beitrag antworten »

Um mal im allgemein vorherrschenden Hype mitzuschwimmen, habe ich mich auch mal zu ChatGPT begeben und dort was mathematisches gefragt:

Kannst du mir das quadratische Reziprozitätsgesetz erklären?

Es folgten ein paar Allgemeinplätze (soweit Ok) zum Jacobi-Symbol, aber überhaupt nichts zum eigentlichen Gesetz. Daher habe ich nachgebohrt:

Das ist nur ein grober Überblick über das Gesetz - und ungenügend.

Dann kam ein etwas längerer Absatz, aus dem ich nun zitiere:

Zitat:
Im Allgemeinen besagt das Gesetz, dass es für jede natürliche Zahl a und jede natürliche Zahl b, die relativ prim zu a sind, eine bestimmte Anzahl von Lösungen x gibt, die erfüllen x^2 = b (mod a). Diese Anzahl wird durch die Jacobi-Symbol (b/a) repräsentiert, das entweder 1, -1 oder 0 sein kann. Wenn das Jacobi-Symbol (b/a) = 1 ist, gibt es (a-1)/2 Lösungen, wenn es -1 ist, gibt es keine Lösungen und wenn es 0 ist, die Anzahl der Lösungen hängt von der spezifischen Form der Gleichung ab.

Blöd nur, dass das i.a. falsch ist. Sind a,b verschiedene ungerade Primzahlen mit , so ist quadratischer Rest modulo , was wiederum heißt, dass die Kongruenz genau 2 Lösungen besitzt, nicht . Letzteres ist lediglich die Anzahl der quadratischen Reste modulo .

Auf diese lockere Art "kombiniert" also ChatGPT die aus irgendwelchen Texten zusammengeklaubten Fakten forsch zu solchen neuen interessanten Aussagen. Schöne neue Welt. smile
Malcang Auf diesen Beitrag antworten »

Guten Morgen,

sehr interessant, HAL 9000. Witzigerweise habe ich selbst erst gestern von ChatGPT erfahren und wollte es mir heute mal anschauen.

Ich frage mich gerade, was wohl passiert, wenn ich dem Bot sage, er solle mir den Beweis der Goldbachvermutung liefern.
Wird der mir sagen, was die Vermutung ist? Oder wird er sogar auf den Fakt zurückgreifen, dass sie möglicherweise unentscheidbar ist?

Na toll...die Zeiten, in denen man sich ohne Telefonnummer irgendwo anmelden konnte, sind wohl vorbei.
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von Malcang
Ich frage mich gerade, was wohl passiert, wenn ich dem Bot sage, er solle mir den Beweis der Goldbachvermutung liefern.
Wird der mir sagen, was die Vermutung ist? Oder wird er sogar auf den Fakt zurückgreifen, dass sie möglicherweise unentscheidbar ist?

Provide the proof of the Goldbach Conjecture
liefert
Zitat:
The Goldbach Conjecture is an unsolved problem in number theory that states that every even integer greater than 2 can be written as the sum of two prime numbers. Despite much effort, a proof of the conjecture has not yet been discovered.

There are several proposed proofs that have been attempted, but so far none have been accepted as a proof of the conjecture. Some of the most promising approaches include using probabilistic methods, algebraic techniques, and analytical methods. However, none of these have been successful in providing a definitive proof.

It is considered one of the oldest unsolved problems in number theory and in all of mathematics, and despite much effort, a proof or counterexample has not yet been found. The conjecture remains unproven, but it has been checked for numbers up to 4 x 10^18 and found to be true.

Auf die Nachfrage "That is not a proof, please provide a proof" bleibt es hartknäckig
Zitat:
I apologize for the confusion, as of my knowledge cutoff in 2021 and my current date, a proof of the Goldbach Conjecture has not been discovered yet. The conjecture remains unproven, and it is considered one of the oldest unsolved problems in number theory and mathematics. Many mathematicians have attempted to prove the conjecture, but so far none have been successful.

It is important to note that a conjecture can be proven false by providing a counterexample, which is a specific value for which the conjecture does not hold, but to date none such counterexample has been found for Goldbach Conjecture.

It is considered as one of the oldest and most important unsolved problems in number theory and mathematics, and it continues to be the subject of ongoing research and study.
Malcang Auf diesen Beitrag antworten »

Zugegeben, ich kenne mich natürlich nicht damit aus. Aber die Datenbank scheint also zu "wissen", dass die Goldbach-Vermutung unbewiesen ist, bringt aber Unsinn beim Jacobisymbol raus.
Malcang Auf diesen Beitrag antworten »

HAL, bitte sei nicht sauer dass ich das hier nochmal hervorkrame.
ist auch nur eine Winzigkeit, versprochen:

Zitat:
Original von HAL 9000
Eigentlich gar nicht so schwer: Wenn keine Quadratzahl ist, dann gibt es eine Primzahl , die in der Primfaktorzerlegung von ungeradzahlig oft auftaucht, d.h., mit ungeradem sowie einer nicht durch teilbaren Zahl .

Dann gibt es ja sicher einen quadratischen Nichtrest von , während die lineare Kongruenz genau eine Lösung hat. Mit dieser Lösung setzen wir einfach und erhalten

sowie

zusammen also .


Müsste ich für nicht einen Repräsentanten der Restklassen und wählen, da es ja Restklassen sind?
HAL 9000 Auf diesen Beitrag antworten »

Na mit und sind doch Repräsentanten gemeint - verstehe jetzt dein Problem nicht. Wichtig ist allerdings, dass - je nach Wahl des Repräsentanten - die Restklasse modulo , aus der dann stammt auch anders ausfallenn kann! Daher kann man von vornherein bei diesem Zugang nicht davon ausgehen, dass Repräsentant unabhängig von Zahl gewählt wird - nein, der ist sehr wohl davon abhängig!!!

Zugegeben ist das oben wohl nicht so deutlich rübergekommen, dass wirklich als ganze Zahl und nicht als Restklasse zu betrachten ist


Vielleicht mal an einem Beispiel durchrechnen: . Dann ist und .

1) Wählen wir Nichtrest , dann hat die Lösung und wir bekommen .

2) Wählen wir aber Nichtrest , dann hat die andere Lösung . Allerdings ist das (zufällig oder nicht) dieselbe Zahl.



Ok, ich hätte das ganze auch anders ausdrücken können: Für einen vorgegebenen Nichtrest besitzt das Kongruenzsystem




genau eine Lösung (der Teilerfremdheit von wegen), einfach per Chinesischem Restsatz. Der von mir oben gewählte Weg führt die Berechnung einer solchen Lösung eben sogar explizit aus.
Malcang Auf diesen Beitrag antworten »

Danke sehr HAL dass du dir nochmal die Zeit nimmst.
Ich weiß zwar worauf es hinausläuft und ich habe es auch verstanden, aber ich "stoße" mich halt an einer Sache:

Zitat:
Original von HAL 9000
1) Wählen wir Nichtrest , dann hat die Lösung und wir bekommen .

2) Wählen wir aber Nichtrest , dann hat die andere Lösung . Allerdings ist das (zufällig oder nicht) dieselbe Zahl.


Nehmen wir mal 1): Wir bekommen als Lösung heraus. Um damit zu bilden, wählen wir aber nicht die Restklasse, sondern den Repräsentanten

Das ist so ein bisschen mein Problem, dass ich hier streng genommen den Formalismus verlasse.
Sorry wenn ich da so oft nachhake.. unglücklich

Edit: Ich glaub ich hab's. Ich tue mir immer wieder schwer mit dem Formalismus, aber ich habe es jetzt so aufgeschrieben:
[attach]57660[/attach]
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »