nice problem from a competition
Larry Hammick
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.
computer
"Larry Hammick" <larryh...@telus.net> ha scritto nel messaggio
news:1143695542.7...@z34g2000cwc.googlegroups.com...
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. Hence 1=(y^n/x^n) for all n, then y=x (recalling
that x and y are positive integers).
Dave Rusin
Larry Hammick <larryh...@telus.net> wrote:
Nice puzzle.
Spoiler follows.
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
.
.
[spoiler space]
For every prime p not dividing x, let n = (x+1)(p-1) + 1; conclude p|(y-x).
dave
computer
"Dave Rusin" <ru...@vesuvius.math.niu.edu> ha scritto nel messaggio
news:e0h8ob$elk$1...@news.math.niu.edu...
I am interested in your solution, could you be more specific? I see
something obscure with your procedure, I think it is due to the fact that,
with just a line, I can't figure out what you want to show. Thanks.
Christopher
> > 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.
Roman B. Binder
there will be equation with some positive integer C(n),
what simply denote Cn:
y^n + n = Cn(x^n + n)
y^n - Cn(x^n) = n(Cn - 1)
1):what for mod n for prime n:
Rs = y - Cn x = Ls = 0
then every y = Cn x mod n for every prime n
but such set of conditions will be not possible
for different values of x and y once Cn is not optional
chosen value but Cn = (y^n +n)/(x^n +n)
(what we could suppose to be some integer initially)
2): on the other hand for y;x;n of gcd=1
y^n + n will be mostly of gcd=1 for x^n +n
ex: y=3;x=2;n=5: Cn = 248/37 = 2^3 *31 / 37
y=5;x=2;n=3: Cn = 128/11 = 2^7 /11
y=11;x=8;n=7: Cn = 19487178/2097159
Cn = 2*3^2 * 1082621 /3*699053
where only 3 is common but Cn remains to be
factor and not some integer
3):then once x and y divided by n let y=ny1; x=nx1:
n[y1^n *n^(n-1) +1] = n*Cn[x1^n *n^(n-1) +1]
n^(n-1) *[y1^n -Cn x1^n] = Cn -1
and then mod n Cn = 1
what applying to 1): mod n x = mod n y so x=y
Also generally:
1) simple mod rules for n as prime could not be
completed until x=y and Cn=1
2) very questionable is integer value of Cn even
for single special values of x;y;n
what implies only trivial x=y
With Compliments
Ro-bin
computer
"Christopher" <ni...@fas.harvard.edu> ha scritto nel messaggio
news:1143748511.2...@e56g2000cwe.googlegroups.com...
You're right, my argument is wrong.
computer
"computer" <comp...@computer.computer> ha scritto nel messaggio
news:442c3e60$0$36930$4faf...@reader3.news.tin.it...
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.
computer
"Christopher" <ni...@fas.harvard.edu> ha scritto nel messaggio
news:1143748511.2...@e56g2000cwe.googlegroups.com...
Another thing: you are assuming that x<>y (x=2 and y=13) and you are in a
particular case: n=3. Ask yourself: "is that true for any n ?" like the
problem stated?
Proginoskes
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
Dave Rusin
computer <comp...@computer.computer> wrote:
>>>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.
>> For every prime p not dividing x, let n = (x+1)(p-1) + 1; conclude
>> p|(y-x).
>I am interested in your solution, could you be more specific? I see
>something obscure with your procedure, I think it is due to the fact that,
>with just a line, I can't figure out what you want to show. Thanks.
The point is that the special n's I'm looking at are simultaneously
congruent to 1 mod (p-1) and to -x mod p. The former statement
means (by Fermat's little theorem) that z^n = z mod p for any
integer z; in particular, that x^n = x mod p. Meanwhile the other
statement makes x congruent to -n mod p. Put together, they show
x^n + n = 0 mod p, i.e. p divides x^n + n.
By assumption, then, p also divides y^n + n, and hence divides the
difference, which equals x^n - y^n . Thus x^n = y^n mod p. But
I have already remarked that z^n = z for every z, and if we apply
this statement to both z=x and z=y we deduce x = y mod p, i.e.
p divides x-y.
But this means x-y is divisible by every prime p and therefore
can only be zero.
(I'm not sure why I first insisted that we apply this argument only to
primes not dividing x, although of course that's sufficient.)
dave
computer
"Proginoskes" <CCHe...@gmail.com> ha scritto nel messaggio
news:1143760566.0...@g10g2000cwb.googlegroups.com...
>>
>> (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.
>
I am *not* assuming that x divides y and (y^n/x^n) *is* a fraction.
Bill Dubuque
>
> From a recent IMO team selection test in Taiwan:
>
>
> 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
Roman B. Binder
rewriting Yours y^n + n as:
(y^n)(x^n + n)/(x^n) + n(x^n -y^n)/(x^n)
after successful division of the first term by (x^n + n)
You'll have fraction (y^n)/(x^n) !
thus the remaining therm should be also some proper
fraction and not equal to 0 .
Therefore Your argumentation is working only for
..........y/x = m as natural number ..............
..................................................
(on the other side every reminder should be checked
if not divided by certain number and not assumed
to be 0 automatically: thus could be so many false
simplifications )
Anyhow Congratulations
Ro-bin
quasi
wrote:
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
Bill Dubuque
>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>Larry Hammick <larryh...@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 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.
>
> 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
computer
"Roman B. Binder" <rbi...@netvision.net.il> ha scritto nel messaggio
news:23935625.1143794686...@nitrogen.mathforum.org...
>>
> But already You've create fractions:
> rewriting Yours y^n + n as:
> (y^n)(x^n + n)/(x^n) + n(x^n -y^n)/(x^n)
> after successful division of the first term by (x^n + n)
> You'll have fraction (y^n)/(x^n) !
> thus the remaining therm should be also some proper
> fraction and not equal to 0 .
> Therefore Your argumentation is working only for
> ..........y/x = m as natural number ..............
I see your point, but y/x must be an integer. Suppose that y/x = m+e, with m
integer and e in (0,1). For n=1 we have:
k (x^1 + 1) = y^1 +1, where k is a positive integer.
This leads to
k (y/(m+e) +1) = y+1,
then
k (y+m+e) = (y+1)(m+e)
that is
ky+km-ym-m = (y+1-k) e,
since the left term is sure an integer, the rhs shows a number that is not
an integer.
computer
"computer" <comp...@computer.computer> ha scritto nel messaggio
news:442d1c71$0$29730$4faf...@reader2.news.tin.it...
> I see your point, but y/x must be an integer. Suppose that y/x = m+e, with
> m integer and e in (0,1). For n=1 we have:
>
> k (x^1 + 1) = y^1 +1, where k is a positive integer.
>
> This leads to
>
> k (y/(m+e) +1) = y+1,
>
> then
>
> k (y+m+e) = (y+1)(m+e)
>
> that is
>
> ky+km-ym-m = (y+1-k) e,
>
> since the left term is sure an integer, the rhs shows a number that is not
> an integer.
Hmmm... ooops.
I find out that this attempt to prove the statement is only partially true.
My proof is not correct. Sorry.
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
Bill McCray
I don't think you wrote what you meant. This is a case where a comma
makes a big difference. As written, it means "I am not assuming that
x divides y, and I am not assuming that (y^n/x^n) is a fraction".
Bill
----------------------------------------------------------------
Reverse parts of the ISP name and the user name for my e-address
Bill Dubuque
>quasi <qu...@null.set> wrote: (*edited*)
>>Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>Larry Hammick <larryh...@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
>>
>>
>> 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.
>
>
> 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]
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
William Elliot
> >>>Larry Hammick <larryh...@telus.net> wrote: (*edited*)
> >>>>
Comment at **
** The integers modulus prime p are a field,
thus for all nonzero n,m, n | m (mod p).
quasi
wrote:
>quasi <qu...@null.set> wrote:
No, I see the magic.
Let me try to replay it.
Fix a prime p.
Find (or show the existence of) a positive integer k such that p-1 |
k-1 and p | a+k .
Finding such a k is equivalent to solving the simultaneous congruences
k = 1 mod (p-1) and k = -a mod p.
By CRT, such there is a unique solution mod p*(p-1), so such a k
exists (and can be forced to be positive).
p | a + k => a + k = 0 mod p => a^k + k = 0 mod p (since p-1 | k-1).
a^k + k = 0 mod p => b^k + k = 0 mod p (since a^k + k | b^k + k).
b^k + k = 0 mod p => b + k = 0 mod p (since p-1 | k-1).
a + k = b + k = 0 mod p => a = b mod p => p | a - b.
Since p was an arbitrary prime, p | a - b for all primes p.
It follows that a - b = 0, so a = b, as required.
quasi
Bill Dubuque
>>>Larry Hammick <larryh...@telus.net> wrote: (*edited*)
>>>>
>>>> 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
>> 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).
Of course, but so what? If you read the whole proof you'll observe
that the goal at this point is to specialize k in [5] so that the
divisibility relation changes into an equality. This is achieved
as described below in 2), i.e. by forcing the divisor to be zero.
Your remark applies only to nonzero divisors so it isn't relevant
here. I deliberately chose to present the proof in this form to
make explicit my reasoning processes. I could have presented it
more traditionally by starting out saying "let p be a prime
divisor of a^n + n..." but that would be unmotivated. Instead,
every step in the proof is completely motivated and the path to
the goal is clear right from the start.
William Elliot
> >>>>> 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
<snip>
> No, I see the magic.
> Let me try to replay it.
>
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
QED.
quasi
<ma...@hevanet.remove.com> wrote (edited):
>
>Larry Hammick wrote (edited):
>>
>>From a recent IMO team selection test in Taiwan:
>>
>>
>>If a^n + n | b^n + n for all positive integers n,
>>
>>then a=b.
>
>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
>
>QED.
Your proof looks good to me.
quasi
quasi
<larryh...@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
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
quasi
>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
Here's an instant counterexample.
Let a=2, b=8, and let f=1.
For all positive integers n, 8^n + 1 = (2^n)^3 + 1 which is divisible
by 2^n+1.
Ok, then let's restrict f to nonconstant polynomials.
Prove or disprove:
Let x,y be integers, and let f be a nonconstant univariate polynomial
quasi
>
>Ok, then let's restrict f to nonconstant polynomials.
>
>Prove or disprove:
>
>Let x,y be integers, and let f be a nonconstant univariate polynomial
>with integer coefficients. If x^n + f(n) divides y^n + f(n) for all
>positive integers n, then x=y.
>
>quasi
Hmm ...
I think I may have restricted f unnecessarily.
Let's put the constants back (except for 0, 1, and -1).
Ok, so here's the latest version ...
Prove or disprove:
Let x,y be integers, and let f be a univariate polynomial
with integer coefficients, but f not identically 0, 1, or -1.
If x^n + f(n) divides y^n + f(n) for all positive integers n, then
x=y.
Remarks:
The case f(n)=n has already been settled. Presumably any linear
function of n could be resolved in a similar way, but I haven't
actually checked this. Anyone want to try wrapping up the linear case?
It might be worth attacking a few other simple special cases.
Let's consider the case where f is constant. As a simple example, what
about if f=2?
Also, why not consider a simple quadratics? For example, how about
f(n) = n^2?
The Little Fermat Theorem may not be enough any more. In fact, the
case f=2 may already require a new tool.
To allow more general polynomials, it might be more natural to relax
the hypothesis by only requiring x^n + f(n) divide y^n + f(n) for all
sufficiently large positive integers n.
Feel free to try any special case that seems open to some attack.
quasi
Bill Dubuque
>>
>> From a recent IMO team selection test in Taiwan:
>>
>> For integers a,b > 0 prove a = b if
>>
>> n n
>
>
> 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
computer
"Bill Dubuque" <w...@nestle.csail.mit.edu> ha scritto nel messaggio
news:y8z7j69...@nestle.csail.mit.edu...
> 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.
>
> 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.
Bill Dubuque
>> eliminated if one follows the hint supplied in my prior post.
>> 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.
k 1+m(p-1) p-1 m
x = x = x (x ) = x (mod p)
For significant generalizations see my prior post
http://google.com/groups?selm=y8zhe8n5383.fsf%40nestle.ai.mit.edu
>> 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.
It suffices to prove there exists p, k satisfying the derived
constraints: prime p>|b-a|, k>0, k = 1 (mod p-1), k = -a (mod p)
Syntactical roles played by p and k in the proof (such as their
order of first appearance, etc) are not relevant to its truth.
--Bill Dubuque
quasi
I can prove it for any nonconstant polynomial f.
Also, the hypothesis with regard to n can be weakened to "all
sufficiently large positive integers n, instead of "all positive
integers n".
Theorem:
Let x,y be integers, and let f be a nonconstant univariate polynomial
with integer coefficients.
If x^n + f(n) divides y^n + f(n) for all sufficiently large positive
integers n, then x=y.
I'll omit the proof for now (lack of time), but I'll point out that
the proof strategy is essentially the same as that outlined by Bill
Dubuque for the original problem.
As a hint, try the case f(n)=n^2. The analysis is a little different
from that in the original problem, but mostly the same, and not too
hard.
Then try f(n)=n^k, which is no harder than n^2.
Looking at the argument for f(n)=n^k, it should be clear that no use
was made of the fact that f was a power. Any nonconstant polynomial
would work just as well.
I can supply further hints as needed, but if you follow the Dubuque
plan of attack, adapted to the new f(n), you should be able to see
what to do next.
Interestingly enough, I have no idea how to prove it when f is a
constant other than 0, 1, or -1. For example:
Problem (1).
Prove or disprove: If x,y are integers such that x^n + 2 divides y^n +
2 for all positive integers n, then x=y.
Another question that arises is whether the conditions with regard to
n be relaxed still further to just "infinitely many n". For example:
Problem (2).
Prove or disprove: If x,y are integers such that x^n + n divides y^n +
n for infinitely many positive integers n, then x=y.
At this point, I have no real insight into either of the above two
problems. My gut sense is that the statements are both true, but I'm
not all that sure about it.
quasi
Bill Dubuque
>
> n n / n = 1 (mod p-1)
> a + n | b + n and <
> \ n = -a (mod p)
> n n
n n
i.e. p | a -a + a+n | b -b + b-a + a+n
--Bill Dubuque
bargiax
"Bill Dubuque" <w...@nestle.csail.mit.edu> wrote:
> 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]
Hello Bill. Could you explain me how to change [3] into a+k | b+k (mod p) ?
The problem is that I don't know what [5] means.
What does it means a writing like "A|B (mod C)" ? Maybe that A (mod C)
divides B (mod C) ?
Thank you.
William Elliot
Seems he's working in integers prime modulus p.
Then Z_p is a field and within Z_p, a|b
if a /= 0 (mod p) or if a = b = 0 (mod p).
Gerry Myerson
quasi <qu...@null.set> wrote:
> Problem (1).
>
> Prove or disprove: If x,y are integers such that x^n + 2 divides y^n +
> 2 for all positive integers n, then x=y.
x = -1, y = 1.
[Note - my newsreader doesn't recognize alt.math.recreational
so I trimmed it]
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
quasi
<ge...@maths.mq.edi.ai.i2u4email> wrote:
>In article <hu1v22tp5q86o74jf...@4ax.com>,
> quasi <qu...@null.set> wrote:
>
>> Problem (1).
>>
>> Prove or disprove: If x,y are integers such that x^n + 2 divides y^n +
>> 2 for all positive integers n, then x=y.
>
>x = -1, y = 1.
Haha -- I missed that loophole, but it's easily fixed ...
Problem (1) [revised]
Prove or disprove: If x,y are integers such that x^n + 2 divides y^n +
2 for all positive integers n, then x = plus or minus y.
quasi
quasi
Well, that was too drastic a fix, but we also need to exclude x=0, y
even. If we exclude (x,y)=(-1,1) or (x,y)=(0,2*k), I think the problem
is redeemed, but to keep the statement simple, let's restrict to
positive integers.
Problem (1) [revised again]
Prove or disprove: If x,y are positive integers such that x^n + 2
divides y^n + 2 for all positive integers n, then x = y
quasi
computer
"Roman B. Binder" <rbi...@netvision.net.il> ha scritto nel messaggio
news:23935625.1143794686...@nitrogen.mathforum.org...
> But already You've create fractions:
> rewriting Yours y^n + n as:
> (y^n)(x^n + n)/(x^n) + n(x^n -y^n)/(x^n)
> after successful division of the first term by (x^n + n)
> You'll have fraction (y^n)/(x^n) !
> thus the remaining therm should be also some proper
> fraction and not equal to 0 .
> Therefore Your argumentation is working only for
> ..........y/x = m as natural number ..............
> ..................................................
However, from the conditions should be x|y and so y/x is an integer. This is
trivial, take any p prime, p>x,y. We have
x^p + p == x + p (mod p) == x (mod p)
y^p + p == y + p (mod p) == y (mod p)
Since x^p + p | y^p + p it follows that [x] | [y].
karzeddin
I see it as simple as that
If you assume (x=y) and obtain the original form, then it is true,
otherwise not
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
Best Regards
Bassam Karzeddin
Al-Hussein Bin Talal University
JORDAN
M.J.T. Guy
>
Nice one. But does that cover the caes when p^2 divides x for some p?
Mike Guy
quasi
>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.
>
>Assume (x=y),
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.
>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
William Elliot
bassam king karzeddin
Larry Hammik who started the thread, didn't add any comment or website link, so I thought he wanted to make it as April's fool
sorry for the misunderstanding
with regards
B.Karzeddin
Bill Dubuque
>M.J.T. Guy <mj...@cus.cam.ac.uk> wrote:
>>Dave Rusin <ru...@vesuvius.math.niu.edu> wrote:
>>>Larry Hammick <larryh...@telus.net> wrote:
>>>>
>>>>
>>>> n n
>>>
>>> For every prime p not dividing a, let n = (a+1)(p-1) + 1;
>>> conclude p|b-a
>>
>> Nice one. But does that cover the caes when p^2|a for some p?
>
> No, see my post April 1 in this thread where I give all details.
Yes, not no. As Dave mentioned in a followup, the condition
"not p|a" can be omitted. Dave's proof is essentially the
same as one I gave here, except I motivated it *completely*.
Stripped of all the motivation, my proof is, in one line:
p-1|n-1 \ n n
>-> p | a -a + a+n | b -b + b-a + a+n -> p|b-a
p|a+n /
--Bill Dubuque
Proginoskes
computer wrote:
> "Proginoskes" <CCHe...@gmail.com> ha scritto nel messaggio
> news:1143760566.0...@g10g2000cwb.googlegroups.com...
> >>
> >> y^n + n = (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.
>
>
> I am *not* assuming that x divides y and (y^n/x^n) *is* a fraction.
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.
--- Christopher Heckman
computer
[cut]
> 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.
Proginoskes
So you're taking back what you said in the post on March 30:
> I am *not* assuming that x divides y and (y^n/x^n) *is* a fraction.
--- Christopher Heckman
computer
>
> So you're taking back what you said in the post on March 30:
>
>> I am *not* assuming that x divides y and (y^n/x^n) *is* a fraction.
>
Yes, I admitted my mistake in a prior message.