Difference between revisions of "2001 USAMO Problems/Problem 5"
(New page: == Problem == Let <math>S</math> be a set of integers (not necessarily positive) such that (a) there exist <math>a,b \in S</math> with <math>\gcd(a,b) = \gcd(a - 2,b - 2) = 1</math>; (b...) |
m (added a missing symbol) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 10: | Line 10: | ||
== Solution == | == Solution == | ||
− | {{ | + | In the solution below we use the expression <math>S</math> ''is stable under'' <math>x\mapsto f(x)</math> to mean that if <math>x</math> belongs to <math>S</math> then <math>f(x)</math> also belongs to <math>S</math>. If <math>c,d\in S</math>, then by (B), <math>S</math> is stable under <math>x\mapsto c^2 - x</math> and <math>x\mapsto d^2 - x</math>, hence stable under <math>x\mapsto c^2 - (d^2 - x) = x + (c^2 - d^2)</math>. Similarly <math>S</math> is stable under <math>x\mapsto x + (d^2 - c^2)</math>. Hence <math>S</math> is stable under <math>x\mapsto x + n</math> and <math>x\mapsto x - n</math> whenever <math>n</math> is an integer linear combination of numbers of the form <math>c^2 - d^2</math> with <math>c,d\in S</math>. In particular, this holds for <math>n = m</math>, where <math>m = \gcd\{c^2 - d^2 : c,d\in S\}</math>. |
+ | |||
+ | Since <math>S\neq \emptyset</math> by (A), it suffices to prove that <math>m = 1</math>. For the sake of contradiction, assume that <math>m\neq 1</math>. Let <math>p</math> be a prime dividing <math>m</math>. Then <math>c^2 - d^2\equiv 0\pmod{p}</math> for all <math>c,d\in S</math>. In other words, for each <math>c,d\in S</math>, either <math>d\equiv c\pmod{p}</math> or <math>d\equiv -c\pmod{p}</math>. Given <math>c\in S</math>, <math>c^2 - c\in S</math> by (B), so <math>c^2 - c\equiv c\pmod{p}</math> or <math>c^2 - c\equiv -c\pmod{p}</math>. Hence | ||
+ | <cmath>\text{For each }c\in S\text{, either }c\equiv 0\pmod{p}\text{ or }c\equiv 2\pmod{p}.\qquad\qquad (*)</cmath> | ||
+ | By (A), there exist some <math>a</math> and <math>b</math> in <math>S</math> such that <math>\gcd(a,b) = 1</math>, that is, at least one of <math>a</math> or <math>b</math> cannot be divisible by <math>p</math>. Denote such an element of <math>S</math> by <math>\alpha</math>: thus, <math>\alpha\not\equiv 0\pmod{p}</math>. Similarly, by (A), <math>\gcd(a - 2, b - 2) = 1</math>, so <math>p</math> cannot divide both <math>a - 2</math> and <math>b - 2</math>. Thus, there is an element of <math>S</math>, call it <math>\beta</math>, such that <math>\beta\not\equiv 2\pmod{p}</math>. By <math>(*)</math>, <math>\alpha\equiv 2\pmod{p}</math> and <math>\beta\equiv 0\pmod{p}</math>. By (B), <math>\beta^2 - \alpha\in S</math>. Taking <math>c = \beta^2 - \alpha</math> in <math>(*)</math> yields either <math>-2\equiv 0\pmod{p}</math> or <math>-2\equiv 2\pmod{p}</math>, so <math>p = 2</math>. Now <math>(*)</math> says that all elements of <math>S</math> are even, contradicting (A). Hence our assumption is false and <math>S</math> is the set of all integers. | ||
== See also == | == See also == | ||
Line 16: | Line 20: | ||
[[Category:Olympiad Number Theory Problems]] | [[Category:Olympiad Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 07:44, 23 October 2022
Problem
Let be a set of integers (not necessarily positive) such that
(a) there exist with
;
(b) if and
are elements of
(possibly equal), then
also belongs to
.
Prove that is the set of all integers.
Solution
In the solution below we use the expression is stable under
to mean that if
belongs to
then
also belongs to
. If
, then by (B),
is stable under
and
, hence stable under
. Similarly
is stable under
. Hence
is stable under
and
whenever
is an integer linear combination of numbers of the form
with
. In particular, this holds for
, where
.
Since by (A), it suffices to prove that
. For the sake of contradiction, assume that
. Let
be a prime dividing
. Then
for all
. In other words, for each
, either
or
. Given
,
by (B), so
or
. Hence
By (A), there exist some
and
in
such that
, that is, at least one of
or
cannot be divisible by
. Denote such an element of
by
: thus,
. Similarly, by (A),
, so
cannot divide both
and
. Thus, there is an element of
, call it
, such that
. By
,
and
. By (B),
. Taking
in
yields either
or
, so
. Now
says that all elements of
are even, contradicting (A). Hence our assumption is false and
is the set of all integers.
See also
2001 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.