Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 1 2006-2007 Problems/Problem 5"
(No difference)

Revision as of 14:48, 3 April 2012

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_2006-2007_Problems/Problem_5&oldid=45965"