---

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

---

> 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

---

> [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.

---

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