|
|
| Author |
Message |
larryhammick@telus.net
science forum Guru Wannabe
Joined: 14 Feb 2006
Posts: 217
|
 Posted: Thu Mar 30, 2006 5:12 am Post subject:
nice problem from a competition
|
|
|
| Quote: | From a recent IMO team selection test in Taiwan:
|
Let x and y be positive integers and suppose
x^n + n divides y^n + n
for all positive integers n. Prove that x=y. |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Thu Mar 30, 2006 11:16 pm Post subject:
Re: nice problem from a competition
|
|
|
computer wrote:
| Quote: | "computer" <computer@computer.computer> ha scritto nel messaggio
news:442c3e60$0$36930$4fafbaef@reader3.news.tin.it...
"Christopher" <night@fas.harvard.edu> ha scritto nel messaggio
news:1143748511.231044.308480@e56g2000cwe.googlegroups.com...
computer wrote:
"Larry Hammick" <larryhammick@telus.net> ha scritto nel messaggio
Let x and y be positive integers and suppose
x^n + n divides y^n + n
for all positive integers n. Prove that x=y.
We have that y^n + n is equal to
(y^n/x^n) (x^n + n) + n(1-(y^n/x^n)).
Since (x^n + n) divides y^n + n for every n, the term
n(1-(y^n/x^n))
must be zero for all n.
I'm afraid I don't see this step at all.  Can you explain? Can you
just remove the first term like that without implicitly assuming
y^n/x^n is an integer? For (x,y,n) = (2,13,3), x^n+n divides y^n+n, but
that term isn't zero.
You're right, my argument is wrong.
No, my argument was not so wrong. I try to explain. Suppose to divide y^n+n
for x^n+n, you get:
(y^n/x^n) (x^n + n) + n(1-(y^n/x^n)),
where n(1-(y^n/x^n)) should be intended as a "remainder". But this remainder
should be zero if x^n+n divides y^n+n, so
n(1-(y^n/x^n))=0 implies x=y and (y^n/x^n) (x^n + n) = (y^n/y^n) (y^n + n) =
y^n+n.
I hope this helped.
|
It seems you are also assuming that x divides into y; otherwise,
(y^n/x^n) will be a fraction, not an integer.
--- Christopher Heckman |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Fri Mar 31, 2006 9:35 am Post subject:
Re: nice problem from a competition
|
|
|
On 31 Mar 2006 01:43:34 -0500, Bill Dubuque <wgd@nestle.csail.mit.edu>
wrote:
| Quote: | Larry Hammick <larryhammick@telus.net> wrote: (*edited*)
From a recent IMO team selection test in Taiwan:
For integers a,b > 0 prove a = b if
n n
(1) a + n | b + n for all n > 0
HINT Find a "big" image of Z where
k k
(1) -> a + k == b + k == 0
-> a + k == b + k == 0
HINT Little Fermat kills evil powers
--Bill Dubuque
|
I tried using the hint you provided, but I just don't see it.
I was able to prove the following claim:
b - a is a multiple of every prime <= a.
proof:
Let p be a prime <= a, and let t = a + 1 - p.
Then p = a + 1 - t.
Let k =1 + t * (p - 1),
Then,
a + k = a + 1 + t * (p - 1) = a + 1 - t + t*p = p + t*p = 0 mod p
Next,
If a <> 0 mod p then a^k = a^(k-1)*a = a^(t*(p-1))*a = a mod p,
and if a = 0 mod p then also a^k = a mod p,
Then a^k + k = a + k mod p = 0 mod p.
It follows that b^k + k = 0 mod p.
But b^k + k = b + k mod p, hence also b + k = 0 mod p.
But a + k = b + k mod p implies p divides b - a.
Thus, every prime <= a is a factor of b - a, as claimed.
As a corollary, every prime factor of a divides b.
Also, using n=1, we get a + 1 divides b + 1.
It follows that a + 1 divides b - a.
So b - a has so many factors, it looks suspiciously like 0, but I
wasn't able to prove that.
Anyway, this is far as I got.
quasi |
|
| Back to top |
|
|
Bill Dubuque
science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236
|
| Posted: Fri Mar 31, 2006 11:57 am Post subject:
Re: nice problem from a competition
|
|
|
quasi <quasi@null.set> wrote:
| Quote: | Bill Dubuque <wgd@nestle.csail.mit.edu> wrote:
Larry Hammick <larryhammick@telus.net> wrote: (*edited*)
From a recent IMO team selection test in Taiwan:
For integers a,b > 0 prove a = b if
n n
(1) a + n | b + n for all n > 0
HINT Find a "big" image of Z where
k k
(1) -> a + k == b + k == 0
-> a + k == b + k == 0
HINT Little Fermat kills evil powers
I tried using the hint you provided, but I just don't see it.
I was able to prove the following claim:
b - a is a multiple of every prime <= a.
proof: Let p be a prime <= a, and let t = a + 1 - p.
|
Why constrain p? Instead let p by any prime.
| Quote: |
Let k = 1 + t (p - 1),
|
Correct k = 1 (mod p - 1) -> x^k = x (mod p) by Little Fermat
Hence a + k | b + k (mod p)
We want a + k = b + k (mod p)
Tis true if k = ??? (mod p) HINT x|y -> x=y if x = ??
p, p-1 are coprime so the two congruences for k are solvable.
Finally choose p "big" enough to force a = b. QED
--Bill Dubuque |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Fri Mar 31, 2006 9:09 pm Post subject:
Re: nice problem from a competition
|
|
|
On Fri, 31 Mar 2006 04:35:39 -0500, quasi <quasi@null.set> wrote:
| Quote: | On 31 Mar 2006 01:43:34 -0500, Bill Dubuque <wgd@nestle.csail.mit.edu
wrote:
Larry Hammick <larryhammick@telus.net> wrote: (*edited*)
From a recent IMO team selection test in Taiwan:
For integers a,b > 0 prove a = b if
n n
(1) a + n | b + n for all n > 0
HINT Find a "big" image of Z where
k k
(1) -> a + k == b + k == 0
-> a + k == b + k == 0
HINT Little Fermat kills evil powers
--Bill Dubuque
I tried using the hint you provided, but I just don't see it.
I was able to prove the following claim:
b - a is a multiple of every prime <= a.
proof:
Let p be a prime <= a, and let t = a + 1 - p.
Then p = a + 1 - t.
Let k =1 + t * (p - 1),
Then,
a + k = a + 1 + t * (p - 1) = a + 1 - t + t*p = p + t*p = 0 mod p
Next,
If a <> 0 mod p then a^k = a^(k-1)*a = a^(t*(p-1))*a = a mod p,
and if a = 0 mod p then also a^k = a mod p,
Then a^k + k = a + k mod p = 0 mod p.
It follows that b^k + k = 0 mod p.
But b^k + k = b + k mod p, hence also b + k = 0 mod p.
But a + k = b + k mod p implies p divides b - a.
Thus, every prime <= a is a factor of b - a, as claimed.
As a corollary, every prime factor of a divides b.
Also, using n=1, we get a + 1 divides b + 1.
It follows that a + 1 divides b - a.
So b - a has so many factors, it looks suspiciously like 0, but I
wasn't able to prove that.
Anyway, this is far as I got.
quasi
|
As Bill Dubuque points out, where did I use the fact that p <= a?
I invoked that restriction because I thought I needed t to be a
positive integer. But looking back at the proof, I don't need t to be
positive, just so long as it's an integer. Thus, my proof appears to
work for any prime p.
Then, letting p be an arbitrary prime, the above proof shows, I think,
that p divides b - a. Hence b - a is a multiple of every prime, which
implies b - a = 0 and therefore a = b.
quasi |
|
| Back to top |
|
|
William Elliot
science forum Guru
Joined: 24 Mar 2005
Posts: 1906
|
| Posted: Sat Apr 01, 2006 10:44 am Post subject:
Re: nice problem from a competition
|
|
|
On Sat, 1 Apr 2006, Bill Dubuque wrote:
| Quote: | Larry Hammick <larryhammick@telus.net> wrote: (*edited*)
|
Comment at **
| Quote: | From a recent IMO team selection test in Taiwan:
For integers a,b > 0 prove a = b if
n n
(1) a + n | b + n for all n > 0
HINT Find a "big" image of Z where
k k
(1) -> a + k == b + k == 0
-> a + k == b + k == 0
HINT Little Fermat kills evil powers
I tried using the hint you provided, but I just don't see it.
I was able to prove: b - a is a multiple of every prime <= a.
PROOF Let p be a prime <= a, and let t = a + 1 - p.
Then p = a + 1 - t. Let k = 1 + t (p - 1), Then,
a + k = a + 1 + t(p-1) = a + 1 - t + tp = p + tp = 0 mod p
If a <> 0 mod p then a^k = a a^(k-1) = a a^(t(p-1)) = a mod p,
and if a = 0 mod p then also a^k = a mod p,
Then a^k + k = a + k mod p = 0 mod p.
It follows that b^k + k = 0 mod p.
But b^k + k = b + k mod p, hence also b + k = 0 mod p.
But a + k = b + k mod p implies p divides b - a.
Thus, every prime <= a is a factor of b - a, as claimed.
As a corollary, every prime factor of a divides b.
Also, using n=1, we get a + 1 divides b + 1.
It follows that a + 1 divides b - a.
So b - a has so many factors, it looks suspiciously like 0,
but I wasn't able to prove that. Anyway, this is far as I got.
As Bill Dubuque points out, where did I use the fact that p <= a?
I invoked that restriction because I thought I needed t to be a
positive integer. But looking back at the proof, I don't need t to be
positive, just so long as it's an integer. Thus, my proof appears to
work for any prime p.
That's almost correct, but not quite. One can't let t be any integer.
It must satisfy a specific congruence to permit the proof to succeed.
In fact the complexities that led to errors -- the explicit
*construction* of a suitable value of k -- can be completely
eliminated if one follows the hint supplied in my prior post.
The proof requires only the *existence* of such a suitable k.
Namely, we wish to choose k, p in a specific manner that
k k
changes a + k | b + k [3]
into a + k = b + k (mod p)
i.e. 1) eliminate k from expts; 2) change '|' to '='
There are obvious ways to satisfy both of these goals:
1) Fermat's Little Theorem removes k from the exponents
x^k = x (mod p), if k = 1 (mod p-1) [4]
Thus with this choice of k, p we reduce [3] to
a + k | b + k (mod p) [5]
** The integers modulus prime p are a field, |
thus for all nonzero n,m, n | m (mod p).
| Quote: | 2) "divides" becomes "equals" if the divisor = 0
x|y -> x = y, if x = 0
So, assuming a + k = 0 (mod p), we reduce [5] to [6]
0 = a + k = b + k (mod p)
-> p | b - a, now choose p > |b - a|
-> b = a QED
The conditions [4],[6] on k are congruences mod p-1 & p
Since the moduli are coprime, a solution exists for k
by CRT (Chinese Remainder Theorem). We needn't find it.
We need k > 0, but, of course, that's always attainable
by simply adding to k a large enough multiple of p(p-1).
And that completes the long-winded version of the proof.
Anyway, I wrote so much that I risk obscuring the
beauty of this little gem. If you go back and look
at my original hint, now you should be able to see
how simple it really is. One can visualize the whole
proof mentally from the diagram supplied in the hint.
One might say it is almost a "proof without words".
Now you have it both ways - with and without words.
Hopefully words didn't destroy the magic of it all.
NOTES 1) is a rather standard technique. Since
exponential Diophantine equations are much more
intractable than are their polynomial counterparts,
it's generally a good idea to first examine any
polynomial specializations to see if a solution
may be obtained from within this simpler domain.
2) lies in the general category of simplifications
attained by converting relational statements into
equational statements. See my prior posts [1] for
much more on this. See [2] for a similar example.
--Bill Dubuque
[1] http://google.com/groups/search?q=group%3A*math*+dubuque+relational
[2] http://google.com/groups?selm=y8zk7vhhrc6.fsf%40nestle.ai.mit.edu
|
|
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Sat Apr 01, 2006 4:36 pm Post subject:
Re: nice problem from a competition
|
|
|
On 29 Mar 2006 21:12:22 -0800, "Larry Hammick"
<larryhammick@telus.net> wrote:
| Quote: | From a recent IMO team selection test in Taiwan:
Let x and y be positive integers and suppose
x^n + n divides y^n + n
for all positive integers n. Prove that x=y.
|
Ok, let's try for a generalization.
Prove or disprove:
Let x,y be integers, and let f be a univariate polynomial with integer
coefficients. If x^n + f(n) divides y*n + f(n) for all positive
integers n, then x=y.
quasi |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Sat Apr 01, 2006 4:44 pm Post subject:
Re: nice problem from a competition
|
|
|
On Sat, 01 Apr 2006 11:36:57 -0500, quasi <quasi@null.set> wrote:
| Quote: | On 29 Mar 2006 21:12:22 -0800, "Larry Hammick"
larryhammick@telus.net> wrote:
From a recent IMO team selection test in Taiwan:
Let x and y be positive integers and suppose
x^n + n divides y^n + n
for all positive integers n. Prove that x=y.
Ok, let's try for a generalization.
Prove or disprove:
Let x,y be integers, and let f be a univariate polynomial with integer
coefficients. If x^n + f(n) divides y*n + f(n) for all positive
integers n, then x=y.
quasi
|
I noticed a typo above, so here's the corrected version ...
Prove or disprove:
Let x,y be integers, and let f be a univariate polynomial with integer
coefficients. If x^n + f(n) divides y^n + f(n) for all positive
integers n, then x=y.
quasi |
|
| Back to top |
|
|
Bill Dubuque
science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236
|
| Posted: Sun Apr 02, 2006 1:22 am Post subject:
Re: nice problem from a competition
|
|
|
William Elliot <marsh@hevanet.remove.com> wrote:
| Quote: |
From a recent IMO team selection test in Taiwan:
For integers a,b > 0 prove a = b if
n n
a + n | b + n for all n > 0
From the premise it suffices to show for all prime p, p | b - a
Case prime p | a
p | a^p + p | b^p + p
p | b^p; p | b
p | b - a
Case prime p not divide a
a^(p-1) = 1 (mod p) (by Fermat's theorem)
a^(p-1) + p-1 = p = 0 (mod p)
p | a^(p-1) + p-1) | b^(p-1) + p-1
0 = b^(p-1) + p-1 = b^(p-1) - 1 (mod p)
b^(p-1) = 1 (mod p) [ie. not p | b]
a^[(a+1)(p-1) + 1] + (a+1)(p-1) + 1
= 1a + (a+1)(-1) + 1 = 0 (mod p)
p | a^[(a+1)(p-1) + 1] + (a+1)(p-1) + 1
| b^[(a+1)(p-1) + 1] + (a+1)(p-1) + 1
p | b^[(a+1)(p-1) + 1] + (a+1)(p-1) + 1
0 = b^[(a+1)(p-1) + 1] + (a+1)(p-1) + 1
= 1b + (a+1)(-1) + 1 = b - a (mod p)
p | b - a
|
That's just an obfuscated form of the proof I gave.
If you want to omit all the motivation I gave then
n n / n = 1 (mod p-1)
a + n | b + n and <
\ n = -a (mod p)
n n
-> p | a - a | b - b + b-a -> p | b-a QED
It is really that simple. There is no need to
complicate it by explictly constructing n etc.
--Bill Dubuque |
|
| Back to top |
|
|
computer
science forum beginner
Joined: 09 Sep 2005
Posts: 45
|
| Posted: Sun Apr 02, 2006 1:57 am Post subject:
Re: nice problem from a competition
|
|
|
"Bill Dubuque" <wgd@nestle.csail.mit.edu> ha scritto nel messaggio
news:y8z7j691t1z.fsf@nestle.csail.mit.edu...
| Quote: | In fact the complexities that led to errors -- the explicit
*construction* of a suitable value of k -- can be completely
eliminated if one follows the hint supplied in my prior post.
The proof requires only the *existence* of such a suitable k.
Namely, we wish to choose k, p in a specific manner that
k k
changes a + k | b + k [3]
into a + k = b + k (mod p)
i.e. 1) eliminate k from expts; 2) change '|' to '='
There are obvious ways to satisfy both of these goals:
1) Fermat's Little Theorem removes k from the exponents
x^k = x (mod p), if k = 1 (mod p-1) [4]
|
I don't know what you mean by "Fermat's little theorem", the one I know
shows that your k should be p.
| Quote: |
Thus with this choice of k, p we reduce [3] to
a + k | b + k (mod p) [5]
2) "divides" becomes "equals" if the divisor = 0
x|y -> x = y, if x = 0
So, assuming a + k = 0 (mod p), we reduce [5] to [6]
0 = a + k = b + k (mod p)
-> p | b - a, now choose p > |b - a|
-> b = a QED
The conditions [4],[6] on k are congruences mod p-1 & p
Since the moduli are coprime, a solution exists for k
by CRT (Chinese Remainder Theorem).
|
The problem is not to find k, is to find p (for any integer k>0) such that
your [3] process works. |
|
| Back to top |
|
|
Bill Dubuque
science forum Guru Wannabe
Joined: 04 May 2005
Posts: 236
|
| Posted: Sun Apr 02, 2006 10:47 am Post subject:
Re: nice problem from a competition
|
|
|
Bill Dubuque <wgd@nestle.csail.mit.edu> wrote:
| Quote: |
n n / n = 1 (mod p-1)
a + n | b + n and
\ n = -a (mod p)
n n
-> p | a - a , b - b + b-a -> p | b-a QED
|
n n
i.e. p | a -a + a+n | b -b + b-a + a+n
--Bill Dubuque |
|
| Back to top |
|
|
quasi
science forum Guru
Joined: 15 Jul 2005
Posts: 1700
|
| Posted: Mon Apr 03, 2006 9:05 pm Post subject:
Re: nice problem from a competition
|
|
|
On 3 Apr 2006 06:00:56 -0700, "karzeddin" <bassam@ahu.edu.jo> wrote:
| Quote: | Dear All
I see it as simple as that
If you assume (x=y) and obtain the original form, then it is true,
otherwise not
|
It's the "otherwise not" that you have to prove.
No, sorry, you don't get to assume the conclusion.
You can assume the hypothesis.
You job is to prove the conclusion.
Alternatively, you can assume the conclusion is false and then prove
that the hypothesis is false. That would be an indirect proof.
Or, as still another alternative, you can assume the hypothesis is
true and the conclusion is false, and then try to prove a
contradiction. That would be a proof by contradiction.
| Quote: | Assume (x=y), which implies (x^n = y^n), adding (n) to both sides, we
get
x^n+n = y^n+n , which is still (x^n+n) divides (y^n+n)
and more over this is the original form
I hoop I'm not mistaken
|
As discussed above, you have not proved the required statement.
Instead, you have proved the converse, which in this case, and I think
you'll agree, is just a triviality.
quasi |
|
| Back to top |
|
|
computer
science forum beginner
Joined: 09 Sep 2005
Posts: 45
|
| Posted: Tue Apr 04, 2006 9:03 pm Post subject:
Re: nice problem from a competition
|
|
|
"Proginoskes" <CCHeckman@gmail.com> ha scritto nel messaggio
news:1144182392.084187.178210@i40g2000cwc.googlegroups.com...
[cut]
| Quote: | But then you can't assume that the "remainder" n(1-(y^n/x^n)) is 0.
It's like writing
25 = 8/3 * 5 + 35/3
and then saying that since 5 divides into 25, the remainder is 0, which
implies that
35/3 = 0.
|
Yes, I told that x divides y. |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Wed Jan 07, 2009 8:53 pm | All times are GMT
|
|
Homeowner Loans | Credit Report | Debt Consolidation | Librerias | Debt Consolidation
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Recreational
