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
Senior Member
 
Joined: Dec 2006

Posts: 137
Thanks: 1

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: 14,011
Thanks: 427

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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
Senior Member
 
Joined: Dec 2006

Posts: 137
Thanks: 1

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: 14,011
Thanks: 427

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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: 14,011
Thanks: 427

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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: 14,011
Thanks: 427

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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
Senior Member
 
Joined: Dec 2006

Posts: 137
Thanks: 1

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: 14,011
Thanks: 427

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic
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
Senior Member
 
Joined: Dec 2006

Posts: 137
Thanks: 1

Re: Solve a Integer equation system

Thanks a lot CRGreathouse. I got lots to learn.
elim 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.