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"

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 integers <math>n</math>. <math>\lfloor x\rfloor</math> is the 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:
+
==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==
−
{{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 11:18, 20 January 2007

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=12243"