What is the remainder when $3^{2002}+7^{2002}+2002$ is divided by 29?

[Saitama]

Problem:

When $3^{2002}+7^{2002}+2002$ is divided by 29, the remainder is:

A)0
B)1
C)2
D)7

Attempt:
I tried the following:

$3^3 \equiv -2\mod 29$ i.e $3^{2002} \equiv 3\cdot 3^{2001} \equiv -3\cdot 2^{667} \mod 29$

Also, $2^5 \equiv 3 \mod 29$, hence, $-3\cdot 2^{667} \equiv -3\cdot 2^2\cdot 3^{133} \mod 29$

But this is becoming too long, I can continue with $3^3 \equiv -2\mod 29$ again but this is time consuming. I assume there exists a better method because 29 is a prime number.

Any help is appreciated. Thanks!

 

[I like Serena]

Problem:

When $3^{2002}+7^{2002}+2002$ is divided by 29, the remainder is:

A)0
B)1
C)2
D)7

Attempt:
I tried the following:

$3^3 \equiv -2\mod 29$ i.e $3^{2002} \equiv 3\cdot 3^{2001} \equiv -3\cdot 2^{667} \mod 29$

Also, $2^5 \equiv 3 \mod 29$, hence, $-3\cdot 2^{667} \equiv -3\cdot 2^2\cdot 3^{133} \mod 29$

But this is becoming too long, I can continue with $3^3 \equiv -2\mod 29$ again but this is time consuming. I assume there exists a better method because 29 is a prime number.

Any help is appreciated. Thanks!

Hey Pranav! :)

Hint: use Fermat's little theorem (or Euler's theorem) saying that any number $a$ that has no factor in common with the prime 29 has $a^{29-1} \equiv 1 \pmod{29}$.

 

[Saitama]

Hi ILS! :D

Hint: use Fermat's little theorem (or Euler's theorem) saying that any number $a$ that has no factor in common with the prime 29 has $a^{29-1} \equiv 1 \pmod{29}$.

I have heard of FLT before but I am unable to apply it.

According to FLT, $3^{28} \equiv 1\mod 29$. Okay, after a bit of calculation, I found that
$$3^{2002}\equiv 3^{14} \mod 29$$
but this would still be time consuming. I think I am applying FLT the wrong way.

 

[I like Serena]

Hi ILS! :D
I have heard of FLT before but I am unable to apply it.

According to FLT, $3^{28} \equiv 1\mod 29$. Okay, after a bit of calculation, I found that
$$3^{2002}\equiv 3^{14} \mod 29$$
but this would still be time consuming. I think I am applying FLT the wrong way.

That's fine! ;)

Continue with squaring or something like that:
$$3^{14} \equiv 9^{7} \equiv (9^2)^3\cdot 9 \equiv 81^3\cdot 9 \equiv (-6)^3 \cdot 9 \pmod{29}$$
And so on...

 

[Saitama]

That's fine! ;)

Continue with squaring or something like that:
$$3^{14} \equiv 9^{7} \equiv (9^2)^3\cdot 9 \equiv 81^3\cdot 9 \equiv (-6)^3 \cdot 9 \pmod{29}$$
And so on...

Ah, it would still take some time, but thanks ILS! :)

Can you think of some trick for this problem, maybe by using the other parts of problem statement? We have two more numbers $7^{2002}$ and $2002$ and the exponent of both 3 and 7 is same as the last number i.e 2002. I am quite new to this number theory stuff, I currently can't think of anything. :(

 

[Opalg]

This is essentially the same as ILS's suggestion. You want to find $3^{14}\pmod{29}$. My little pocket calculator gives $3^7 = 2187$ and $75\times29 = 2175$. So $3^7\equiv 12 \pmod{29}$, and $3^{14} = (3^7)^2 \equiv 12^2 = 144 \equiv -1 \pmod{29}.$ It also gives $7^7 = 823543 = 28398\times29 + 1\equiv1 \pmod{29}.$ So $7^{14} = (7^7)^2 \equiv1 \pmod{29}.$ That just leaves $2002 \pmod{29}$, which should not be too hard.

 

[Deveno]

The thing to do in this situation is start looking at powers of 3 and 7 mod 29. We have:

$3^2 = 9$
$3^3 = 27 = -2$ (sometimes it's easier to work with the negatives if they're smaller integers)
$3^4 = 21 = -6$
$3^5 = 11$
$3^6 = 4$
$3^7 = 12$
$3^8 = 7$ <---this is interesting!
$3^9 = 21 = -8$
$3^{10} = 5$
$3^{11} = 15$
$3^{12} = 16$
$3^{13} = 19 = -10$
$3^{14} = 28 = -1$

As we discovered when doing this: $7 = 3^8$, so we can write:

$3^{14} + 7^{14} = 3^{14} + 3^{112} = 3^{14} + (3^{28})^4 = 3^{14} + 1^4 = -1 + 1 = 0$.

None of these calculations required a calculator.

 

[Saitama]

The thing to do in this situation is start looking at powers of 3 and 7 mod 29. We have:

$3^2 = 9$
$3^3 = 27 = -2$ (sometimes it's easier to work with the negatives if they're smaller integers)
$3^4 = 21 = -6$
$3^5 = 11$
$3^6 = 4$
$3^7 = 12$
$3^8 = 7$ <---this is interesting!
$3^9 = 21 = -8$
$3^{10} = 5$
$3^{11} = 15$
$3^{12} = 16$
$3^{13} = 19 = -10$
$3^{14} = 28 = -1$

As we discovered when doing this: $7 = 3^8$, so we can write:

$3^{14} + 7^{14} = 3^{14} + 3^{112} = 3^{14} + (3^{28})^4 = 3^{14} + 1^4 = -1 + 1 = 0$.

None of these calculations required a calculator.

This is essentially the same as ILS's suggestion. You want to find $3^{14}\pmod{29}$. My little pocket calculator gives $3^7 = 2187$ and $75\times29 = 2175$. So $3^7\equiv 12 \pmod{29}$, and $3^{14} = (3^7)^2 \equiv 12^2 = 144 \equiv -1 \pmod{29}.$ It also gives $7^7 = 823543 = 28398\times29 + 1\equiv1 \pmod{29}.$ So $7^{14} = (7^7)^2 \equiv1 \pmod{29}.$ That just leaves $2002 \pmod{29}$, which should not be too hard.

Thanks a lot Opalg and Deveno! :)

 

[kaliprasad]

There is a short cut
$3^2 + 7^2 = 58$ = 0 mod 2

$3^{2002} + 7^{2002}= (3^2)^{1001} + (7^2)^{1001}$

sum of odd powers of 2 numbers divisible by $3^2 + 7^2$
now one can proceed