Page 1 of 1
USAMO #2 2004
Posted:
Thu Apr 12, 2007 8:54 pm
by 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.
Posted:
Thu Apr 12, 2007 9:42 pm
by 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.
Posted:
Thu Apr 12, 2007 9:51 pm
by stupidityismygam
edit: ok...i cant read
Posted:
Thu Apr 12, 2007 10:28 pm
by zefuri
there needs to be a hide button? MISTA POTTA
Posted:
Fri Apr 13, 2007 6:16 pm
by 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.
Posted:
Sat Apr 14, 2007 12:48 pm
by 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.
Posted:
Sat Apr 14, 2007 4:37 pm
by zefuri
okay thanks!
Posted:
Sat Apr 14, 2007 10:43 pm
by stupidityismygam
Posted:
Sat Apr 14, 2007 11:00 pm
by 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.
Posted:
Sat Apr 14, 2007 11:35 pm
by stupidityismygam
ah...
i read the problem wrong...
sorry my bad :'(
Posted:
Sun Apr 15, 2007 10:44 am
by 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