Author 
Topic: Cubic Congruences (Read 691 times) 

ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Cubic Congruences
« on: Jul 12^{th}, 2008, 8:32am » 
Quote Modify

I posted this on sci.math 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^{3} + 1 = 0 (mod y) y^{3} + 1 = 0 (mod x)


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730


Re: Cubic Congruences
« Reply #1 on: Jul 12^{th}, 2008, 10:51am » 
Quote Modify

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.


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Congruences
« Reply #2 on: Jul 12^{th}, 2008, 12:38pm » 
Quote Modify

Call a solution with x y reduced if y^{2} x^{3}+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^{3}+1)/y, x, y, (y^{3}+1)/x, ...

« Last Edit: Jul 12^{th}, 2008, 12:39pm by Eigenray » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Cubic Congruences
« Reply #3 on: Jul 12^{th}, 2008, 2:37pm » 
Quote Modify

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 yx^{2}x+1, we can jump down from the row containing (x,y,z) to (x, y',z'), where y' = (x^{2}x+1)/y. Then we have y'z'^{2}z+1, so we can jump again to (x', y'', z'), etc. Similarly, if yx+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?


IP Logged 



