My Math Forum Solve a Integer equation system

 Number Theory Number Theory Math Forum

 May 4th, 2010, 05:15 PM #1 Senior Member   Joined: Dec 2006 Posts: 166 Thanks: 3 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: 16,046 Thanks: 937 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 $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 Senior Member   Joined: Dec 2006 Posts: 166 Thanks: 3 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: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
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: 16,046 Thanks: 937 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: 937 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 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 Senior Member   Joined: Dec 2006 Posts: 166 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: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
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 Senior Member   Joined: Dec 2006 Posts: 166 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 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 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top