Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Einheiten in Restklassen + modulo

Einheiten in Restklassen + modulo

Schüler Gymnasium, 13. Klassenstufe

Tags: Einheit, modulo, restklassen

8mileproof aktiv_icon

11:18 Uhr, 02.01.2012

hallo hab folgende frage, bei der ich gerne wüsste, wie ich rechnen soll, um an die lösung zu kommen:

also die frage ist : wie lauten alle einheiten von

ℤ_{11}

und ihre Inversen ?

dazu habe ich ein beispiel in unserem skript gefunden. die rechnung steht da allerdings nicht drin. da steht:

die einheiten von

ℤ_{9}

sind genau

{0,1,2,4,5,7,8}

. es gilt :

{\bar{1}}^{- 1} = \bar{1}

{\bar{2}}^{- 1} = \bar{5}

{\bar{4}}^{- 1} = \bar{7}

{\bar{8}}^{- 1} = \bar{8}

{\bar{7}}^{- 1} = \bar{4}

{\bar{5}}^{- 1} = \bar{2}

mehr steht da nicht. kann mir jmd. erklären wie man draufkommt, und was man alles dafür braucht. solche verfahren wie ggt oder den erweiterten euklidischen algorithmus habe ich drauf. auch kann ich mit begriffen wie restklassen usw. was anfangen.

z . b

. ist

ℤ_{9}

die menge

{0,1,2,3,4,5,6,7,8}

ist. und in der menge der einheiten also

{0,1,2,4,5,7,8}

ist mir aufgefallen, dass die zahlen 3 und 6 fehlen. das hat bestimmt was zu bedeuten. ich weiß aber nicht was.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Einheitenrechnen (Mathematischer Grundbegriff)

Bummerang

12:26 Uhr, 02.01.2012

Hallo,

als Einheit taugt jede teilerfremde Zahl und die

1,

deshalb fehlen bei der 9 auch die Werte 3 und 6 (die Null sollte natürlich auch fehlen, denn das ist klar, dass die nicht zur Einheit taugt, oder?). Bei

ℤ_{11}

ist es so, dass die

11

eine Primzahl ist, da findet man keine Teiler und somit sind die Einheiten alle Werte (außer der Null!). Die Inversen findet man auch häufig einfach. Inverses der 1 ist die 1. Ist die 2 eine Einheit, dann ist wegen der Teilerfremdheit auch der Index von

ℤ

ungerade und dann ist das Inverse zur 2 im

ℤ_{n}

genau

\frac{1}{2} \cdot (n + 1)

. Wegen der Kommutativität in

ℤ_{n}

hast Du jetzt schon 3 Inverse gefunden, denn das Inverse zu

\frac{n + 1}{2}

ist dann natürlich wieder 2. Die Inversen in einer Tabelle, wie von Dir oben benutzt, bilden in der zweiten Spalte eine Permutation der ersten Spalte. Willst Du das Inverse zu einer weiteren Zahl suchen, dann mußt Du nur eine der noch nicht als Inverse gefundenen Zahlen hernehmen und probieren. Damit sinkt von gefundener Inverser zur nächsten die Anzahl der Testfälle um mindestens 1 (wenn man

z . B

. wie oben

8^{- 1} = 8

findet) oder gar um 2 (wenn man

z . B

4^{- 1} = 7

findet, dann hat man ja auch

7^{- 1} = 4

gefunden).

8mileproof aktiv_icon

16:11 Uhr, 02.01.2012

okay, vielen dank für die ausführliche erklärung. alles sehr schön. hab auch das mit der permutation verstanden...hab aber leider trotzdem ein kleines problem:

wenn ich jetzt

z

.b.die inverse zur 2 bestimmen muss...dann muss ich ja

\frac{1}{2} \cdot (n + 1)

rechnen. so kommen wir auf die 5. und bei der 4?
also wenn ich jetzt

\frac{1}{4} \cdot (n + 1)

rechne, kommt da doch nicht 7 raus...oder? sondern 2.5...wie mach ich daraus ne

\bar{7}

Bummerang

16:15 Uhr, 02.01.2012

Hallo,

