# Thread: Congruence, finding remainder

1. ## Congruence, finding remainder

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

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?

2. Originally Posted by knarQ
I'm fairily new to this discrete maths thing and I'm stuck on a problem that seems quite simple:

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

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

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

From here jut divide 2004 by 41 to find the remainder.

3. In the second, Fermat gives $\displaystyle 2004^{60}\equiv 1\bmod 61$. How can you use this to rewrite or break down that large exponent?
Hint: Use the rule $\displaystyle (a^{b})^{c}=a^{bc}$.

4. It feels good that I was on the right track.

$\displaystyle 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?

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

5. Originally Posted by knarQ
Does this make sense?

$\displaystyle (2004^{100})^{60}\equiv 1\bmod 61$
Hi knarQ.

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