2012 AIME I Problems/Problem 15
Problem 15
There are mathematicians seated around a circular table with
seats numbered
in clockwise order. After a break they again sit around the table. The mathematicians note that there is a positive integer
such that
-
(
![$1$](http://latex.artofproblemsolving.com/d/c/e/dce34f4dfb2406144304ad0d6106c5382ddd1446.png)
![$k,$](http://latex.artofproblemsolving.com/c/9/9/c99a6aaebc17474bd09ea71d84d4e769a0662b55.png)
![$k$](http://latex.artofproblemsolving.com/8/c/3/8c325612684d41304b9751c175df7bcc0f61f64f.png)
![$ka$](http://latex.artofproblemsolving.com/4/0/8/408730e185e0b41fcc93fd334b48e79f1c8e799d.png)
![$i + n$](http://latex.artofproblemsolving.com/d/4/9/d49c43f56bface4f34de7ad1d3e6a46a70fc1b63.png)
![$i$](http://latex.artofproblemsolving.com/3/4/8/34857b3ba74ce5cd8607f3ebd23e9015908ada71.png)
-
(
![$2$](http://latex.artofproblemsolving.com/4/1/c/41c544263a265ff15498ee45f7392c5f86c6d151.png)
Find the number of possible values of with
Solution
It is a well-known fact that the set forms a complete set of residues if and only if
is relatively prime to
.
Thus, we have is relatively prime to
. In addition, for any seats
and
, we must have
not be equivalent to either
or
modulo
to satisfy our conditions. These simplify to $(a-1)p \nequiv (a-1)q$ (Error compiling LaTeX. Unknown error_msg) and $(a+1)p \nequiv (a+1)q$ (Error compiling LaTeX. Unknown error_msg) modulo
, so multiplication by both
and
must form a complete set of residues mod
as well.
Thus, we have ,
, and
are relatively prime to
. We must find all
for which such an
exists.
obviously cannot be a multiple of
or
, but for any other
, we can set
, and then
and
. All three of these will be relatively prime to
, since two numbers
and
are relatively prime if and only if
is relatively prime to
. In this case,
,
, and
are all relatively prime to
, so
works.
Now we simply count all that are not multiples of
or
, which is easy using inclusion-exclusion. We get a final answer of
See also
2012 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 14 |
Followed by Last Problem | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.