Re: x^n + y^n = k (mod m)

On Mon, 05 Nov 2007 02:45:13 GMT, Gerry Myerson
<gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

In article <rbisrael.20071105003011$4a2e@xxxxxxxxxxxxxxxx>,
Robert Israel <israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

quasi <quasi@xxxxxxxx> writes:

Sorry, if this is a duplicate -- it appeared not to go through the
first time.

On Sun, 04 Nov 2007 21:52:41 GMT, Gerry Myerson
<gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

In article <j1eri39vlnds5itga57pvsclrf0eld0j3c@xxxxxxx>,
quasi <quasi@xxxxxxxx> wrote:

Does there exist an integer n > 2, and an integer k, such that

(1) x^n + y^n = k has no integer solutions.

(2) For all integers m > 1, the congruence x^n + y^n = k (mod m) has
integer solutions.

Here are two possible routes to finding such a thing.

1. There is no solution in integers to x^3 + y^3 = 6,
but there is a solution in rationals,
so x^3 + y^3 = 6 (mod m) has a solution for every m
avoiding prime divisors of the denominators. Maybe it
has solutions for those primes, too.

Nice plan of attack.

But x^3 + y^3 = 6 (mod 9) has no solutions.

OK, then, 20 = (19 / 7)^3 + (1 / 7)^3

I follow the idea.

The rational solution yields a congruence solution in integers to

x^3 + y^3 = 20 (mod m)

for all integers m > 1 such that (m,7) = 1.

and x^3 + y^3 = 20 mod 49 has the solution x = 6, y = 0.

Using x = 0 and noting that y^3 = 20 mod 7 has the solution y = 3,
Hensel's Lemma can be used to successively find a solution to

y^3 = 20 mod 7^k for k = 2, 3, 4, ...

Hence, using x = 0, the congruence

x^3 + y^3 = 20 mod m has solutions whenever m is a power of 7.

The Chinese Remainder Theorem clinches the rest.

Thus, while the equation x^3 + y^3 = 20 has no integer solutions, the
congruence x^3 + y^3 = 20 (mod m) has integer solutions for all
integers m > 1.

2. There are only finitely many primes p for which
there exists k such that x^3 + y^3 = k (mod p)
has no solution. Use Chinese Remainder Theorem
to find k such that x^3 + y^3 = k (mod p) has solution
for all those k; then x^3 + y^3 = k (mod m) ought to have
a solution for all m. Just make sure you choose k so there
are no solutions in Z.

No, I don't agree with the above.

Just because you have a solution mod p does not guarantee a solution
mod p^2. The issue is prime powers.

Case in point: the example above.

I think Hensel's Lemma gives you a solution
to x^3 + y^3 = k mod p^2
if you have a solution mod p,
except when p = 3.

Right.

As long as p is not 3, a solution to x^3 + y^3 = k mod p can be lifted
(keeping x fixed) to all higher powers of p.

Thanks for the insights.

quasi
.

Relevant Pages