# modular arith

• Aug 3rd 2010, 11:14 AM
sfspitfire23
modular arith
Find the remainder of $100^{11}+1$ divided by $11$

100 is equivalent to 1 (mod 11) and 1 is equivalent to -10 (mod 11).

Thus, $1^{11}+-10=-9$. But -9 is equivalent to 2 (mod 11). Thus, the remainder is 2.

Correct?
• Aug 3rd 2010, 11:44 AM
undefined
Quote:

Originally Posted by sfspitfire23
Find the remainder of $100^{11}+1$ divided by $11$

100 is equivalent to 1 (mod 11) and 1 is equivalent to -10 (mod 11).

Thus, $1^{11}+-10=-9$. But -9 is equivalent to 2 (mod 11). Thus, the remainder is 2.

Correct?

Why convert the 1 to -10? You create extra work for yourself. Just keep it as 1 + 1 = 2 :D
• Aug 3rd 2010, 12:47 PM
melese
Quote:

Originally Posted by sfspitfire23
Find the remainder of $100^{11}+1$ divided by $11$

100 is equivalent to 1 (mod 11) and 1 is equivalent to -10 (mod 11).

Thus, $1^{11}+-10=-9$. But -9 is equivalent to 2 (mod 11). Thus, the remainder is 2.

Correct?

For similar cases you could also use Fermat's Little Theorem. Since 100 and 11 are relatively prime with 11 a prime, we have $100^{10}\equiv 1(mod\ 11)$, then $100^{11}+1\equiv 100+1(mod\ 11)$ and 100 is congruent to 1 modulo 11. So $100^{11}+1\equiv 2 (mod\ 11)$.