Teiler einer Potenz < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Sei [mm] n:=(r+1)^m, [/mm] dann gilt bekanntlich
[mm] n=\summe_{i=0}^{m} \vektor{m \\ i}r^i
[/mm]
mit r,m [mm] \in \IN^0 [/mm] Sei nun
[mm] t:=\summe_{i=0}^{k} \vektor{m \\ i}r^i
[/mm]
für ein k [mm] \in \IN [/mm] mit 0 [mm] \le [/mm] k [mm] \le [/mm] m, so dass gilt:
t teilt n
|
Hallo,
ich hab schon Schwierigkeiten hier eine klare Überschrift zu finden. Das Problem ist wahrscheinlich eher bei der Zahlentheorie, als bei der Kombinatorik einzuordnen. Was mich hier interessiert ist, was man für alle Lösungen über k in Abhängigkeit von r und m sagen kann.
Gibt es hierzu bereits allgemeine Lösungen?
Klar ist, dass es für jedes r,m die trivialen Lösungen [mm] k_0=0 [/mm] und [mm] k_1=m [/mm] gibt.
Ich habe diese Anfrage noch in keinem anderen Forum gestellt. Sie bezieht sich auch nicht auf eine Übungsaufgabe, sondern auf ein praktisches Problem aus der Codierungstheorie. Es können nämlich nur für die so gefundenen Parameter k, r und m fehlerkorrigierende bzw. -erkennende Codes konstruiert werden (http://de.wikipedia.org/wiki/Perfekter_Code).
Viele Grüße
Jürgen
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 08:49 Mo 25.09.2006 | | Autor: | statler |
Hallo Jürgen!
> Sei [mm]n:=(r+1)^m,[/mm] dann gilt bekanntlich
>
> [mm]n=\summe_{i=0}^{m} \vektor{m \\ i}r^i[/mm]
>
> mit r,m [mm]\in \IN^0[/mm] Sei nun
>
> [mm]t:=\summe_{i=0}^{k} \vektor{m \\ i}r^i[/mm]
>
> für ein k [mm]\in \IN[/mm] mit 0 [mm]\le[/mm] k [mm]\le[/mm] m, so dass gilt:
>
> t teilt n
Ist t nicht gleich [mm] (r+1)^{k}? [/mm] Ist dann nicht t immer ein Teiler von n, außer vielleicht für r = -1? Oder bin ich noch nicht richtig wach?
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:49 Mo 25.09.2006 | | Autor: | mathiash |
Moin zusammen,
lieber Dieter, in der zweiten Summe steht ja
[mm] \vektor{m\\i}
[/mm]
und nicht
[mm] \vektor{k\\i}.
[/mm]
Mehr fällt mir momentan leider auch nicht ein.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:50 Mo 25.09.2006 | | Autor: | jbulling |
Hallo Stadler, Hallo Mathiash,
die Aussage von Mathias ist richtig. Hab grad vorsichtshalber auch nochmal geprüft, was ich geschrieben habe.
Eigentlich interessiert mich ja schon der allgemeine Fall. Mich würde vor allem interessieren, ob es dafür schon eine Lösung gibt.
Allerdings lohnt es sich den Fall r=1 genauer anzuschauen. Da sind wahrscheinlich einfachere Gesetzmäßigkeiten zu finden. Der Fall r=1 ist deshalb besonders interessant, weil wohl die meisten Codes in Computersystemen verwendet werden, die eben Informationen binär kodieren (r+1) ist nämlich die Anzahl der Buchstaben im Kodierungsalphabet, m die Länge eines Codewortes in Buchstaben (also die Bitbreite bei r=1) und k ist der halbe(?) Hammingabstand, den die Codewörter haben sollen.
Wenn man den Sonderfall r=1 betrachtet, dann wird die Sache etwas angreifbarer, denn man hat:
[mm] t:=\summe_{i=0}^{k} \vektor{m \\ i}
[/mm]
Wenn man mal den ganz einfachen Fall k=m weglässt (t=n), dann gilt
[mm] t:=\summe_{i=0}^{k} \vektor{m \\ i}=1 [/mm] + [mm] \summe_{i=0}^{k} \vektor{m \\ i}
[/mm]
und man kann daran ablesen, dass folgende Kongruenz erfüllt ist:
$1 + [mm] \summe_{i=0}^{k} \vektor{m \\ i} \equiv [/mm] 1 (mod [mm] \, [/mm] m)$
Außerdem weiss man über n:
[mm] n=(r+1)^m=2^m
[/mm]
iFür Teiler von n kommen also nur Potenzen von 2 in Frage, damit hat man also auch:
[mm] $2^x \equiv [/mm] 1 (mod [mm] \, [/mm] m)$
für ein x [mm] \in \IN [/mm] und das führt zusammen mit dem Satz von Fermat-Euler dazu, dass
[mm] $Ord_m [/mm] 2 | x$
gelten muss und damit kann man mit
[mm] $Ord_m [/mm] 2 | [mm] \varphi(m)$
[/mm]
evtl. die Suche nach geeigneten Parametern etwas beschleunigen. Allerdings sind das nur notwendige, aber keine hinreichenden Bedingungen und besonders viel hilft das vermutlich auch noch nicht. Genauso kann man das natürlich für alle (r+1) beweisen, die Primzahlen, oder Potenzen von Primzahlen sind. Bei zusammengesetzten Zahlen ist diese Bedingung aber vermutlich nicht mal mehr notwendig.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:38 So 01.10.2006 | | Autor: | jbulling |
Hallo Felix,
danke für den Link. Der ist echt interessant.
Bei d=3 gilt $t=(3-1)/2=1$ und [mm] $2^k-1 [/mm] + 1$ ist natürlich eine Zweierpotenz, aber dass das abgesehen vom Sonderfall d=7, n=23 die einzigen Lösungen sind, ist schon bemerkenswert.
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Mo 09.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[]](/images/popup.gif){kind=small}
hier