wo steht bei mir, dass das mit der 4 so funktioniert, dass man einfach die Regel für die 2 hernimmt und nur die 2 durch die 4 ersetzt? Wenn Du Dir selbst Berechnungsformeln kreierst, dann sollten die auch stimmen und wenn Du auf kein sinnvolles Ergebnis kommst, dann ist das ein relativ sicheres Anzeichen dafür, dass die von Dir erdachte Regel nicht stimmt!

8mileproof aktiv_icon

16:18 Uhr, 02.01.2012

natürlich steht das bei dir nicht....ich dachte, weil das mit dem

\frac{1}{2}

bei 2 geklappt hat, dann muss das doch auch mit dem

\frac{1}{4}

bei der 4 klappen....

wieso die aufregung?

Bummerang

16:27 Uhr, 02.01.2012

Hallo,

"ich dachte, weil das mit dem

\frac{1}{2}

bei 2 geklappt hat, dann muss das doch auch mit dem

\frac{1}{4}

bei der 4 klappen"

Das ist ein gewagter Analogieschluß! Man sollte mit solchen Vermutungen immer vorsichtig sein und wenigstens ein paar bestätgende Beispiele parat haben, wenn man solche Analogieschlüsse unbeweisen in der Öffentlichkeit (und das hier ist sehr öffentlich!) benutzt. Du selbst hast festgestellt, dass das nicht klappt und kommst nicht auf die Idee, dass an Deinem Schluß etwas falsch sein muß? Mir persönlich ist das ja egal, was Du hier von dem schreibst, was Du so denkst, aber denke immer daran, dass das hier alle lesen können, dass alle daraus Schlüsse über Dich ziehen werden, auch wenn sie noch so falsch sind. Wie gesagt, mir ist das egal, aber Dir auch?

8mileproof aktiv_icon

16:38 Uhr, 02.01.2012

ähm....ich weiß nicht, in was für ne richtung das geht...aber das ist definitiv die falsche.

ähm...könntest du mir nicht einfach zeigen, wie es bei der 4 geht ? weil, (ich wiederhole): das mit dem

\frac{1}{2},

dachte ich, sei allgemein und mit dem

\frac{1}{4}

habe ich nur gepostet, weil zeigen wollte wie ich versucht habe die

\bar{7}

bei der 4 rauszubekommen. so. natürlich seh ich dass das falsch ist. das sehen auch diejenigen, die meinen obigen beitrag/fragestellung lesen.

p . s . :

auch das kann ich wiederholen: wieso die aufregung?

Bummerang

17:27 Uhr, 02.01.2012

Hallo,

wenn es für die 4 so einfach in einem Term ginge, hätte ich es angegeben! Ganz offensichtlich ist, wenn das Inverse der 2 gerade ist, dann ist das Inverse der 4 die Hälfte davon und Deine Formel wäre sogar richtig. Klappt also beim

ℤ_{11}

ausnahmsweise, weil

2^{- 1} = 6

und somit

4^{- 1} = 3 (4 \cdot 3 = 12

ist im

ℤ_{11}

natürlich äquvalent zu

1)

. Wenn aber das Inverse der 2 ungerade ist, das funktioniert schon im

ℤ_{9}

oder

ℤ_{13},

dann geht das eben nicht. Da muß man ein paar Schleifen mehr durch die Zahlen drehen, ehe man wieder bei der 1 vorbeikommt. Eine Schleife mehr bedeutet aber genau eine ungerade Anzahl mehr, das kann nicht die Lösung sein. Das selbe gilt für 3 Schleifen mehr. Und 4 und mehr Schleifen zusätzlich sind Unsinn. Bleibt also nur 2 Schleifen mehr. Da man schon bei

n + 1

eine Schleife hinter sich hat, ergeben sich dann insgesamt 3 Schleifen und als Inverses

\frac{1}{4} \cdot (3 \cdot n + 1)

. Im

ℤ_{9}

wäre das die 7 (stimmt auffallend) und im

ℤ_{13}

die

10

(Beweis durch Nachrechnen). Natürlich ist die 4 nur Einheit in

ℤ_{n}

mit ungeradem

n

