Wyznaczenie reszt z dzielenia Maciek: Witam, W jaki sposób mogę wyliczyć wszystkie możliwe reszty z dzielenia aⁿ mod b, gdzie a i b znamy? Przykładowo 3ⁿ mod 7. Chodzi mi o sposób inny niż obliczanie "brute forcem", które działało by przy liczach a w graniach od 1 do 500.

Artur z miasta Neptuna: Jezeli a i b sa wzglednie pierwsze to istnieje taka liczba k ze a^k mod b = 1 lub −1. Pozostaje wiec jedynie wyliczenie minimalnej liczby k i w ten sposob mocno upraszczasz obliczenia reszty. W twoim przypadku masz 3³ mod 7 = 3² * 3 mod7 = 2*3 mod 7 = −1 a co za tym idzie 3⁶ mod7=1

Artur z miasta Neptuna: Jezeli zadanie polega na wyliczeniu WSZYSTKICH mozliwych reszt dla nieograniczonego n to wystarczy sprawdzic jaki jest NWD(a,b) jezeli sa to liczby wzglednie pierwsze to reszty sa w ciele Z_b jezeli NWD(a,b) = c > 1 to przyjmuje reszty postaci k*c takie ze 0≤k*c<b

Artur_z_miasta_Neptuna: oczywiście źle napisałem ... wzglednie pierwsze to reszty NIE są w ciele Z_b bo nie ma reszty 0

Maciek: PS: Chodzi mi o WSZYSKIE możlwie reszty z dzielenia. Możesz mi to opisać dokładniej?