Wednesday, November 16, 2005

Modular Math. Topic: Number Theory. Level: AMC/AIME.

Problem: What is the remainder when you divide $6^{2005}+8^{2005}$ by $49$?

Solution Modular arithmetic is a useful tool for this problem. The concept is really quite simple:

We state that $a \equiv b \pmod{c} \Rightarrow c|(a-b)$,

that is, $a$ and $b$ leave the same remainder upon division by $c$.

We rewrite the problem as evaluating $6^{2005}+8^{2005} \pmod{49}$.

The key to this problem is noticing that $6 = 7-1$ and $8 = 7+1$. Rewrite them as such:

$(7-1)^{2005}+(7+1)^{2005}$.

Applying our handy Binomial Theorem, we see that

$\displaystyle (7-1)^{2005} = (2005C0)(7^{2005}) - (2005C1)(7^{2004}) + \ldots +(2005C2004)(7)-(2005C2005)$.

Consider this $\pmod{49}$ or $\pmod{7^2}$. We note that any term with a power of $7$ greater than or equal to $2$ is $0 \pmod{49}$ (make sure you get this, review the definition of mod if you don't). Thus the only terms that we need to consider are the last two: $\displaystyle (2005C2004)(7)-(2005C2005) = 2005(7)-1$.

Similarly, the only two terms of $(7+1)^{2005}$ we need to consider are $\displaystyle (2005C2004)(7)+(2005C2005) = 2005(7)+1$.

Summing the two, we have $(2005(7)-1)+(2005(7)-1) = 4010(7) \equiv 42 \pmod{49}$ (you can work out the details yourself). Hence our answer is $42$. QED.

--------------------

Comment: Modular arithmetic has extremely wide applications in Number Theory, including a number of important theorems you should be familiar with (e.g. Fermat's Little Theorem). Learning this concept will increase your ability to solve NT problems dramatically. If you just love Number Theory and want to learn more about it, check out the PROMYS website; it's a summer camp devoted entirely to NT.

--------------------

Practice Problem: Find the remainder when $1+10+10^2+\ldots+10^{2005}$ is divided by $9$.

7 comments:

  1. We can rewrite as (1+10^1+ 10^2 + ..... 10^8)(10^1997+10^1988+.....+10^(9n+8).....10^8)+ 1+ 10^1+ 10^2.......10^7
    (1+10^1+ 10^2 + ..... 10^8) is divisble by 9 and (1+ 10^1+ 10^2.......10^7) is divisible by 8. So the remainder is 8.

    Jeffrey, how do I Latex this up?

    Once again, your blog is the best I've seen! Thanks for the problems.

    ReplyDelete
  2. Your answer is correct. I'm not sure how to get LaTeX into comments though... I'll see what I can do.

    ReplyDelete
  3. o.o Wasteful solution. It took me way too long to understand what you were doing without LaTeX.

    Sol'n #1: Take the expression mod 9 directly. 10 mod 9 = 1, so the answer is 2005 mod 9, and since 1997 = 999*3 is divisible by 9, the answer is 8.

    Sol'n #2 Consider the expression as 2006 1's strung together, and apply the divisibility test by 9 twice: 111...111... -> 2006 -> 8. (Shortcut to solution #1)

    ReplyDelete
  4. But I like my solution....its beautiful. :-)

    ReplyDelete
  5. Qiaochu, stop being so negative. Lol.

    ReplyDelete
  6. * 2006 mod 9, 1998 = 999*2. Whoops. Mistyped XD

    I admit the solution's elegant...

    ReplyDelete
  7. me: cheerio what do you want to stay?
    cheerio: >

    ReplyDelete