2008 iTest Problems/Problem 60
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 |