matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenZahlentheorieProdukt aus glatten Zahlen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Zahlentheorie" - Produkt aus glatten Zahlen
Produkt aus glatten Zahlen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Produkt aus glatten Zahlen: glatte Zahlen Produkt
Status: (Frage) beantwortet Status 
Datum: 23:21 Mi 18.09.2013
Autor: zahlentheorie

Hallo,

ich habe folgende Aufgabe:

Eine natürliche Zahl n heißt glatt bezüglich einer Schranke S, wenn in der Primfaktorzerlegung von n keine Primzahlen größer als S vorkommen.

Gegeben sei nun eine Menge von 2000 glatten Zahlen bezüglich der Schranke 19. Ich soll zeigen, dass es dann möglich ist, aus dieser Menge 8 Zahlen auszuwählen, sodass deren Produkt die 8. Potenz einer ganzen Zahl ist.

Was ich bisher herausgefunden habe, ist, dass ich, wenn ich zwei Zahlen auswählen will, sodass deren Produkt ein Quadrat ist, so muss meine Menge mindestens 257 Zahlen umfassen, denn es gibt 8 Primzahlen, die kleiner/gleich 19 sind. Betrachte ich die Exponenten in der Primzahlzerlegung modulo 2, so gibt es [mm] 2^8 [/mm] verschiedene Kombinationen von Primzahlexponenten. Nehme ich einen mehr, habe ich mindestens 2 Zahlen, mit der gleichen Primzahlkombination modulo 2. Multipliziere ich diese, erhalte ich ein Quadrat.

Mir ist es nur noch nicht gelungen, dieses Konzept von 2 auf 8 zu erhöhen, ohne dabei viel mehr als 2000 Zahlen zu benötigen. Hat jemand einen Tipp?

LG

Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Produkt aus glatten Zahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 00:15 Do 19.09.2013
Autor: felixf

Moin!

> ich habe folgende Aufgabe:
>  
> Eine natürliche Zahl n heißt glatt bezüglich einer
> Schranke S, wenn in der Primfaktorzerlegung von n keine
> Primzahlen größer als S vorkommen.
>  
> Gegeben sei nun eine Menge von 2000 glatten Zahlen
> bezüglich der Schranke 19. Ich soll zeigen, dass es dann
> möglich ist, aus dieser Menge 8 Zahlen auszuwählen,
> sodass deren Produkt die 8. Potenz einer ganzen Zahl ist.

Ich vermute, die Zahlen sollen jeweils paarweise verschieden sein?

> Was ich bisher herausgefunden habe, ist, dass ich, wenn ich
> zwei Zahlen auswählen will, sodass deren Produkt ein
> Quadrat ist, so muss meine Menge mindestens 257 Zahlen
> umfassen, denn es gibt 8 Primzahlen, die kleiner/gleich 19
> sind. Betrachte ich die Exponenten in der Primzahlzerlegung
> modulo 2, so gibt es [mm]2^8[/mm] verschiedene Kombinationen von
> Primzahlexponenten. Nehme ich einen mehr, habe ich
> mindestens 2 Zahlen, mit der gleichen Primzahlkombination
> modulo 2. Multipliziere ich diese, erhalte ich ein Quadrat.

Genau.

> Mir ist es nur noch nicht gelungen, dieses Konzept von 2
> auf 8 zu erhöhen, ohne dabei viel mehr als 2000 Zahlen zu
> benötigen. Hat jemand einen Tipp?

Du hast ja praktisch folgendes Problem: gegeben sind 2000 Elemente [mm] $v_1, \dots, v_{2000}$ [/mm] aus $X := [mm] (\IZ/8\IZ)^8$. [/mm] Gesucht sind jetzt acht verschiedene Indices [mm] $i_1, \dots, i_8$ [/mm] mit [mm] $\sum_{j=1}^8 v_{i_j} [/mm] = 0$. Insgesamt hat $X$ nun [mm] $8^8 [/mm] = [mm] 2^{3 \cdot 8} [/mm] = [mm] 2^{24}$ [/mm] Elemente, was wesentlich mehr 2000 ist.

Wenn du vier Elemente aus [mm] $v_1, \dots, v_{2000}$ [/mm] addierst, gibt es dafuer [mm] $\binom{2000}{4}$ [/mm] Moeglichkeiten. Das ist groesser als $39617 [mm] \cdot [/mm] |X|$, also sehr gross im Vergleich zu [mm] $8^8 [/mm] = |X|$. Damit kannst du vielleicht zeigen, dass es zwei disjunkte(!) vierelementige Teilmengen von [mm] $\{ 1, \dots, 2000 \}$ [/mm] geben muss, deren zugehoerige Summen jeweils zusammenaddiert 0 ergeben.

