
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 4th, 2010, 05:15 PM  #1 
Joined: Dec 2006 Posts: 132 Thanks: 0  Solve a Integer equation system
Let Find smallest 
May 5th, 2010, 06:23 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system
No solutions below 10^45. Edit: No solutions below 10^55. 
May 5th, 2010, 06:53 AM  #3 
Joined: Apr 2010 Posts: 65 Thanks: 0  Re: Solve a Integer equation system
when is square? (b=2k) or (c=2n+1) 
May 5th, 2010, 11:12 AM  #4 
Joined: Dec 2006 Posts: 132 Thanks: 0  Re: Solve a Integer equation system
The Chinese Remainder theorem shows that for some I don't know if this is useful. Seems a very tough problem. 
May 5th, 2010, 12:23 PM  #5  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system Quote:
If you wanted to incorporate my earlier search, you could say that for some , but that would be silly.  
May 5th, 2010, 01:39 PM  #6 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system I think it can be proven that my method can't be extended to any further primes  the proof should be easy with the amount of checking I did to remove special cases  but I won't bother writing it out. This above result (the behavior of d mod 3622080) can be used to show that c is 316675 mod 329280. This lets me check even further, showing that d > 10^70. I imagine that if I took into account behavior mod other primes (where there will be several residue classes, but hopefully not too many) I could push the verification to at least 10^80. But I have a feeling that there's a much better way to do all of this. 
May 6th, 2010, 07:39 AM  #7 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system
Working mod 372118412930880 I can show that d > 10^100. This actually wasn't nearly as hard as I expected  it took about 5 minutes (including about 1 second for preprocessing) and 23 kB. The method should scale pretty well; I'm not yet sure if it is memorybound or CPUbound. (I've picked the most efficient primes to use so far; further choices will be less good, so it won't scale as easily as it has so far.) Edit: Working mod 391343029186433681945280 took only 100 seconds (including about 18 seconds for preprocessing) and 71 MB to show that d > 10^125. It's definitely memorybound, at least as currently implemented  I could substitute time for memory to some degree if I can do fast CRTs. Also, due to a flaw in my implementation*, my actual memory use is slightly more than double the quoted  I'm essentially using two copies of a large array. * Flaw: I'm too lazy to do it the right way. 
May 6th, 2010, 03:50 PM  #8 
Joined: Dec 2006 Posts: 132 Thanks: 0  Re: Solve a Integer equation system
This is amazing! Would you please explain your algorithm? thanks

