My Math Forum Solve a Integer equation system

 Number Theory Number Theory Math Forum

 May 4th, 2010, 05:15 PM #1 Joined: Dec 2006 Posts: 132 Thanks: 0 Solve a Integer equation system Let $a,b,c \in \mathbb{N}^+$ Find smallest $d= 2a^2=3b^3+2=5c^5+3$
 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 $12*k^3 + 1$ is square? (b=2k) or $80n^5 + 200n^4 + 200n^3 + 100n^2 + 25n + 4$ (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 $d= 38+30k$ for some $k\in \mathbb{N}^+$ 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:
 Originally Posted by elim The Chinese Remainder theorem shows that $d= 38+30k$ for some $k\in \mathbb{N}^+$ I don't know if this is useful. Seems a very tough problem.
I'd usually write $d=30k+8$ or $d\equiv8\pmod{30}$, but yeah. You can narrow it down more if you like. After a bit of work, I was able to show that $d\equiv1053698\pmod{3622080}$. No further improvements are available with my methods using primes below 100 million.

If you wanted to incorporate my earlier search, you could say that $d=999999999999999999999999999999999999999999999999 9406658+3622080k$ for some $k\in\mathbb{Z}^+$, 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 pre-processing) and 23 kB. The method should scale pretty well; I'm not yet sure if it is memory-bound or CPU-bound. (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 pre-processing) and 71 MB to show that d > 10^125. It's definitely memory-bound, 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:
 Originally Posted by elim This is amazing! Would you please explain your algorithm? thanks
c has the highest power, so I check values of c to see if they produce valid a and b. I restrict the values it can take on by considering which values will produce a and b that are integers and for which squares and cubes exist mod a given prime (or prime power). I choose primes that have few valid residues; these are produced brute-force.

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
(38-2)/3,(128-2)/3,(218-2)/3,(248-2)/3,(338-2)/3,(428-2)/3,(578-2)/3,(638-2)/3,(878-2)/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) and if a residue class represents some squares with Code: issquare(Mod(123424654645,43857476878425458)) These together with ispower(..., 3) were the main parts of my calculations above. (Working with large numbers by hand is hard!) 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 ABC-conjecture, 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:
 Originally Posted by Peter 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).
That's not a solution over the integers -- c = -1 yields d = -2, not 2. (There are no integer solutions with c or d negative, since d/2 must be a square.)

May 11th, 2010, 12:07 AM   #14

Joined: Sep 2008

Posts: 142
Thanks: 0

Re: Solve a Integer equation system

Quote:
 Originally Posted by CRGreathouse That's not a solution over the integers -- c = -1 yields d = -2, not 2. (There are no integer solutions with c or d negative, since d/2 must be a square.)
Oh I forgot about the factor 3. Maybe I should leave the explicit calculations to others .

 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((d-2)/3,3),print(c)) c->my(d=5*c^5+3);if(ispower((d-2)/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((d-2)/3,t/3); c=Mod((d-3)/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((d-2)/3,t/3); c=Mod((d-3)/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 }; Usage: something like Code: cc(1e26,3*10^6) where 1e26 is the checking limit (on c, so d is checked to the fifth power of this value) and 3*10^6 is the memory bound. Larger memory bounds take more memory (duh!) but also spend more time calculating CRTs. Small memory bounds take less time on CRTs but more time checking if large numbers are cubes. 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 well-implemented 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post 1love Algebra 4 September 10th, 2013 06:05 PM harrypham Number Theory 12 August 10th, 2012 12:02 AM mariorossi Algebra 3 September 18th, 2010 02:51 PM abotaha Algebra 2 July 24th, 2010 12:27 AM abotaha Calculus 1 January 1st, 1970 12:00 AM

 Contact - Home - Top