Modulare Arithmetik

volkard

Sqwan schrieb:

Da kann ich jetzt mit zerlegung arbeiten. War was ist bei potenzen die sehr hoch sind? 5681 zum beispiel?

Irgendwie ganz einfach irgendwie, nur ist Wikipedia-Mathematik wie immer nicht lesen.
Zum Testsn, ob deine Vermutung stimmt, bietet sich schonmal
http://www.wolframalpha.com/input/?i=phi(5681)
an.
Und bestimmt auch
http://www.wolframalpha.com/input/?i=factor(5681)
Ach ,ja, dann ist es einfach 12*18*22

Bei Primzahlenpotentzen drin wie bei 13*13*1317=37349 gehts ein wenig anders.
Irgendwie kommt 12*13*1316 raus. Als wenn ein Primfaktor nur einmal das Recht hätte, als p-1 aufzutauchen und bei allen folgenden das nicht mehr darf.

Ob das Sinn ergibt? Mal phi(27) anschauen.
27=3*3*3.
Es fallen nur 9 Zahlen raus, nämlich die durch 3 teilbaren. Durch 9 teilbare oder durch 27 teilbare sind ja schon raus, weil die ebenfalls durch 3 teilbar sind.
Das würde zur Formel phi(p^k)=pk-p^(k-1) führen. Ah, so stehts in Wikipedia.

Meine ist gleich, wegen p^k-p(k-1) = p*p^(k-1)-1*p(k-1) = (p-1)*p^(k-1)

Edit: Bisher dachte ich immer, man müsse zuerst die Primfaktoren sammeln und danach die Formel anwenden.
Anscheinen nicht. Mal den Trick eingetippt.

unsigned int phi(unsigned int n){
	unsigned int result=1;
	for(unsigned int t=2;n!=1;++t){
		if(n%t==0){
			result*=(t-1);
			n/=t;
			while(n%t==0){
				result*=t;
				n/=t;
			}
		}
	}
	return result;
}

otze

Sqwan schrieb:

EDIT: was mir noch aufgefallen ist:
bei ^32 hätte ich ein problem da 2*16+0 raus käme

Ja, für ^32 hat die Gleichung auch keine Lösung.

es muss ja auch nicht immer eine Lösung geben

Hmmm,
war das echt so durcheinander ... naja, wie auch immer.

Nochmal zum Trick mit dem Runterbrechen der Potenz.

Du hasst ja folgende Gleichung:
(13+x*17)^31 ≡ 3 (mod 4) [1]

und dank Euler weißt du folgendes:
(13+x*17)^2 ≡ 1 (mod 4) [2]

Nun müssen wir den Euler irgendwie in unsere Gleichung einbringen. Um [2] in [1] einsetzen zu können, müssen wir [1] in eine Form bringen, in die wir [2] einsetzen können. Dh wir brauchen irgendwie in [1] > (13+x*17)^2 < drin. Also irgendwie ein ^2

Dafür wenden wir die Potenzgesetze an [1] an:
(13+x*17)^31 ≡ 3 (mod 4)

(13+x*17)^(2*15+1) ≡ 3 (mod 4) -- Dort steht ne 2, das ist für uns gut

(13+x*17)^(2*15) * (13+x*17)^(1) ≡ 3 (mod 4) -- Addition der Exponenten, ist Multiplikation der Potenzen

