Kongruensräkning med bas 5

Jag kommer inte vidare i uträkningen av frågan: Bestäm resten då 5¹⁸⁹ delas med 8.

Tänker att regeln a^m $\equiv$(a')^m bör användas, men när jag försöker göra om basen i uttrycket till något annat blir det ju bara nåt som också ger resten 5.

5¹⁸⁹ = (5³)⁶³ => 5¹⁸⁹ $\equiv$ (125)⁶³ (mod 8)

125 / 8 = 15 rest 5 

5¹⁸⁹ = (5⁷)²⁷ => 5¹⁸⁹ $\equiv$78125²⁷ (mod 8)

78125/8 = 9765 rest 5

Jag tror jag inte fattat principen helt än. Det blir ju olika rester för olika n i 5ⁿ, men eftersom 189 bara är delbart med 3 och 7, och då, när jag bryter ut de talen ur exponenten som ovan, det ändå bara blir rest 5, så får jag väl aldrig fram ett tal jag kan byta exponenten till som ger en rest annan än 5 (som det görs i exemplen på den här sidan).

Varför byter man ens bas från början?