wu :: forums
wu :: forums - Cubic Congruences

Welcome, Guest. Please Login or Register.
Jan 19th, 2022, 11:05am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Eigenray, SMQ, Grimbal, william wu, towr, Icarus)
   Cubic Congruences
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Cubic Congruences  (Read 691 times)
ThudnBlunder
Uberpuzzler
*****




The dewdrop slides into the shining Sea

   


Gender: male
Posts: 4489
Cubic Congruences  
« on: Jul 12th, 2008, 8:32am »
Quote Quote Modify 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: male
Posts: 13730
Re: Cubic Congruences  
« Reply #1 on: Jul 12th, 2008, 10:51am »
Quote Quote Modify 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: male
Posts: 1948
Re: Cubic Congruences  
« Reply #2 on: Jul 12th, 2008, 12:38pm »
Quote Quote Modify 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: male
Posts: 1948
Re: Cubic Congruences  
« Reply #3 on: Jul 12th, 2008, 2:37pm »
Quote Quote Modify Modify

We can sometimes move from one reduced solution to another:
365921129
5471863491514323
612816289465094514611621369865104518
4934544280910258430893716213989054
49345442809102585650982425657216682614011

 
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 Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

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