A Polynomial in Three Variables with Few Integer SolutionsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/