My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

Reply
 
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
elim is offline  
 
May 5th, 2010, 06:23 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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)
Xitami is offline  
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.
elim is offline  
May 5th, 2010, 12:23 PM   #5
Global Moderator
 
CRGreathouse's Avatar
 
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 for some
I don't know if this is useful. Seems a very tough problem.
I'd usually write or , but yeah. You can narrow it down more if you like. After a bit of work, I was able to show that . 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 for some , but that would be silly.
CRGreathouse is offline  
May 5th, 2010, 01:39 PM   #6
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
May 6th, 2010, 07:39 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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
elim is offline  
May 6th, 2010, 04:24 PM   #9
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
elim is offline  
May 7th, 2010, 10:54 AM   #11
Global Moderator
 
CRGreathouse's Avatar
 
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?
CRGreathouse is offline  
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
Peter is offline  
May 10th, 2010, 07:06 PM   #13
Global Moderator
 
CRGreathouse's Avatar
 
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.)
CRGreathouse is offline  
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 .
Peter is offline  
May 12th, 2010, 02:02 PM   #15
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2014 My Math Forum. All rights reserved.