
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 4th, 2010, 05:15 PM  #1 
Senior Member Joined: Dec 2006 Posts: 163 Thanks: 3  Solve a Integer equation system
Let Find smallest 
May 5th, 2010, 06:23 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Solve a Integer equation system
No solutions below 10^45. Edit: No solutions below 10^55. 
May 5th, 2010, 06:53 AM  #3 
Member 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 
Senior Member Joined: Dec 2006 Posts: 163 Thanks: 3  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: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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 
Senior Member Joined: Dec 2006 Posts: 163 Thanks: 3  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: 16,046 Thanks: 932 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  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 
Senior Member Joined: Dec 2006 Posts: 163 Thanks: 3  Re: Solve a Integer equation system
Thanks a lot CRGreathouse. I got lots to learn.


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 