USAMO #2 2005
Posted:
Mon Apr 16, 2007 8:45 pm
by stupidityismygam
Prove that the system
[unparseable or potentially dangerous latex formula]
[unparseable or potentially dangerous latex formula]
has no solutions in integers x, y, and z.
Posted:
Mon Apr 16, 2007 10:26 pm
by kashhustler
hmm... i don't understand why you used mod 13. what was the reasoning behind it? why not mod 7? or 11? or 3?
i tried a bunch of factoring on this problem but didn't really get anywhere...
Posted:
Mon Apr 16, 2007 10:59 pm
by NickR
Well, to go one step further, it looks like [unparseable or potentially dangerous latex formula] (I could be wrong though)
Therefore, [unparseable or potentially dangerous latex formula]
Posted:
Mon Apr 16, 2007 11:41 pm
by Kurt
Generally, you would choose mods that have low numbers of residues for a problem. Although I don't understand why you are setting up all of those extra congruences, unless you are wanting to use CRT somewhere. But for that, you'd need another mod as well...
I'd rather find congruences in one mod, and use those to solve all equations (or rather, show that there is no solution). Mod 13 will indeed work well, since it has only 5 different residues that repeat for 3rd, 6th, and 9th powers. You could choose another base if you wanted to, but it shouldn't matter ultimately since you are hoping to prove it doesn't work for any integer set.
Those residues[unparseable or potentially dangerous latex formula] are [unparseable or potentially dangerous latex formula].
Substituting these back into (1) (to use your notation, Stephen), you could solve for possible y values.
I'll use [unparseable or potentially dangerous latex formula] first:
Thus, [unparseable or potentially dangerous latex formula].
So:
[unparseable or potentially dangerous latex formula].
Which means [unparseable or potentially dangerous latex formula].
That is the only solution for y for [unparseable or potentially dangerous latex formula].
Let's now substitute those values into the other original equation (2):
[unparseable or potentially dangerous latex formula].
Which means that [unparseable or potentially dangerous latex formula]. However, 6 is not a 9th power residue [unparseable or potentially dangerous latex formula], so there are no integer solutions for this scenario.
I'm not going to go through the other cases (although in the 1.5 hours you would want to designate for this problem, this should be well more than enough), but I would think the same method would work for the other 4 cases. I chose [unparseable or potentially dangerous latex formula] first, simply because it seemed like it would be the most trustworthy test case (no convenient 1's or 0's, etc.). It would be easier for [unparseable or potentially dangerous latex formula] cases I should think.)
Posted:
Tue Apr 17, 2007 5:35 pm
by zefuri
Is there an official solution
Posted:
Tue Apr 17, 2007 5:40 pm
by stupidityismygam
anyone want to try it with like nod 7 or something and see, if it comes out nice?