((13+x*17)²⁾15 * (13+x*17)^(1) ≡ 3 (mod 4) -- Mutli Multi macht Expo Expo

Nun da steht jetzt unsere tolle (13+x*17)^2 und dank Euler wissen wir das dies modulo 4 gleich 1 ist. Also 1 einsetzen:

(1)^15 * (13+x17)^(1) ≡ 3 (mod 4)
(13+x17)^(1) ≡ 3 (mod 4)
13+x*17 ≡ 3 (mod 4)

ey, was solln das hier, wo ist das problem, sich für x einfach mal eine tabelle zu erstellen, also zu Fuß ausrechnen, und dann gucken, was rumkommt?

Sqwan

und dank Euler weißt du folgendes:
(13+x*17)^2 ≡ 1 (mod 4) [2]

Eben das weiß ich nicht... Den rest habe ich verstanden. Da liegt das problem. das zu berechnen...

Bullshit schrieb:

ey, was solln das hier, wo ist das problem, sich für x einfach mal eine tabelle zu erstellen, also zu Fuß ausrechnen, und dann gucken, was rumkommt?

So du Held, dann mach mir doch mal ne tabelle für alle X
(13+x*17)^133789513 ≡ 531 (mod 199417)
Ich bin gespannt auf die Tabelle... Und erst auf den Fußweg ^^
Du solltest wissen das eine eine Klausur über 1 std geht, du 5 Aufgaben zu lösen hast, von der sowas ein Teil von Aufgabe 1 ist, die aus ca 5 Teilen besteht...

volkard

199417 = ...
Per Taschenrechner keine Teiler unter 33 gefunden.
In der Tat ist das eine Primzahl. Und das zu zeigen kann nicht Teil der Klausur sein.
Dein Mimimi ist zu unvollständig.

(13+x*17)^133789513 ≡ 531 (mod 199417)
z^133789513 = 531 (mod 199417)
phi(199417)=199416
133789513%199416=180793
Und dann würde fastexp ansetzten. 199416 hat glaub ich nur 18 Bit. Ewig kanns nicht dauern.

Sqwan

nein... in der tat ist es das nicht. es war auch nur ein beispiel um zu zeigen das "einfach alle x testen" nicht der weg sein kann.

Ich häng immernoch an der scheiß bestimmung von phi... Offentlich krieg ich das bis montag morgen noch raus...

Die eulerische Funktion ist dein Problem ?

Also, die Funktion gibt dir zur Zahl x an, wieviele teilerfremde es zu x zwischen 1 und x gibt. Teilerfremd heißt einfach gesagt, wenn die zwei Zahlen in einem Bruch als Nenner und Zähler vorkommen, nicht mehr kürzbar sind.

zB: 1/3 --> hier kann man nicht weiter kürzen, dh sie sind teilerfremd, da sie keinen gemeinsamen "kürzer" (teiler) mehr haben.

genauso wie: 3/8, 12/17, 5/2 etc ... Diese Zahlen haben einen ggT = 1.

Wenn du jetzt phi(6) berechnen willst, schaust du dir die Zahlen von 1-5 an:

size_t count = 0;
1/6 -> Teilerfremd ++count;
2/6 -> BIEP (Teiler 2 möglich)
3/6 -> BIEP (Teiler 3 möglich)
4/6 -> BIEP (Teiler 2 möglich)
5/6 -> Teilerfremd ++count;

count = 2!

Das heißt phi(6) ist gleich 2. Und jetzt noch was interessantes. phi(primzahl) ist immer primzahl-1. Denn ne Primzahl hat -wie üblich- keinen Teiler, daher sind alle Zahlen kleiner x (=prim) Teilerfemd zu x.

Beispiel phi(5):
1/6 -> Teilerfremd ++count;
2/6 -> Teilerfremd ++count;
3/6 -> Teilerfremd ++count;
4/6 -> Teilerfremd ++count;

phi(5) = 4, genauso wie phi(3) = 2, phi(17) = 16 usw.
Und jetzt noch was schönes. Laut einem tollen Satz der Mathematik lassen sich alle Zahlen in Primfaktoren zerlegen. zB 9 = 3*3 oder 15 = 5*3.
Das kannst du auch bei der Berechnung von phi() benutzen, denn es gilt:

phi(a*b) = phi(a) * phi(b)

Achtung, gilt aber nur für a,b = prim und a!=b (s.u.). Also phi(80) != phi(10) * phi(8), eher phi(80) = phi(2*2*2*2*5). Und hier kommt direkt noch die nächste Regel ins Spiel.

phi(2*2*2*2*5) = phi(2^4) * phi(5) .. Sobald ne Primpotenz in phi auftauch, also zb phi(2*2) = phi(2^2) gilt

phi(p^k) = p^k - p^(k-1)

Also zurück zur 80:
phi(80) = phi(2^4 * 5) = phi(2^4) * phi(5) = [2^4 - 2^(4-1)] * 4 = 32

All dies wird auch ganz schön bei RSA ausgenutzt. Nochmal alls summengefasst:

phi(x) = Anzahl aller Teilerfremden zu x, zwischen 1 und x

phi(prim) = prim-1
phi(primA*primB) = (primA-1)*(primB-1)
phi(prim^k) = prim^k - prim^(k-1)

Sqwan schrieb:

Offentlich krieg ich das bis montag morgen noch raus...

Ohhhh!

SeppJ

KasF schrieb:

Sqwan schrieb:

Offentlich krieg ich das bis montag morgen noch raus...

Ohhhh!

Die Klausur müsste ja nun zu Ende sein.
@Sqwan: Wie war's? Gut modulo gerechnet und schön Summen vereinfacht?

Sqwan

naja... war so ne sache ^^
(2^501 + 37) mod 4 galt es zu berechnen.

Da ioch phi nicht berechnen konnte habe ich acuh das raus erstmal (2^501 mod 4 + 37 mod 4) gemacht.
Daraus dann 2¹⁰10^5 mod 4 * 2^1 mod4 + 37 mod 4 wo dann ein rest von 3 bei raus kam.
Obs richtig ist weiß ich noch nicht.

Summen habe ich auch schön "versucht" zu vereinfachen, ist aber wohl falsch denke ich.

$\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})$

summe dann rein gezogen...

$\frac{202}{\sum_{k=1}^{201}(k)+404} - \frac{202}{\sum_{k=4}^{204}(k)-404}$

ergebnis sollte -401 sein, war aber es bei mir aber nicht...
Also ein Fehler beim verwenden der summe...

Jester

(2^501+37) mod 4 = 2^501 mod 4 + 37 mod 4 = 4*2^499 mod 4 + 1 = 1

Jester

Sqwan schrieb:

$\sum_{k=1}^{201}(\frac{1}{k+2}) - \sum_{k=4}^{204}(\frac{1}{k-2})$

summe dann rein gezogen...

$\frac{202}{\sum_{k=1}^{201}(k)+404} - \frac{202}{\sum_{k=4}^{204}(k)-404}$

aua, denkst Du auch dass 1/2 + 1/2 zusammen 1/4 ergibt?

edit: Ah, Du hast oben auch erweitert... dann hast du einfach nur erweitert und das Summenzeichen unterwegs verloren...

In der zweiten Summe einfach k durch k+4 ersetzen. Dann lässt die sich umschreiben als $$\sum_{k=0}^{200} \frac{1}{k+2}$. Danach kann man prima sehen, dass genau 1/203 - 1/2 übrig bleibt. Alle weiteren Terme sind in beiden Summanden enthalten und heben sich daher auf.