# Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 5"

m |
|||

Line 1: | Line 1: | ||

− | Let <math>p</math> be a prime and <math>f(n)</math> satisfy <math>0\le f(n) <p</math> for all | + | ==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 8: | Line 17: | ||

==Solution== | ==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>. | ||

---- | ---- | ||

Line 17: | Line 30: | ||

*[[Mock AIME 1 2006-2007]] | *[[Mock AIME 1 2006-2007]] | ||

+ | |||

+ | [[Category:Intermediate Number Theory Problems]] |

## Revision as of 12:18, 20 January 2007

## 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 .