Congruence, finding remainder

I'm fairily new to this discrete maths thing and I'm stuck on a problem that seems quite simple:

http://www.bahnhof.se/wb204729/congruence.jpg

The first problem I think can be solved by Fermat's little theorem. Since 41 is a prime, (2004^41)-2004 would probably be divisible by 41? But r1 should lie between 0 and 40, and I can't figure that part out. 2004 gives a remainder 36 when divided by 41, but then there was the power part.

I'm pretty lost on the second one, but 61 is also a prime, but the power and the divider is not the same so that rules out Fermat?