USAMO #2 2004

[zefuri]

Suppose [unparseable or potentially dangerous latex formula], [unparseable or potentially dangerous latex formula] are integers whose greatest common divisor is [unparseable or potentially dangerous latex formula]. Let [unparseable or potentially dangerous latex formula] be a set of integers with the following properties:

(a) For [unparseable or potentially dangerous latex formula].
(b) For [unparseable or potentially dangerous latex formula] (not necessarily distinct), [unparseable or potentially dangerous latex formula]
(c) For any integers [unparseable or potentially dangerous latex formula], if [unparseable or potentially dangerous latex formula], then [unparseable or potentially dangerous latex formula]

Prove that [unparseable or potentially dangerous latex formula] must be equal to the set of all integers.

[zefuri]

We shall attempt to show
If [unparseable or potentially dangerous latex formula], we can find [unparseable or potentially dangerous latex formula] where [unparseable or potentially dangerous latex formula]

We let
[unparseable or potentially dangerous latex formula].

Thus, by condition 2,
[unparseable or potentially dangerous latex formula]

Hence, using condition 3, we can obtain the following:
[unparseable or potentially dangerous latex formula]

By condition 2, we can find:
[unparseable or potentially dangerous latex formula]

Therefore we can continue using condition 2 to find all [unparseable or potentially dangerous latex formula].

It remains to be shown that [unparseable or potentially dangerous latex formula]

Since [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] are relatively prime, we can use a well-known theorem which state if a and b are positive integers that [unparseable or potentially dangerous latex formula] for some integer [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula].

Consequently,
[unparseable or potentially dangerous latex formula]

Since, we can use our previous proof to prove [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] We can prove [unparseable or potentially dangerous latex formula]

Therefore, we can prove S must be equal to the set of all integers.

[stupidityismygam]

edit: ok...i cant read

[zefuri]

there needs to be a hide button? MISTA POTTA

[zefuri]

oh whoops instead of using that theorem i need to use the corollary of that theorem
[unparseable or potentially dangerous latex formula]

because it is not known that the gcd of any pair [unparseable or potentially dangerous latex formula] are relatively prime.

[makashi]

zefuri, you're probably aware that the theorem regarding the existence of integers [unparseable or potentially dangerous latex formula] and [unparseable or potentially dangerous latex formula] such that [unparseable or potentially dangerous latex formula] is a corollary of Euclid's Algorithm, so you might as well state it. Your proof that [unparseable or potentially dangerous latex formula] looks a lot like smoke and mirrors and in general, it's not a good idea to trivialize problems on the USAMO, so it's better to describe the process used to determine that indeed [unparseable or potentially dangerous latex formula].

stupidityismygam, your claim that there exists some [unparseable or potentially dangerous latex formula] is not true. For example, we could just have [unparseable or potentially dangerous latex formula]. I'm not sure how your argument about [unparseable or potentially dangerous latex formula] works.

[zefuri]

okay thanks!

[stupidityismygam]

[makashi]

No. The elements of the set [unparseable or potentially dangerous latex formula] are not [unparseable or potentially dangerous latex formula]. In the above example, [unparseable or potentially dangerous latex formula] does not exist.

[stupidityismygam]

ah...

i read the problem wrong...

sorry my bad :'(

[zefuri]

yeah i should probably have been more clear about that problem...but latex kinda made me speed up my work cuz i dont like latex