wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Cubic Congruences
        
(Message started by: ThudanBlunder on Jul 12^th, 2008, 8:32am)

Title: Cubic Congruences
Post by ThudanBlunder on Jul 12^th, 2008, 8:32am

I posted this on sci.math (http://mathforum.org/kb/thread.jspa?threadID=1092718&messageID=3462763#3462763) a few years ago and even those rottweilers didn't bite:

Is there a general formula for all solutions in natural numbers of the following system of congruences:

x³ + 1 = 0 (mod y)
y³ + 1 = 0 (mod x)

Title: Re: Cubic Congruences
Post by towr on Jul 12^th, 2008, 10:51am

[hide]
We can add a term to each without consequence
x^3+y^3 + 1 = 0 mod y
x^3+y^3 + 1 = 0 mod x

So x^3+y^3 + 1 is a multiple of x and y, and therefore of xy/ggd(x,y)

If x and y are coprime, we 'just' need to solve x^3+y^3 - n * xy + 1.
[/hide]

Title: Re: Cubic Congruences
Post by Eigenray on Jul 12^th, 2008, 12:38pm

Call a solution with x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif y reduced if y² http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x³+1. The first few reduced solutions are

{1,1}, {2, 3}, {5, 9}, {14, 45}, {35, 54}, {49, 325}, {65, 114}, {93, 398}, {99, 626}, ...

Is there a pattern?

Each reduced solution gives an infinite sequence of solutions:

..., 9, 2, 1, 1, 2, 9, 365, 5403014, ...
..., 14, 3, 2, 3, 14, 915, 54718634, ...
..., 11819225, 549, 14, 5, 9, 146, 345793, ...
..., 16213, 61, 14, 45, 6509, 6128162894, ...
..., (x³+1)/y, x, y, (y³+1)/x, ...

Title: Re: Cubic Congruences
Post by Eigenray on Jul 12^th, 2008, 2:37pm

We can sometimes move from one reduced solution to another:

365	9	2	1	1	2	9
	54718634	915	14	3	2	3
6128162894	6509	45	14	61	16213	69865104518
			4934544280910258	4308937	16213	989054
			4934544280910258	5650982425657216682614011

If y|x²-x+1, we can jump down from the row containing (x,y,z) to (x, y',z'), where y' = (x²-x+1)/y. Then we have y'|z'²-z+1, so we can jump again to (x', y'', z'), etc.

Similarly, if y|x+1, we can jump from (x, y) to (x, y'), where y'=(x+1)/y. But it looks like this will only take us between [1,2,9], [2,3,14], and [14,5,9].

But what about solutions like (35,54)? Can we connect them to (1,1) somehow?