Difference between revisions of "2012 AIME I Problems/Problem 15"
IMOJonathan (talk | contribs) (→Solution) |
IMOJonathan (talk | contribs) (→Solution) |
||
Line 22: | Line 22: | ||
− | Note: another way to find that <math>(a-1)</math> and <math>(a+1)</math> have to be relative prime to <math>n</math> is the following: start with <math>ap-aq \not \equiv \pm(p-q) \pmod n</math>. Then, we can divide by <math>p-q</math> to get <math>a \not \equiv \pm 1</math> modulo <math>\frac{n}{\gcd(n, p-q)</math>. Since <math>\gcd(n, p-q)</math> ranges through all the divisors of <math>n</math>, we get that <math>a \not \equiv \pm 1</math> modulo the divisors of <math>n</math> or <math>\gcd(a-1, n) = \gcd(a+1, n) = 1</math>. | + | Note: another way to find that <math>(a-1)</math> and <math>(a+1)</math> have to be relative prime to <math>n</math> is the following: start with <math>ap-aq \not \equiv \pm(p-q) \pmod n</math>. Then, we can divide by <math>p-q</math> to get <math>a \not \equiv \pm 1</math> modulo <math>\frac{n}{\gcd(n, p-q)}</math>. Since <math>\gcd(n, p-q)</math> ranges through all the divisors of <math>n</math>, we get that <math>a \not \equiv \pm 1</math> modulo the divisors of <math>n</math> or <math>\gcd(a-1, n) = \gcd(a+1, n) = 1</math>. |
== See also == | == See also == | ||
{{AIME box|year=2012|n=I|num-b=14|after=Last Problem}} | {{AIME box|year=2012|n=I|num-b=14|after=Last Problem}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 01:03, 12 December 2016
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
-
(






-
(

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
and
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
Note: another way to find that and
have to be relative prime to
is the following: start with
. Then, we can divide by
to get
modulo
. Since
ranges through all the divisors of
, we get that
modulo the divisors of
or
.
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.