Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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)))

If you have any questions about this or need more help, please write back
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.

If you have any questions about this or need more help, please write back
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/