Problem: (2006-2007 Warm-Up 5 - #13) Determine the units digit in the decimal expansion of $ (20+\sqrt{397})^{2674} $.
Solution: Well, in its current form it is quite an ugly expression, with half of the terms involving a radical. Maybe we can simplify this, a.k.a. get rid of the radicals. Consider
$ (20+\sqrt{397})^{2674}+(20-\sqrt{397})^{2674} $.
Since we know $ 20-\sqrt{397} < 1 $, then $ (20-\sqrt{397})^{2674} \rightarrow 0 $ (it's really small). The above expression is an integer because all of the radical terms cancel out. So if we find the units digit of this, we simply subtract one away and get the units digit of our original number. But this number is just
$ 2(20^{2674}+\cdots+397^{1337}) $,
where every term in between is divisible by $ 20 $. That means they all have a units digit of zero, so we only need to look at the last term. Since powers of $ 7 $ repeat the sequence
$ 7, 9, 3, 1 \pmod{10} $,
we know $ 397^{1337} \equiv 7^{1337} \equiv 7 \pmod{10} $. So twice of this would give a units digit of $ 4 $. Subtracting one away as we mentioned above gives us a units digit of $ 3 $. QED.
--------------------
Comment: This is an excellent application of the binomial theorem and a good test of your intuition, which basically consisted of noticing $ 20^2 \approx 397 $. The power $ 2674 $ was an arbitrary even number; in fact, for smaller powers we notice the exact same thing:
$ (20+\sqrt{397})^2 \approx 1593.99 $.
--------------------
Practice Problem: Determine how many elements of the $ n $th row of Pascal's Triangle are odd.
Probably the best question on today's warmup, too bad I didn't really cover anything like that XD
ReplyDeleteAnyway, I saw a solution by Lucas' Theorem but I'll go slightly more basic and use the lemma behind it instead:
Lemma: (a + b)^p = a^p + b^p mod p
Easy to prove. With this lemma, let n = 2^{e_1} + 2^{e_2}+ ... + 2^{e_d}(its binary expansion). Then
(x + 1)^n = (x^{2^{e_1}} + 1)(x^{2^{e_2}} + 1)...(x^{2^{e_d}} + 1) mod 2
If this form is expanded every coefficient will be 1 because of unique represention base 2 so there'll be 2^d odd coefficients, where d is the number of nonzero binary digits in n.
BY THE WAY HARD QUESTION I COULDN'T DO:
ReplyDeleteInstead of (x + 1)^n find the number of odd coefficients in (x^2 + x + 1)^n
=(