May 6th, 2010, 04:24 PM  #9  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system Quote:
Notice that 391343029186433681945280 = 2^6 * 3 * 5 * 7^3 * 11 * 31 * 61 * 211 * 331 * 421 * 1321 * 1471. 3622080 = 2^6 * 3 * 5 * 7^3 * 11 is the constant from earlier; the other primes {31, 61, 211, 331, 421, 1321, 1471} are ones which I calculated to have few appropriate residues. Here's a short example. I'll use d = 8 mod 30 rather than d = 1053698 mod 3622080 so the numbers are smaller. Consider the values of d mod 30 * 31 (where 31 is one of the primes dividing the large number above; I could have used 61 or 211 but again I'm going for size here). They are 8,38,68,98,128,158,188,218,248,278,308,338,368,398 ,428,458,488,518,548,578,608,638,668,698,728,758,7 88,818,848,878,908 But none of 68/2,158/2,278/2,308/2,368/2,398/2,458/2,488/2,518/2,548/2,668/2,728/2,788/2,818/2,848/2 are squares mod 30*31/2 (by quadratic reciprocity  use the Legendre symbol). So only 8,38,98,128,188,218,248,338,428,578,608,638,698,75 8,878,908 are possible. Of those, none of (382)/3,(1282)/3,(2182)/3,(2482)/3,(3382)/3,(4282)/3,(5782)/3,(6382)/3,(8782)/3 are cubes mod 30*31/3. Thus, c can be only 8,98,188,608,698,758,908 mod 30*31. You can use the Sun Zi's theorem (the CRT) to lift these to 1053698,37274498,73495298,55384898,91605698,408965 78,26408258 mod 112284480 = 3622080*31, which means that instead of checking 1 number out of every 30, you're checking 7 numbers out of every 112284480.  
May 7th, 2010, 10:32 AM  #10 
Joined: Dec 2006 Posts: 132 Thanks: 0  Re: Solve a Integer equation system
Thanks a lot CRGreathouse. I got lots to learn.

May 7th, 2010, 10:54 AM  #11 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system
No problem. You should try this in Pari  it's very easy to use. For example, you can check if a number is a square with Code: issquare(2484723543478) Code: issquare(Mod(123424654645,43857476878425458)) Where did you get the question? 
May 10th, 2010, 11:01 AM  #12 
Joined: Sep 2008 Posts: 142 Thanks: 0  Re: Solve a Integer equation system
I do not have an aswer, but I stronly suspect that there are no solutions (appart from the excluded d=2,a=1,b=0,c=1 which prevents one from proving that ther are no soloutions via the kind of congruences CRGreathouse uses). Of course there ist the numerical evidence that CRGreathouse has found, but there is one more reason: There is a very famous conjecture called the ABCconjecture, which if true would prove, that there are no "big" solutions for even the equality 3b^3+2=5c^5+3. For details on the conjecture see for instance here: http://en.wikipedia.org/wiki/Abc_conjecture It does not violate the conjecture as written in Wikipedia, but you can see from there that the ratio: ln(C)/ln(rad(ABC)) is bounded. The biggest such ratio (called quallity) one has found so far is 1,6299 (see http://www.math.leidenuniv.nl/~desmit/a ... .php?set=2) and it is conjectureed, that thats the maximum or at least not far from it. setting A=1, B=3b^3 and C=5c^5 for a big solution b,c of your problem would have quality almost 15/8 or 1,875 thats way bigger than any exspected value (and would violate the more complicted and more precise conjecture on the "merite" of a tripple). So on the one hand, your problem probably does not have a solution, on the other hand if you manage to find one, that will produce a publication in a good journal. Happy hunting! Peter 
May 10th, 2010, 07:06 PM  #13  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system
Good insight, Peter. I hada hunch that it was connected with abc, but didn't look into it since I figured the OP wouldn't know about it. Quote:
 
May 11th, 2010, 12:07 AM  #14  
Joined: Sep 2008 Posts: 142 Thanks: 0  Re: Solve a Integer equation system Quote:
 
May 12th, 2010, 02:02 PM  #15 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 12,809 Thanks: 84  Re: Solve a Integer equation system
I've written some additional code to help me generate larger modular systems. The systems are now too large to hold in main memory, but it's easy to keep them in two arrays and CRT them together one at a time. (Three arrays would also be possible, reducing memory to the cube root rather than the square root of the naive version, but only at the cost of a large increase in the time needed to calculate the moduli. At least, I think so.) The code is very messy but seems to work. Code: checkmod(v1,m1,v2,m2,ff,lim)={ my(m=lcm(m1,m2),mv1,t); for(i=1,#v1, mv1=Mod(v1[i],m1); for(j=1,#v2, forstep(n=lift(chinese(mv1,Mod(v2[j],m2))),lim,m, ff(n) ) ) ) }; addhelp(checkmod, "checkmod(v1,m1,v2,m2,ff,lim): Runs the function ff on nonnegatives below lim that are v1[i] mod m1 and v2[j] mod m2 for some i and j."); cc(lim,sizelim)={ my(v1=[1053698],m1=3622080,v2=[0],m2=1,sl,sz,m,s); local(mod); \\ Populate arrays while((sl = (sizelim / 2) \ sizebyte(v1)) > 12, sz=#v1; v1=newvec(v1,m1,min(sl,1e3),1); if(#v1==sz, break, m1 = mod) ); sizelim = sizebyte(v1); print("First array: "#v1" values mod "m1); print(" "sizelim>>10" kB remain"); while((sl = sizelim \ sizebyte(v2)) > 12, sz=#v2; v2=newvec(v2,m2,min(sl,2e3),m1); if(#v2==sz, break, m2 = mod) ); m = lcm(m1,m2); s = #v1 * #v2; print("Second array: "#v2" values mod "m2); print("Working with "s" values mod "m); print("About "lim\m" steps needed"); \\ Convert arrays from d to c for(i=1,#v1,v1[i]=lift(5*Mod(v1[i],m1)^5+3)); for(i=1,#v2,v2[i]=lift(5*Mod(v2[i],m2)^5+3)); checkmod(v1,m1,v2,m2, \\c>my(d=5*c^5+3);if(issquare(d/2)&&ispower((d2)/3,3),print(c)) c>my(d=5*c^5+3);if(ispower((d2)/3,3)&&issquare(d/2),print(c)) ,lim) }; newvec(v, m, maxprime, avoid)={ my(best=1,bestAt,s,t,a,b,c,tv,nv); avoid = lcm(avoid, m); forprime(p=3,maxprime, s = 0; if(gcd(avoid,p) == 1, t = p * 30; forstep(d=8,t,30, a=Mod(d/2,t/2); b=Mod((d2)/3,t/3); c=Mod((d3)/5,t/5); if(issquare(a)&ispower(b,3)&ispower(c,5),s++) ) , \\t = p^(1+valuation(v1,p)) * 30 / gcd(30, p) s = p \\ Just don't calculate these  probably not going to be any good, and certainly lots of trouble. ); if(s/p < best, best = s/p; bestAt = p; ) ); if (best == 1, return(v)); mod = m * bestAt; \\ local variable t = bestAt * 30; tv=[]; forstep(d=8,t,30, a=Mod(d/2,t/2); b=Mod((d2)/3,t/3); c=Mod((d3)/5,t/5); if(issquare(a)&ispower(b,3)&ispower(c,5),tv=concat(tv,d)) ); nv=vector(#v*#tv); a=0; for(i=1,#v, for(j=1,#tv, nv[a++]=lift(chinese(Mod(v[i],m),Mod(tv[j],bestAt))) ) ); nv }; Code: cc(1e26,3*10^6) This version spends a *lot* of time doing CRTs, which in turn rely on the extended Euclidean algorithm. I don't think this is particularly wellimplemented in Pari, unfortunately. Sadly, this method hasn't given me much of an improvement, although it has removed (for the moment) the memory barrier. I'm working on a proof that d > 10^145; it might take half an hour. 

Tags 
equation, integer, solve, system 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
help, solve equation in the complex number system?  1love  Algebra  4  September 10th, 2013 06:05 PM 
Solve equation in integer number  harrypham  Number Theory  12  August 10th, 2012 12:02 AM 
help to solve equation system  mariorossi  Algebra  3  September 18th, 2010 02:51 PM 
solve of system of nonlinear equation  abotaha  Algebra  2  July 24th, 2010 12:27 AM 
solve of system of nonlinear equation  abotaha  Calculus  1  January 1st, 1970 12:00 AM 