# Congruence, finding remainder

• May 7th 2009, 05:41 AM
knarQ
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?
• May 7th 2009, 06:49 AM
TheEmptySet
Quote:

Originally Posted by knarQ
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?

Fermat little theorem says

$a^{p} \equiv a \mod(p)$
so in your case you get

$2004^{41}=2004\mod(41)$

From here jut divide 2004 by 41 to find the remainder.
• May 7th 2009, 07:29 AM
fardeen_gen
In the second, Fermat gives $2004^{60}\equiv 1\bmod 61$. How can you use this to rewrite or break down that large exponent?
Hint: Use the rule $(a^{b})^{c}=a^{bc}$.
• May 7th 2009, 11:28 AM
knarQ
It feels good that I was on the right track. :)

$2004^{6000}=(2004^{100})^{60}$

By Fermat any number that is coprime with 61 and raised to 60 leaves remainder 1 when divided by 61, so my r2 probably is just... 1. Does this make sense?

$(2004^{100})^{60}\equiv 1\bmod 61$
• May 7th 2009, 03:42 PM
TheAbstractionist
Quote:

Originally Posted by knarQ
Does this make sense?

$(2004^{100})^{60}\equiv 1\bmod 61$

Hi knarQ.

Almost. Write it as $\left(2004^{60}\right)^{100}\equiv1\pmod{61}$ instead.