Difference between revisions of "2008 iTest Problems/Problem 60"
Rockmanex3 (talk | contribs) (Solution to Problem 60 (credit to official solution) -- Harmonic Triangle) |
m |
||
Line 42: | Line 42: | ||
<br> | <br> | ||
From the two pieces of information, we find that the remainder when <math>S</math> is divided by <math>2008</math> is <math>\boxed{1944}.</math> | From the two pieces of information, we find that the remainder when <math>S</math> is divided by <math>2008</math> is <math>\boxed{1944}.</math> | ||
− | + | ===Note=== | |
+ | The triangle in this problem is called [https://en.wikipedia.org/wiki/Leibniz_harmonic_triangle Lebiniz's Harmonic Triangle] | ||
==See Also== | ==See Also== | ||
{{2008 iTest box|num-b=59|num-a=61}} | {{2008 iTest box|num-b=59|num-a=61}} |
Latest revision as of 00:29, 2 November 2023
Contents
[hide]Problem
Consider the Harmonic Table
where and
.
Find the remainder when the sum of the reciprocals of the terms on the
row gets divided by
.
Solution
Notice that all the denominators have a common factor. If we factor the GCD of the few rows, the denominators seem to replicate the terms of Pascal's Triangle.
We claim that Plugging
results in
Now we need to show that
if
If then
That means
Thus, We can use this to find the sum of the
terms in the
row. Let
be the wanted sum.
Finally, to find the remainder when is divided by
we need to use modular arithmetic. First, note that
so we can use the remainder when
is divided by
and
to help us find the remainder when
is divided by
.
The remainder when is divided by
is
because the exponent of
in
is way over
By Fermat's Little Theorem, we know that
and since
is relatively prime to
Thus,
so the remainder when
is divided by
is
From the two pieces of information, we find that the remainder when is divided by
is
Note
The triangle in this problem is called Lebiniz's Harmonic Triangle
See Also
2008 iTest (Problems) | ||
Preceded by: Problem 59 |
Followed by: Problem 61 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • 61 • 62 • 63 • 64 • 65 • 66 • 67 • 68 • 69 • 70 • 71 • 72 • 73 • 74 • 75 • 76 • 77 • 78 • 79 • 80 • 81 • 82 • 83 • 84 • 85 • 86 • 87 • 88 • 89 • 90 • 91 • 92 • 93 • 94 • 95 • 96 • 97 • 98 • 99 • 100 |