wu :: forums « wu :: forums - Cubic Congruences » Welcome, Guest. Please Login or Register. Apr 12th, 2024, 3:33am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: Eigenray, towr, Icarus, william wu, SMQ, Grimbal)    Cubic Congruences « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Cubic Congruences  (Read 706 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »