Author |
Topic: Cubic Congruences (Read 707 times) |
|
ThudnBlunder
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Cubic Congruences
« on: Jul 12th, 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:
x3 + 1 = 0 (mod y)
y3 + 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 12th, 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 12th, 2008, 12:38pm » |
Quote Modify
|
Call a solution with x  y reduced if y2 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, ...
|
| « Last Edit: Jul 12th, 2008, 12:39pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Cubic Congruences
« Reply #3 on: Jul 12th, 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 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?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print