Produkt (ni über ki) modulo p < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) reagiert/warte auf Reaktion | Datum: | 14:46 Sa 28.11.2009 | Autor: | pitmat |
Aufgabe | Es soll bewiesen werden:
Produkt von (ni über ki) modulo p mit i >=1 und ni, ki < p ist gleich 1 modulo p |
Dies gehört zu einer Aufgabe, die ich begonnen habe und bei der ich nun an dieser Stelle nicht weiterkomme (es sieht also so aus, als hätte ich noch nichts alleine versucht, aber dies ist das erste Teilergebnis und ich weiß nicht, wie man weiterrechnen soll.)
Kann mir jemand sagen, ob das überhaupt sein kann (vielleicht habe ich mich verrechnet?) und wenn ja, einen Tipp geben, wie man das beweisen kann? Danke!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
|
Hallo,
also ich kann nicht erkennen, was du zeigen willst.
Es gibt einen Formeleditor und eine Eingabehilfe. Nutze bitte die Formeln, die unten stehen wenn du einen Artikel verfasst, um z.B. [mm] \vektor{n_i \\ k_i} [/mm] darzustellen.
lg Kai
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 15:06 Sa 28.11.2009 | Autor: | pitmat |
Das mit den Formeln klappt irgendwie nicht.
Also ich will zeigen:
[(n1 über k1)*(n2 über k2)* ... * (na über ka) ] modulo p = [1] modulo p
Und es gilt: ni, ki < p
|
|
|
|
|
> Das mit den Formeln klappt irgendwie nicht.
>
> Also ich will zeigen:
>
> [(n1 über k1)*(n2 über k2)* ... * (na über ka) ] modulo
> p = [1] modulo p
>
> Und es gilt: ni, ki < p
Machen wir ein einfaches Beispiel:
[mm] n_1=3 [/mm] , [mm] k_1=1 [/mm] , [mm] n_2=4 [/mm] , [mm] k_2=2 [/mm] , $p=5$
[mm] $\left[\pmat{n_1\\k_1}*\pmat{n_2\\k_2}\right]_{mod\ p}\ [/mm] =\ [mm] \left[\pmat{3\\1}*\pmat{4\\2}\right]_{mod\ 5}\ [/mm] =\ [mm] [3*6]_{mod\ 5}\ [/mm] =\ [mm] 3\,\not=\,1$
[/mm]
Die Formel stimmt also offensichtlich gar nicht.
Möglicherweise hattest du noch weitere Bedingungen
für die [mm] n_i [/mm] , [mm] k_i [/mm] und $p$ ?
Übrigens: Klicke auf die Gleichungskette, um zu sehen
wie man sie schreibt.
LG Al-Chw.
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 15:51 Sa 28.11.2009 | Autor: | pitmat |
Okay ... danke.
Die Ursprungsaufgabe ist so:
p ist prim, n = nq...no|p und k = kr...ko|p die p-al-Darstellungen von n und k aus N und sei k<n. Dann gilt:
(Tut mir leid, das mit der Formel kapiere ich nicht, da muss man das ja erstmal lange überlegen :-()
n über k ist kongruent zu
Produkt über alle i von (ni über ki) modulo p (wenn ni<ki, dann ist ni über ki = 0)
Klappt das mit den Bedingungen vielleicht oder kannst du mir einen Tipp geben, wie man die Aufgabe sonst lösen soll?
|
|
|
|
|
> Okay ... danke.
>
> Die Ursprungsaufgabe ist so:
>
> p ist prim, n = nq...no|p und k = kr...ko|p die
> p-al-Darstellungen von n und k aus N und sei k<n.
(analog zu "dezimal", "oktal": "p-al"
hab' ich das richtig verstanden ?)
> Dann gilt:
> n über k ist kongruent zu
>
> Produkt über alle i von (ni über ki) modulo p (wenn
> ni<ki, dann ist ni über ki = 0)
>
> Klappt das mit den Bedingungen vielleicht oder kannst du
> mir einen Tipp geben, wie man die Aufgabe sonst lösen
> soll?
Machen wir wieder ein Beispiel:
$p=5$ (prim)
$\ [mm] n=2413|_5\ [/mm] =\ [mm] 2*5^3+4*5^2+1*5^1+3*5^0\ [/mm] =\ [mm] 358|_{dezimal}$
[/mm]
$\ [mm] k=1302|_5\ [/mm] =\ [mm] 1*5^3+3*5^2+0*5^1+2*5^0\ [/mm] =\ [mm] 202|_{dezimal}$
[/mm]
[mm] $\left[\pmat{2\\1}*\pmat{4\\3}*\pmat{1\\0}*\pmat{3\\2}\right]\ [/mm] mod\ 5\ =\ [2*4*1*3]\ mod\ 5\ =\ 24\ mod\ 5\ =\ [mm] \mathbf{\red{4}}\not=1$
[/mm]
Habe ich da etwas missverstanden ?
LG Al-Chw.
Na endlich lichtet sich der Nebel um diese Aufgabe ein
wenig, nachdem noch Felix eingegriffen hat. Ich habe
nun im obigen Beispiel noch den Wert von [mm] \pmat{n\\k} [/mm] berechnet.
Da ist er:
12882883993663775884822443753549680614384464363413779
97736833265465601198608886534719181418297605864068744
(106 Dezimalstellen) und endet mit einer "4", also ist
tatsächlich [mm] \left[\pmat{n\\k}\right]_{mod\ 5}=\mathbf{\red{4}} [/mm] , was dem obigen Resultat entspricht.
Nach dieser Detektivtour kann man nun an die eigentliche Aufgabe
gehen und sich überlegen, ob dies nicht nur ein Zufallstreffer war.
LG
|
|
|
|
|
Status: |
(Frage) reagiert/warte auf Reaktion | Datum: | 16:51 Sa 28.11.2009 | Autor: | pitmat |
Ja, also das stimmt, aber der letzte Teil nicht. Wir sollen halt zeigen, dass n über k mod p dasselbe ist wie der Quatsch mit ni über ki mod p - das mit der 1 hatte ich ja wohl falsch rausgekriegt.
Deswegen: Wie kann man diese Aufgabe lösen? Wie soll man da rangehen?
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 02:34 So 29.11.2009 | Autor: | felixf |
Hallo!
> Ja, also das stimmt, aber der letzte Teil nicht. Wir sollen
> halt zeigen, dass n über k mod p dasselbe ist wie der
> Quatsch mit ni über ki mod p - das mit der 1 hatte ich ja
> wohl falsch rausgekriegt.
Man, das war ja eine schwere Geburt. Ich fasse das mal so zusammen:
Aufgabe |
Sei $p$ eine Primzahl, $n, k [mm] \in \IN$, [/mm] und sei $n = [mm] \sum_{i=0}^t n_i p^i$ [/mm] und $m = [mm] \sum_{i=0}^t k_i p^i$ [/mm] die $p$-adischen Darstellungen von $n$ und $k$ (mit [mm] $n_i, k_i \in \{ 0, \dots, p - 1 \}$). [/mm] Zeigen Sie, dass dann [mm] $\prod_{\stackrel{i=0}{n_i \neq 0}}^t \binom{n_i}{k_i} \equiv \binom{n}{k} \pmod{p}$ [/mm] gilt.
|
Stimmt das so?
LG Felix
|
|
|
|
|
Status: |
(Frage) überfällig | Datum: | 13:02 So 29.11.2009 | Autor: | pitmat |
Ja, genau, so ist das richtig, nur dass [mm] \binom{n_i}{k_i} [/mm] = 0 ist, wenn ni = 0 ist.
Mein Weg war, die Darstellungen im p-adischen System umzuschreiben in eine Darstellung im Dezimalsystem und das gleichzusetzen, aber da kam eben mein falscher Start raus.
Hat jemand einen Tipp, wie man das lösen kann, einen Ansatz? Das wäre echt prima, ich habe jetzt schon ewig an dieser Aufgabe gesessen. :-(
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 13:20 Di 01.12.2009 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|