reszta z dzielenia artur: Znajdź resztę z dzielenia liczby całkowitej a przez 73 wiedząc, że a¹⁰⁰ == 2 (mod 73) oraz a¹⁰¹ == 69 (mod 73).

sushi_ gg6397228: przemnoz pierwsze przez a

Vax: Ewentualnie tak, oczywiście (a,73) > 1, więc z twierdzenia Eulera a⁷² == 1 (mod 73) ⇒ a⁵⁰⁴ == 1 (mod 73) czyli a⁵⁰⁵ == a (mod 73), ale a¹⁰¹ == 69 (mod 73) /⁵ ⇒ a⁵⁰⁵ == 69⁵ == (−4)⁵ == 71 (mod 73) czyli a == 71 (mod 73). Warto zauważyć, że nie skorzystaliśmy z 1 założenia.