. Analoge Überlegungen kann man sich für alle Dualzahlen machen, ist aber nicht wirklich sinnvoll, die Fälle werden immer vielfältiger, da ist man mit Probieren meist schneller!

PS: Ich bin nicht aufgeregt!

8mileproof aktiv_icon

10:25 Uhr, 03.01.2012

ich verstehs leider nicht....ist mir zu kompliziert....gibt es dazu kein allg. verfahren, was ich immer und immer wieder anwenden kann?

z . b

. sowas wie den erweiterten euklidischen algorithmus?

trotzdem danke....

Bummerang

10:30 Uhr, 03.01.2012

Hallo,

natürlich kannst Du das anwenden, ist eine hübsche Übung. Aber in der Praxis (außerhalb Schule und Uni) und bei Übungsaufgaben wirst Du technische Hilsmittel benutzen und in Klausuren wird sich der Aufwand auf eine akademisch überschaubare Menge beschränken, die Du, und da wiederhole ich mich, mit Probieren meist schneller ermittelst!

8mileproof aktiv_icon

23:09 Uhr, 03.01.2012

ja, hast recht. ich weiß jetzt was du mit meinst. ich hab hier zum beispiel ne aufgabe mit

ℤ_{246}

und ich muss angeben wie viele einheiten das besitzt....und wenn ich jetzt anfangen würde bei allen zahlen in

ℤ_{246}

mithilfe des ggt die teilerfremden zahlen zu

246

zu finden, dann brauche ich ja tage dafür....und in der klausur geht das ja nicht...ich kann ja schlecht sagen, dass ich die klausur mit nachhause nehme und nach 3 tagen wiederkomme...

edit: wie könnte man denn soetwas schnell bestimmen...bis jetzt hatte ich immer mit mengen wie

ℤ_{9}

und so zu tun gehabt...da ging das noch ein paar zahlen auf teilerfremdheit zu überprüfen...also immer dann wenn ggt()=1

\Rightarrow

teilerfremd....aber bei

246

kann man doch nicht alle zahlen durchgehen...ist das voll krank....

hagman aktiv_icon

23:18 Uhr, 03.01.2012

Ohne die Inversen zu suchen und wenn man nur die Anzahl der Einheiten bestimmen soll, ist es ganz einfach:
Das ist die Anzahl der zu

n

teilerfremden Zahlen zwischen 0 und

n,

auch bekannt als

φ (n)

.
Wenn

n

eine Primzahl ist, gilt

φ (n) = n - 1

(das war beispielsweise oben bei

ℤ_{11}

der Fall).
Wenn

n

eine Primzahlpotenz ist, etwa

n = p^{k}

mit

p

prim, dann ist

φ (n) = p^{k - 1} \cdot (p - 1)

oder auch

φ (n) = n \cdot (1 - \frac{1}{p})

Und wenn

n

eine beliebige Zahl

> 1

ist, kann man die Teilergebnisse für alle beteiligten Primzahlen miteinander multiplizieren bzw. es gilt

φ (n) = n \cdot \prod_{p | n} (1 - \frac{1}{p})

.

Hier ist

n = 246 = 2 \cdot 3 \cdot 41,

also

φ (n) = (2 - 1) \cdot (3 - 1) \cdot (41 - 1) = 80

8mileproof aktiv_icon

23:29 Uhr, 03.01.2012

ist das die eulersche phi-funktion?

edit: also ist hier die zahl

246

eine beliebige zahl und du machst eine primfaktorzerlegung....und die teilergebnisse werden miteinander multipliziert richtig?

ich hab das jetzt ein anderen bsp. mal ausprobiert und zwar gings um

ℤ_{276}

276 = 2 \cdot 2 \cdot 3 \cdot 23 = (2 - 1) \cdot (2 - 1) \cdot (3 - 1) \cdot (23 - 1) = 44

edit: in meiner musterlösung steht, dass da

88

rauskommen muss. hmmh...die zahl

276

ist weder eine primzahl noch eine potenz einer primzahl, sodass eigtnl. nur die 3. formel in frage kommt, oder?

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

957922

957301

	Status: nicht eingeloggt	Noch nicht registriert?