[pigfly]

Prove that there exsits two positive integer x,y so that:
n^x=x+my
for all positive integer m,n

[sambitnayak]

Hi pigfly,

Is there an error in your problem?

Let us say there exists two such integers and .
Then is valid for all positive integers and .
Put , then we have .
Put and , then we have .
The above two imply that , and hence, .
But then is not true for all positive integers .

Thus, there exist no such integers and .

Kindly clarify this.

**********************************************************************************
Sambit

[Peter]

I guess the question is to prove that:

[Rodolphe2005]

We search x for having n^x = x (m)
x=k*m+i with k in N and i in |[0;m-1]|
n^(km+i) = i (m)
Let a=n^m
a^k * n^i = i (m)
We can set that n ^ m = 1, if no we just need to take n' = n/pgcd(n,m) and m'=m/pgcd(n,m) and at end we multiply by pgcd(n,m) for refind n and m
So it exists b such that (it's correct ?) n^i * b = 1 (m)
Now we need to find k such that a^k = b*i (m)

If m is prime, Vect(a)=Z/mZ so for all i it exist k for a^k = b*i (m)

If m is not prime I doesn't find, for the moment, a solution

[Peter Scholze]

i think we cant that . this is for example not possible if m is prime and n is not 1 mod m, since by little fermat, . furthermore, we cannot cancel the greatest common divisor out of m,n, look at the equation(though this wouldn't anyway).

Peter

[Rodolphe2005]

"n ^ m = 1"
I wanted to say gcd(m,n)=1
But it's right I have done some errors, nice problem !

[grobber]

Well, it’s not hard to show for the case when , with prime. It’s really easy for , and then we use induction on :

We only need to prove it in the case . Assume , where . However, , and it’s clear that we can select such that the last expression is .

For the case , just take (what you called ) equal to and we get because .

Maybe a similar inductive argument works for the case when isn’t a prime power, but I haven’t tried that.

[grobber]

This problem is a consequence of this one.

[pigfly]

First of all, I upologize for some mistake during posting up the problem. I'm thankful to PeterVDD for understanding my ideas . Now,I had the solution.We will prove the sequence which is defined by is eventually constant (1)(This is also Grobber's problem:http://www.artofproblemsolving.com/Forum/viewtopic.php?t=15713 ).Then , the problem was solved. Proof by induction
+) m=1: it is easy(m=2:Problem 3 ,20 th USAMO )
+) suppose the problem corrects with every number <m . We prove that it corrects with m.
Lemma:If (1) corrects with h,q such that gcd(h,q)=1 then it corrects with hq
Indeed, (1) corrects with h,q :equiv:(mod h)
:equiv: (mod q) :ge:
According to the Chinese' theorem remainder which there exist only b(mod hq) such that: b :equiv: c(mod h); b :equiv: d(mod q) :equiv: b( mod hq) :ge: .This lemma is proved
If n= with t>1 from lemma we have the solution
If n=
then :equiv: t(mod)
-)gcd(n,m) <> 1 we have is divisible by m :ge: a
-)gcd(n,m) = 1: :equiv: 1(modm)(euler's theorem)
:ge:
deduce that :equiv: (mod m). Hence, :equiv: (modm) :ge: ,the sequence is eventually constant .In every case we have solution of (1). So, problem 3 is solved