Aufgabe #25 < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 12:58 Di 01.03.2005 | | Autor: | Hanno |
Hallo an alle!
Quelle: Baltic Way 2001
Es seien $p,q$ zwei verschiedene Primzahlen. Man zeige:
[mm] $\summe_{i=1}^{q-1}{\lfloor\frac{i\cdot p}{q}\rfloor}=\frac{1}{2}(q-1)(p-1)$
[/mm]
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:51 Mi 09.03.2005 | | Autor: | Hanno |
Hallo an alle!
Es bezeichne [mm] $q_x$ [/mm] den Rest von $x$ bei Division durch $q$. Dann gilt:
$ [mm] \summe_{i=1}^{q-1}{\lfloor\frac{i\cdot p}{q}\rfloor}$
[/mm]
[mm] $=\summe_{i=1}^{q-1}{\frac{i\cdot p-q_{i\cdot p}}{q}}=\frac{p}{q}\cdot\frac{q(q-1)}{2}-\frac{1}{q}\summe_{i=1}^{q-1} q_{i\cdot p}$
[/mm]
Nehmen wir an, es gäbe [mm] $i,j\in \{1,2,...,q-1\}$ [/mm] mit [mm] $i\not= [/mm] j$ und [mm] $i\cdot p\equiv j\cdot p\pmod{q}$. [/mm] Dann folgt [mm] $q|(i-j)p\Longrightarrow [/mm] i=j$ - Widerspruch. Folglich nimmt der Term [mm] $q_{i\cdot p}$ [/mm] alle Werte von $1$ bis $q-1$ an, es gilt also
[mm] $=\frac{p(q-1)}{2}-\frac{q(q-1)}{2q}=\frac{(p-1)(q-1)}{2}$, [/mm]
was zu zeigen war.
Liebe Grüße,
Hanno
|
|
|
|
