/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
mini-bevis
Fra : Jacob Jensen


Dato : 16-09-04 15:56

Kan nogle hjælpe her?


Vi har et heltal i givet med værdi i [0..m-1] (m er en potens af 2).
Vi skal nu bevise at alle værdier

(i + sum{p=0..j}(p)) mod m, for j = 0..m-1

....er forskellige.

Sagt på en anden måde skal vi bevise at de første m tal:

(i+0) mod m, (i+1) mod m, (i+3) mod m, (i+6) mod m, (i+10) mod m...

....er forskellige.

Jacob Jensen



 
 
Jes Hansen (16-09-2004)
Kommentar
Fra : Jes Hansen


Dato : 16-09-04 16:16

> Sagt på en anden måde skal vi bevise at de første m tal:
>
> (i+0) mod m, (i+1) mod m, (i+3) mod m, (i+6) mod m, (i+10) mod m...

Følgende er taget fra Anders Thorup -- Algebra:

[Lad m være givet. Da gælder:] I følge Divisionssætningen findes for hvert
helt tal a entydigt bestemte tal q og r, således at

a=q·m+r og 0<=r<m.

Tallene r, der tilfredsstiller en ligning a=q·m+r med et helt tal q, er
netop tallene, der er kongruente med a, altsp netop elementerne i
restklassen [a]. Resultalet udsiger altså, at der i hver restklasse [a]
findes et og kun ét tal r med 0<=r<m. Denne rest kaldes den principale rest
ved division med m. Specielt følger det at antallet af restklasser er lig
med antallet af mulige principale rester, altså lig med m. Mængder Z/Zm af
restklasser består altså af de m restklasser: [0],[1],...,[m-1].

---
Med venlig hilsen
Jes Hansen




Jacob Jensen (16-09-2004)
Kommentar
Fra : Jacob Jensen


Dato : 16-09-04 17:05

> [Lad m være givet. Da gælder:] I følge Divisionssætningen findes for hvert
> helt tal a entydigt bestemte tal q og r, således at
>
> a=q·m+r og 0<=r<m.
>
> Tallene r, der tilfredsstiller en ligning a=q·m+r med et helt tal q, er
> netop tallene, der er kongruente med a, altsp netop elementerne i
> restklassen [a]. Resultalet udsiger altså, at der i hver restklasse [a]
> findes et og kun ét tal r med 0<=r<m. Denne rest kaldes den principale
> rest
> ved division med m. Specielt følger det at antallet af restklasser er lig
> med antallet af mulige principale rester, altså lig med m. Mængder Z/Zm af
> restklasser består altså af de m restklasser: [0],[1],...,[m-1].

Men vi skal vise at de tal jeg har angivet netop falder i de m restklasser.
Så ved vi de er forskellige.



Michael Knudsen (16-09-2004)
Kommentar
Fra : Michael Knudsen


Dato : 16-09-04 17:36

On Thu, 16 Sep 2004 16:55:45 +0200, Jacob Jensen wrote:

> Sagt på en anden måde skal vi bevise at de første m tal:
>
> (i+0) mod m, (i+1) mod m, (i+3) mod m, (i+6) mod m, (i+10) mod m...

Et vink: Vis, at (n mod m) = (s mod m), hvis og kun hvis m går op i n-s,
og brug dette til at vise det ønskede.

--
Michael Knudsen

Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste