Obliczanie przy wykorzystaniu twierdzenia Fermata.

[Spens13]

Witam, otóż mam za zadanie obliczyć następujący przykład przy wykorzystaniu twierdzenia Fermata:
\(\displaystyle{ a=7^{1843}\pmod{9}}\)

Wiem, że \(\displaystyle{ a^{p-1}=1\pmod{p}}\), ale za bardzo nie wiem jak to mogę wykorzystać przez to, że za \(\displaystyle{ 7^{1843}}\) mam jeszcze \(\displaystyle{ \pmod{9}}\).

Proszę o pomoc :/

@edit
Dodatkowo w wykładzie pojawia się taki wzór (który też mi nic nie mówi):
\(\displaystyle{ a^{\phi(n)}\pmod{n}=1}\)

[Ponewor]

Dla liczb złożonych musisz obliczyć wartość funkcji \(\displaystyle{ \phi\left(n\right)}\) czyli funkcji Eulera, a potem podnieść kongruencję do możliwie wysokiej potęgi.