Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 5"
m |
|||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
− | + | ==Modified Problem== | |
+ | For a [[prime number]] <math>p</math>, define the [[function]] <math>f_p(n)</math> as follows: | ||
+ | If there exists <math>y</math>, <math>0 \leq y < p</math>, such that | ||
+ | |||
+ | <math> ny-p\left\lfloor \frac{ny}{p}\right\rfloor=1 </math> | ||
+ | |||
+ | set <math>f_p(n) = y</math>. Otherwise, set <math>f_p(n) = 0</math>. Compute the sum <math>f_{11}(1) + f_{11}(2) + \ldots + f_{11}(120) + f_{11}(121)</math>. | ||
+ | |||
+ | ==Original Problem== | ||
+ | Let <math>p</math> be a prime and <math>f(n)</math> satisfy <math>0\le f(n) <p</math> for all [[integer]]s <math>n</math>. <math>\lfloor x\rfloor</math> is the [[floor function | greatest integer less than or equal to]] <math>x</math>. If for fixed <math>n</math>, there exists an integer <math>0\le y < p</math> such that: | ||
Line 6: | Line 15: | ||
then <math>f(n)=y</math>. If there is no such <math>y</math>, then <math>f(n)=0</math>. If <math>p=11</math>, find the sum: <math>f(1)+f(2)+...+f(p^{2}-1)+f(p^{2})</math>. | then <math>f(n)=y</math>. If there is no such <math>y</math>, then <math>f(n)=0</math>. If <math>p=11</math>, find the sum: <math>f(1)+f(2)+...+f(p^{2}-1)+f(p^{2})</math>. | ||
+ | |||
+ | ==Solution== | ||
+ | The definition of <math>f_p</math> is equivalent to the following: "If <math>n</math> has a multiplicative [[inverse with respect to an operation | inverse]] [[mod]] <math>p</math>, <math>f_p(n)</math> is the member of the [[set]] <math>\{0, 1, \ldots, p - 1\}</math> such that <math>n \cdot f_p(n) \equiv 1 \pmod p</math>. Otherwise, <math>f_p(n) = 0</math>." | ||
+ | |||
+ | Note that this really gives a well-defined function because that set includes exactly one member from each [[congruence class]] modulo <math>p</math>, and each invertible element has inverses in only one such class. | ||
+ | |||
+ | From this point onwards, it's clear: as <math>n</math> cycles through <math>1, 2, \ldots, 10 \pmod{11}</math>, <math>f_p(n)</math> also cycles through the same values in some order. We cover those values 11 times. Thus the answer is <math>11 \cdot (1 + 2 + \ldots + 10) = 605</math>. | ||
+ | |||
+ | ---- | ||
+ | |||
+ | *[[Mock AIME 1 2006-2007 Problems/Problem 4 | Previous Problem]] | ||
+ | |||
+ | *[[Mock AIME 1 2006-2007 Problems/Problem 6 | Next Problem]] | ||
+ | |||
+ | *[[Mock AIME 1 2006-2007]] | ||
+ | |||
+ | [[Category:Intermediate Number Theory Problems]] |
Latest revision as of 15:52, 3 April 2012
Modified Problem
For a prime number , define the function
as follows:
If there exists
,
, such that
set . Otherwise, set
. Compute the sum
.
Original Problem
Let be a prime and
satisfy
for all integers
.
is the greatest integer less than or equal to
. If for fixed
, there exists an integer
such that:
then . If there is no such
, then
. If
, find the sum:
.
Solution
The definition of is equivalent to the following: "If
has a multiplicative inverse mod
,
is the member of the set
such that
. Otherwise,
."
Note that this really gives a well-defined function because that set includes exactly one member from each congruence class modulo , and each invertible element has inverses in only one such class.
From this point onwards, it's clear: as cycles through
,
also cycles through the same values in some order. We cover those values 11 times. Thus the answer is
.