Hallo, ich hab anscheinend ein kleines Problem mit Fermat.

Wenn Zahlen a und m 'relatively prime' zueinander sind, dann teilt m a hoch Phi von m minus 1.
(siehe Anhang)


Allerdings klappt das bei mir nicht immer… Hier ein paar Ausdrucke, da Java besser rechnet als ich:
3^4 mod 10 = 1.0
10^2 mod 3 = 9.0
7^4 mod 10 = 1.0
10^6 mod 7 = 9.0
9^4 mod 10 = 1.0
10^8 mod 9 = 1.0
11^4 mod 10 = 1.0
10^10 mod 11 = 1.0
7^5 mod 12 = 7.0
12^6 mod 7 = 1.0

Kann mir einer erklären, warum das nicht immer hinhaut?
Besten Dank!

10^2 = 100 / 3 = 33 + 1/3, da brauchst du Java, um es falsch auszurechnen? ;)
wie kann man überhaupt bei Teilung durch 3 einen Rest größer 2 übrig behalten?

1.000.000 / 7 = 142857 + 1/7

phi(12) dürfte 6 sein, ist das die Anzahl der Teiler?

7^6 / 12 = 117649 / 12 = 9804 + 1/12

aha, Anzahl der teilerfremden Zahlen usw.
für 12 wären das nur die 1, 5, 7 und 11 ->

7^4 mod 12 = 1

Oha, du solltest sehen, was ich noch mit Java nicht kann :-D

Danke erstmal, das hätte mir eig. auffallen MÜSSEN.. Ich bin irg. automatisch davon ausgegangen, dass PHI(12) ja 1 mehr ist als PHI(10), weil ja 11 dazwischen ist ^^