Congruence, finding remainder

Printable View

May 7th 2009, 04: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, 05: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, 06: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, 10: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, 02: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.