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