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 12th, 2008, 8:32am)

Title: Cubic Congruences
Post by ThudanBlunder on Jul 12th, 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:

x3 + 1 = 0 (mod y)
y3 + 1 = 0 (mod x)

Title: Re: Cubic Congruences
Post by towr on Jul 12th, 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 12th, 2008, 12:38pm
Call a solution with x http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif y reduced if y2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif x3+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, ...
..., (x3+1)/y, x, y, (y3+1)/x, ...

Title: Re: Cubic Congruences
Post by Eigenray on Jul 12th, 2008, 2:37pm
We can sometimes move from one reduced solution to another:
3659 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|x2-x+1, we can jump down from the row containing (x,y,z) to (x, y',z'), where y' = (x2-x+1)/y.  Then we have y'|z'2-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?



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board