Mock AIME 1 2006-2007 Problems/Problem 5

Modified Problem

For a prime number $p$ , define the function $f_p(n)$ as follows: If there exists $y$ , $0 \leq y < p$ , such that

$ny-p\left\lfloor \frac{ny}{p}\right\rfloor=1$

set $f_p(n) = y$ . Otherwise, set $f_p(n) = 0$ . Compute the sum $f_{11}(1) + f_{11}(2) + \ldots + f_{11}(120) + f_{11}(121)$ .

Original Problem

Let $p$ be a prime and $f(n)$ satisfy $0\le f(n) <p$ for all integers $n$ . $\lfloor x\rfloor$ is the greatest integer less than or equal to $x$ . If for fixed $n$ , there exists an integer $0\le y < p$ such that:

$ny-p\left\lfloor \frac{ny}{p}\right\rfloor=1$

then $f(n)=y$ . If there is no such $y$ , then $f(n)=0$ . If $p=11$ , find the sum: $f(1)+f(2)+...+f(p^{2}-1)+f(p^{2})$ .

Solution

The definition of $f_p$ is equivalent to the following: "If $n$ has a multiplicative inverse mod $p$ , $f_p(n)$ is the member of the set $\{0, 1, \ldots, p - 1\}$ such that $n \cdot f_p(n) \equiv 1 \pmod p$ . Otherwise, $f_p(n) = 0$ ."

Note that this really gives a well-defined function because that set includes exactly one member from each congruence class modulo $p$ , and each invertible element has inverses in only one such class.

From this point onwards, it's clear: as $n$ cycles through $1, 2, \ldots, 10 \pmod{11}$ , $f_p(n)$ also cycles through the same values in some order. We cover those values 11 times. Thus the answer is $11 \cdot (1 + 2 + \ldots + 10) = 605$ .

Previous Problem

Next Problem

Mock AIME 1 2006-2007

Page

Toolbox

Search

Mock AIME 1 2006-2007 Problems/Problem 5

Modified Problem

Original Problem

Solution