wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Two Cubic Congruences
        
(Message started by: Barukh on Nov 26^th, 2004, 11:42pm)

Title: Two Cubic Congruences
Post by Barukh on Nov 26^th, 2004, 11:42pm

Find all solutions in natural numbers of the following system of congruences:

x³ + 1 [equiv] 0 mod y
y³ + 1 [equiv] 0 mod x

Title: Re: Two Cubic Congruences
Post by SWF on Dec 6^th, 2004, 9:45pm

There are lots of solutions, such as (76405, 319189) and many more obvious ones like (1,1) and (2,3). I am guessing there are an infinite number of solutions, and a general formula.

Title: Re: Two Cubic Congruences
Post by Barukh on Dec 9^th, 2004, 2:41am

on 12/06/04 at 21:45:53, SWF wrote:

There are lots of solutions, such as (76405, 319189)

How did you get this one?

Quote:

I am guessing there are an infinite number of solutions,

Correct.

Quote:

...and a general formula.

It is true there is a formula to produce an infinite number of solutions (can you derive it?).

The tough question is: does it produce every solution? Frankly speaking, I don't know the answer...

Title: Re: Two Cubic Congruences
Post by towr on Dec 9^th, 2004, 6:16am

In case anyone wants some examples to distill regularities from, here are all the pairs with x and y <=150

[1,1]
[2,1]
[1,2]
[3,2]
[9,2]
[2,3]
[14,3]
[9,5]
[14,5]
[2,9]
[5,9]
[146,9]
[3,14]
[5,14]
[45,14]
[61,14]
[54,35]
[14,45]
[35,54]
[14,61]
[114,65]
[65,114]
[9,146]

Title: Re: Two Cubic Congruences
Post by SWF on Dec 9^th, 2004, 6:53pm

I used a simple program to find solutions pretty much by mindless trial and error, except knowing x and y are relatively prime. Then noticed that the same number often appears in different pairs. When loooking for larger pairs tried using one of the larger numbers from some previously found pairs. Sometimes that helps find more. For example the sequence

1, 2, 3, 14, 16, 16213, 989054

has each adjacent pair as suitable numbers. I found (76405, 319189) after finding that (18289, 76405) by trial and using 76405 as the new lower number. Some others: (56126, 331467), (78174, 730835), (3869073, 2088449). Do all of these fit your formula, Barukh?

I was unable to find a formula. Tried a few things like factoring (x^3+1). Let y=a*b, and take (x+1) divisible by a, and (x^2-x+1) divisible by b, and similarly let x=c*d,... That didn't go far enough. Also tried x=a+b with no success.

Title: Re: Two Cubic Congruences
Post by Barukh on Dec 10^th, 2004, 4:20am

on 12/09/04 at 18:53:37, SWF wrote:

1, 2, 3, 14, 16, 16213, 989054

I think you mean 61, not 16.

Quote:

(76405, 319189) after finding that (18289, 76405) by trial and using 76405 as the new lower number. Some others: (56126, 331467), (78174, 730835), (3869073, 2088449). Do all of these fit your formula, Barukh?

Of course, not! Again, the formula I had in mind allows to produce an infinite number of solutions as follows: If (x, y) is a specific solution with x [le] y, then (y, (y³+1)/x) is also a solution of this kind. Starting at (1,1) one derives (1,2), (2,9), (9,365),… Starting at (2,3), one gets (3,14), (14,915),… etc.

The problem with this formula is that the solutions grow very rapidly and many small solutions are not covered. :(

Quote:

I was unable to find a formula. Tried a few things like factoring (x^3+1). Let y=a*b, and take (x+1) divisible by a, and (x^2-x+1) divisible by b, and similarly let x=c*d,... That didn't go far enough. Also tried x=a+b with no success.

I investigated the case when x divides y+1. I believe I managed to show that then x can be one of 2, 3, 5. This produces the solutions (2,3), (2,9), (3,14), (5,9), (5,14). But I cannot recall the proof… Or, maybe it was not a proof? ;D