Beweise oder Widerlege < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 10:50 So 29.11.2009 | | Autor: | wauwau |
| Aufgabe | Sei k eine positive, ganze Zahl und [mm] $q_i, [/mm] p$ verschiedene Primzahlen
Zeige oder widerlege folgendes:
[mm] $\prod_{i=1}^{k}q_i \equiv [/mm] a [mm] \mod (p^2) [/mm] $ dann
[mm] $\prod_{i=1}^{k}(q_i-1) \not \equiv [/mm] a [mm] \mod [/mm] (p) $ |
Hat irgendwer eine Idee?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:03 So 29.11.2009 | | Autor: | felixf |
Hallo!
> Sei k eine positive, ganze Zahl und [mm]q_i, p[/mm] verschiedene
> Primzahlen
> Zeige oder widerlege folgendes:
> [mm]\prod_{i=1}^{k}q_i \equiv a \mod (p^2)[/mm] dann
> [mm]\prod_{i=1}^{k}(q_i-1) \not \equiv a \mod (p)[/mm]
Ich denke ich haette da ein Gegenbeispiel: sei $p = 3$ und $k = 2$, [mm] $q_1 [/mm] = 5$, [mm] $q_2 [/mm] = 11$. Dann ist [mm] $q_1 q_2 \equiv [/mm] 1 [mm] \pmod{9}$, [/mm] also setze $a := 1$. Jedoch ist [mm] $(q_1 [/mm] - 1) [mm] (q_2 [/mm] - 1) = 4 [mm] \cdot [/mm] 10 = 40 [mm] \equiv [/mm] 1 = a [mm] \pmod{3}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion | | Datum: | 14:24 So 29.11.2009 | | Autor: | wauwau |
| Aufgabe | | Für welche a könnte es gelten (z.B. a=2, 1<a<p)? |
?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:47 Di 01.12.2009 | | Autor: | felixf |
Hallo!
> Für welche a könnte es gelten (z.B. a=2, 1<a<p)?
> ?
Wenn fuer irgendein [mm] $q_i$ [/mm] gilt, dass [mm] $q_i \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] ist, dann stimmt die Aussage: dann ist [mm] $\prod_{i=1}^k (q_i [/mm] - 1) [mm] \equiv [/mm] 0 [mm] \pmod{p}$, [/mm] waehrend [mm] $\prod_{i=1}^k q_i \not\equiv [/mm] 0 [mm] \pmod{p}$ [/mm] ist.
Im Fall $a = 2$ und $p = 3$ gilt die Aussage also: wenn alle [mm] $q_i \equiv [/mm] 2 [mm] \pmod{3}$ [/mm] sind, ist [mm] $\prod_{i=1}^k (q_i [/mm] - 1) [mm] \equiv [/mm] 1 [mm] \not\equiv [/mm] a [mm] \pmod{p}$.
[/mm]
Ist $k = 2$, so muss [mm] $q_1 [/mm] + [mm] q_2 \not\equiv [/mm] 1 [mm] \pmod{p}$ [/mm] gelten, damit die Aussage gilt. Ist $p > 3$ (oder etwas groesser?), so kann man [mm] $a_1, a_2 \in \{ 1, \dots, p - 1 \}$ [/mm] waehlen mit [mm] $a_1 [/mm] + [mm] a_2 \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] und [mm] $a_1 a_2 \not\equiv [/mm] 0 [mm] \pmod{p}$: [/mm] dies ist aequivalent dazu, dass mind. eins der Polynome [mm] $x^2 [/mm] - x + [mm] \lambda$, $\lambda \in \{ 2, \dots, p - 1 \}$ [/mm] ueber [mm] $\IF_p$ [/mm] in Linearfaktoren zerfaellt. Wenn es kein solches [mm] $\lambda$ [/mm] gaebe, wuerde es vermutlich zu wenig Quadrate modulo $p$ geben (einfach die $pq$-Formel auf das Polynom anwenden). Und wenn man solche [mm] $a_1, a_2$ [/mm] hat, kann man Primzahlen [mm] $q_1, q_2$ [/mm] mit [mm] $q_i \equiv a_i \pmod{p}$ [/mm] waehlen, und hat einen Widerspruch fuer die Aussage.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 06:31 Di 01.12.2009 | | Autor: | felixf |
Hallo,
> Ich denke ich haette da ein Gegenbeispiel: sei [mm]p = 3[/mm] und [mm]k = 2[/mm],
> [mm]q_1 = 5[/mm], [mm]q_2 = 11[/mm]. Dann ist [mm]q_1 q_2 \equiv 1 \pmod{9}[/mm], also
> setze [mm]a := 1[/mm]. Jedoch ist [mm](q_1 - 1) (q_2 - 1) = 4 \cdot 10 = 40 \equiv 1 = a \pmod{3}[/mm].
das kann man verallgemeinern: ist $a = 1$, so kann man immer [mm] $q_1, \dots, q_{p-1}$ [/mm] finden, bei denen [mm] $\prod_{i=1}^{p-1} q_i \equiv \prod_{i=1}^{p-1} q_i \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] ist. Man waehlt einfach ein $1 < s < p$ und waehlt die [mm] $q_i$ [/mm] so, dass [mm] $q_i \equiv [/mm] s [mm] \pmod{p}$ [/mm] ist. Die Behauptung folgt dann mit dem kleinen Satz von Fermat.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:42 Do 03.12.2009 | | Autor: | wauwau |
| Aufgabe | | Und wie könnte es für a ungleich 1 ausschauen ??? |
z.B: a=2
|
|
|
| |
|
Hallo wauwau,
auch dafür ein Gegenbeispiel:
[mm] p=5, q_1=3, q_2=13 \quad \Rightarrow q_1 q_2 \equiv 14 \mod{p^2} \quad \wedge \quad (q_1 -1)(q_2 -1)= 24\equiv 14\mod{p} [/mm]
und noch eins für [mm]\blue{a\equiv 2\mod{p}}[/mm]:
[mm] \blue{p=7, q_1=11, q_2=53 \quad \Rightarrow q_1 q_2 \equiv 44 \mod{p^2} \quad \wedge \quad (q_1 -1)(q_2 -1)= 520\equiv 2\equiv 44\mod{p}} [/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:32 Mi 09.12.2009 | | Autor: | wauwau |
|
|
|
| |
|
Hallo wauwau,
![[haee]](/images/smileys/haee.gif "[haee]")
Darf ich das verstehen, und wenn ja, wie?
Die Kongruenzklasse [mm] a\mod{p} [/mm] wird ja normalerweise mit a<p angegeben, so auch in den obigen Beispielen von Felix und mir.
Oder meinst Du, dass in der Voraussetzung [mm] a\mod{p^2} [/mm] bereits a<p gelten soll?
Hast Du übrigens auch eigene Ergebnisse oder Ansätze?
lg
reverend
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 14:09 Do 10.12.2009 | | Autor: | wauwau |
| Aufgabe | Meine ursprüngliche Aufgabe bei der Untersuchung von Produktvariationen war:
gilt für ein gewisses natürliches k, [mm] q_i, [/mm] p versch. Primzahlen
[mm] $\prod_{i=1}^{n}q_i [/mm] = [mm] kp^2+2$
[/mm]
dann folgt
[mm] $\prod_{i=1}^{n}(q_i [/mm] -1) [mm] \not= kp^2-kp+2$ [/mm] |
Da ich da mit Ungleichungsabschätzungen nicht weitergekommen bin, habe ich nun mal versucht das ganze Zahlentheoretisch zu verallgemeinern, was mit aber bis jetzt auch nicht geholfen hat.
Außer du checkst das!
Zu deinen Fragen:
>..........
> Oder meinst Du, dass in der Voraussetzung [mm]a\mod{p^2}[/mm]
> bereits a<p gelten soll?
Ja genau!
>
> Hast Du übrigens auch eigene Ergebnisse oder Ansätze?
>
> lg
> reverend
|
|
|
| |
|
Hallo wauwau,
> gilt für ein gewisses natürliches k, [mm]q_i,[/mm] p versch.
> Primzahlen
> [mm]\prod_{i=1}^{n}q_i = kp^2+2[/mm]
> dann folgt
> [mm]\prod_{i=1}^{n}(q_i -1) \not= kp^2-kp+2[/mm]
Ist das in beiden Zeilen das gleiche k? (Ich nehme an, nein)
Sind die [mm] q_i [/mm] paarweise verschieden, will heißen, ist das Produkt quadratfrei? (Ich nehme an, ja)
Soweit ich sehe, macht die Aufgabe am ehesten Sinn mit meiner obigen Deutung, auch wenn sie davon nicht abhängt.
Ich vermute, dass sie nicht allgemein lösbar ist, obwohl ich jetzt noch nicht daran gearbeitet habe. Das formulierte Problem erinnert doch sehr an die Definition der Carmichael-Zahlen. Zumindestens dürfte es schwierig werden, einen Lösungsweg zu finden; die Giuga-Vermutung ist ja auch noch nicht bewiesen...
Die Frage lasse ich halboffen, vielleicht weiß ja jemand mehr.
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:22 Fr 11.12.2009 | | Autor: | wauwau |
Danke für den Hinweis mit den Carmichael Zahlen, vielleicht komme ich da ein wenig weiter.
Meine grundlegende Betrachtung war:
Verändert man alle Summanden einer Summe um den gleichen Betrag, so kann man die Änderung der Summe leicht und exakt bestimmen.
Wie schaut das aber bei Produkten aus. Wie kann das Produkt variieren, wenn man alle Faktoren um konstante Beträge verändert.
Da habe ich natürlich mal Spezialfälle (quadratfreie Zahlen) betrachtet
Antworten dann unten.
DAnke noch mal... Vielleicht fällt dir nochwas ein..
> Hallo wauwau,
>
> > gilt für ein gewisses natürliches k, [mm]q_i,[/mm] p versch.
> > Primzahlen
> > [mm]\prod_{i=1}^{n}q_i = kp^2+2[/mm]
> > dann folgt
> > [mm]\prod_{i=1}^{n}(q_i -1) \not= kp^2-kp+2[/mm]
>
> Ist das in beiden Zeilen das gleiche k? (Ich nehme an,
> nein)
Sollte schon das gleich k sein.
> Sind die [mm]q_i[/mm] paarweise verschieden, will heißen, ist das
> Produkt quadratfrei? (Ich nehme an, ja)
Ja
>
> Soweit ich sehe, macht die Aufgabe am ehesten Sinn mit
> meiner obigen Deutung, auch wenn sie davon nicht abhängt.
>
> Ich vermute, dass sie nicht allgemein lösbar ist, obwohl
> ich jetzt noch nicht daran gearbeitet habe. Das formulierte
> Problem erinnert doch sehr an die Definition der
> Carmichael-Zahlen. Zumindestens dürfte es schwierig
> werden, einen Lösungsweg zu finden; die Giuga-Vermutung
> ist ja auch noch nicht bewiesen...
>
> Die Frage lasse ich halboffen, vielleicht weiß ja jemand
> mehr.
>
> lg
> reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:20 Sa 12.12.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