(Das es zwei solche Teilmengen gibt, die moeglicherweise jedoch nicht disjunkt sind, ist einfach zu zeigen.)

LG Felix


Bezug
                
Bezug
Produkt aus glatten Zahlen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 00:42 Do 19.09.2013
Autor: zahlentheorie

Danke für deine Antwort!

"(Das es zwei solche Teilmengen gibt, die moeglicherweise jedoch nicht disjunkt sind, ist einfach zu zeigen.) "

Noch nicht einmal das sehe ich gerade einfach so :( Ich sehe gerade überhaupt nicht, wie man überhaupt mit Sicherheit auch nur eine vierelementige Teilmenge [mm] $\{i_1,i_2,i_3,i_4\}$ $\subset \{1, ..., 2000\}$ [/mm] nehmen kann, sodass [mm] $v_{i_1}+v_{i_2}+v_{i_3}+v_{i_4} [/mm] = 0$. Wenn das ginge, könnte man dann nicht das gleiche Argument benutzen, um aus den [mm] $\binom{2000}{8}$ [/mm] möglichen Summen aus 8 Summanden, eine solche rauszusuchen, sodass deren Summe gleich 0 ist? Da gibt es ja noch viel mehr Möglichkeiten.

Oder habe ich da ein enormes Brett vorm Kopf? Vielleicht ist es auch schon etwas spät, um etwas sinnvolles zu leisten.

Bezug
                        
Bezug
Produkt aus glatten Zahlen: Antwort
Status: (Antwort) fertig Status 
Datum: 06:47 Fr 20.09.2013
Autor: felixf

Moin!

> Danke für deine Antwort!
>  
> "(Das es zwei solche Teilmengen gibt, die moeglicherweise
> jedoch nicht disjunkt sind, ist einfach zu zeigen.) "

Ah, ganz so einfach ist das doch wieder nicht ;-)

> Noch nicht einmal das sehe ich gerade einfach so :( Ich
> sehe gerade überhaupt nicht, wie man überhaupt mit
> Sicherheit auch nur eine vierelementige Teilmenge
> [mm]\{i_1,i_2,i_3,i_4\}[/mm] [mm]\subset \{1, ..., 2000\}[/mm] nehmen kann,
> sodass [mm]v_{i_1}+v_{i_2}+v_{i_3}+v_{i_4} = 0[/mm]. Wenn das ginge,

Ich hab nicht nach $= 0$ gesucht, sondern nach zwei solchen Teilmengen die die gleiche Summe (modulo 8) liefern. Damit kommt man aber nicht direkt weiter.

So wie du es gemacht hast, ist es am einfachsten und funktioniert auch ohne viel Aufwand ;-)

LG Felix


Bezug
        
Bezug
Produkt aus glatten Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:47 Do 19.09.2013
Autor: zahlentheorie

Ich habe es inzwischen gelöst. Hat man mehr als 257 Zahlen, so lassen sich ja zwei finden, deren Produkt eine Quadratzahl ist. Nun nimmt man diese beiden Zahlen aus der Menge heraus und wiederholt diesen Vorgang, bis nur noch 255 Zahlen in der Menge enthalten sind. Auf diese Weise hat man dann eine neue Menge aus Quadratzahlen generiert, auf die man wieder das gleiche Verfahren anwendet. Auf diese Weise gelangt man zur Lösung.

Bezug
                
Bezug
Produkt aus glatten Zahlen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 06:45 Fr 20.09.2013
Autor: felixf

Moin!

> Ich habe es inzwischen gelöst. Hat man mehr als 257
> Zahlen, so lassen sich ja zwei finden, deren Produkt eine
> Quadratzahl ist.

Es reicht schon, wenn es mehr als 256 sind.

> Nun nimmt man diese beiden Zahlen aus der
> Menge heraus und wiederholt diesen Vorgang, bis nur noch
> 255 Zahlen in der Menge enthalten sind. Auf diese Weise hat
> man dann eine neue Menge aus Quadratzahlen generiert, auf

Und zwar $(2000 - 256) / 2 = 872$ Stueck.

> die man wieder das gleiche Verfahren anwendet.

Im naechsten Schritt bleiben $(872 - 256) / 2 = 308$ vierte Potenzen, und daraus kann man sogar $(308 - 256) / 2 = 26$ verschiedene achte Potenzen bekommen.

> Auf diese
> Weise gelangt man zur Lösung.

Sieht gut aus :)

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]