Author |
Topic: Two Cubic Congruences (Read 645 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Two Cubic Congruences
« on: Nov 26th, 2004, 11:42pm » |
 Quote  Modify
|
Find all solutions in natural numbers of the following system of congruences:
x3 + 1 [equiv] 0 mod y
y3 + 1 [equiv] 0 mod x
|
|
 IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Two Cubic Congruences
« Reply #1 on: Dec 6th, 2004, 9:45pm » |
Quote Modify
|
There are lots of solutions, such as (76405, 319189) and many more obvious ones like (1,1) and (2,3). I am guessing there are an infinite number of solutions, and a general formula.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Cubic Congruences
« Reply #2 on: Dec 9th, 2004, 2:41am » |
Quote Modify
|
on Dec 6th, 2004, 9:45pm, SWF wrote:| There are lots of solutions, such as (76405, 319189) |
|
How did you get this one?
Quote:| I am guessing there are an infinite number of solutions, |
|
Correct.
Quote:| ...and a general formula. |
|
It is true there is a formula to produce an infinite number of solutions (can you derive it?).
The tough question is: does it produce every solution? Frankly speaking, I don't know the answer...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Two Cubic Congruences
« Reply #3 on: Dec 9th, 2004, 6:16am » |
Quote Modify
|
In case anyone wants some examples to distill regularities from, here are all the pairs with x and y <=150
[1,1]
[2,1]
[1,2]
[3,2]
[9,2]
[2,3]
[14,3]
[9,5]
[14,5]
[2,9]
[5,9]
[146,9]
[3,14]
[5,14]
[45,14]
[61,14]
[54,35]
[14,45]
[35,54]
[14,61]
[114,65]
[65,114]
[9,146]
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Two Cubic Congruences
« Reply #4 on: Dec 9th, 2004, 6:53pm » |
Quote Modify
|
I used a simple program to find solutions pretty much by mindless trial and error, except knowing x and y are relatively prime. Then noticed that the same number often appears in different pairs. When loooking for larger pairs tried using one of the larger numbers from some previously found pairs. Sometimes that helps find more. For example the sequence
1, 2, 3, 14, 16, 16213, 989054
has each adjacent pair as suitable numbers. I found (76405, 319189) after finding that (18289, 76405) by trial and using 76405 as the new lower number. Some others: (56126, 331467), (78174, 730835), (3869073, 2088449). Do all of these fit your formula, Barukh?
I was unable to find a formula. Tried a few things like factoring (x^3+1). Let y=a*b, and take (x+1) divisible by a, and (x^2-x+1) divisible by b, and similarly let x=c*d,... That didn't go far enough. Also tried x=a+b with no success.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Two Cubic Congruences
« Reply #5 on: Dec 10th, 2004, 4:20am » |
Quote Modify
|
on Dec 9th, 2004, 6:53pm, SWF wrote:| 1, 2, 3, 14, 16, 16213, 989054 |
|
I think you mean 61, not 16.
Quote:| (76405, 319189) after finding that (18289, 76405) by trial and using 76405 as the new lower number. Some others: (56126, 331467), (78174, 730835), (3869073, 2088449). Do all of these fit your formula, Barukh? |
|
Of course, not! Again, the formula I had in mind allows to produce an infinite number of solutions as follows: If (x, y) is a specific solution with x [le] y, then (y, (y3+1)/x) is also a solution of this kind. Starting at (1,1) one derives (1,2), (2,9), (9,365),… Starting at (2,3), one gets (3,14), (14,915),… etc.
The problem with this formula is that the solutions grow very rapidly and many small solutions are not covered. 
Quote:| I was unable to find a formula. Tried a few things like factoring (x^3+1). Let y=a*b, and take (x+1) divisible by a, and (x^2-x+1) divisible by b, and similarly let x=c*d,... That didn't go far enough. Also tried x=a+b with no success. |
|
I investigated the case when x divides y+1. I believe I managed to show that then x can be one of 2, 3, 5. This produces the solutions (2,3), (2,9), (3,14), (5,9), (5,14). But I cannot recall the proof… Or, maybe it was not a proof? 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print