Associated Topics || Dr. Math Home || Search Dr. Math

### A Polynomial in Three Variables with Few Integer Solutions

```Date: 03/12/2011 at 09:42:00
From: Reza
Subject: ok

Prove this equation has no solution for natural numbers x, n, and k:

x^(2n) = (38n + 1)k + 2

```

```
Date: 03/28/2011 at 23:06:50
From: Doctor Vogler
Subject: Re: ok

Hi Reza,

Thanks for writing to Dr. Math. That's a really good question!

It had me stumped for some time ... until I finally figured out that the
reason I couldn't prove it: it's not true.

The smallest counterexample is n = 13797, for which there are many
solutions in x and k, including

x = 12
k = (12^27594 - 2)/524287 (which is an integer).

Some other possible x values for this same n are

x = 58, 66, 101, 133, 160, 168, 214, 215, 247,
249, 270, 312, 316, 319, 340, 343, 357, and so on.

There are no solutions with n < 1000000 other than n = 13797. That was as
far as I searched.

What I did was change your equation to

x^(2n) = 2 (mod 38n + 1).

This is equivalent to

x^(2n) = 2 (mod p^k) for all prime power factors of 38n + 1.

Since 38n + 1 is odd, p^k must also be odd, which means that the
multiplicative group of integers mod p^k is cyclic of order
(p - 1)p^(k - 1). So to find a solution for x, we must check if 2 is a
gcd(2n, (p - 1)p^(k - 1))'th power in that group. This is easy to test by
checking if

2^((p - 1)p^k/gcd(2n, (p - 1)p^(k - 1))) = 1 (mod p^k)).

So I had a computer program start at n = 1 and count up, and for each n it
would factor n, then run through the prime power factors and check if that
equation holds for all of the prime power factors. If it did, then I had
it print out n. I checked up to n = 1000000, and I got exactly one hit,
which I verified manually to make sure I did this all correctly.

I did this all in the math program GNU Pari, which you can download for
free from

http://pari.math.u-bordeaux.fr/

The instruction I gave Pari was:

for(n=1,100000,m=38*n+1;f=factor(m);w=1;for(i=1,length(f~),p=f[i,1];
e=f[i,2];q=p^e;l=(p-1)*p^(e-1);if(Mod(2,m)^(l/gcd(2*n,l))!=1,w=0));
if(w==1,print(n)))

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 03/31/2011 at 19:43:52
From: Doctor Vogler
Subject: Re: ok

Hi Reza,

Some more computer searching showed that the next-smallest n for which
there are solutions (after n = 13797) is

n = 7233601536.

For this n, some solutions for x are

x = 7741533
x = 11446861

There are many others, too. Obviously, solutions to your equation are very
sparse, but there are solutions. (More specifically, valid n's are sparse;
valid x's for those n's are not.)

Given the size of the first two solutions, I don't expect I'll be able to
do enough computer searching to find a third value for n that solves your
equation.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 04/04/2011 at 21:26:50
From: Doctor Vogler
Subject: Re: ok

Hi Reza,

I realized that I made a mistake.

The command I should have given Pari was:

for(n=1,100000,m=38*n+1;f=factor(m);w=1;for(i=1,length(f~),p=f[i,1];
e=f[i,2];q=p^e;l=(p-1)*p^(e-1);if(Mod(2,q)^(l/gcd(2*n,l))!=1,w=0));
if(w==1,print(n)))

When I do this, there are a LOT more solutions! The smallest one has

n = 21
x = 58
k = 145020350463113589197975088134437366
213226795686957600478033954905820738.

and show me what you have been able to do, and I will try to offer further
suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search