Author |
Topic: A MODULAR PROBLEM (Read 917 times) |
|
pcbouhid
Uberpuzzler
Gender: 
Posts: 647
|
 |
A MODULAR PROBLEM
« on: Nov 25th, 2005, 6:26am » |
 Quote  Modify
|
Find the smallest positive integer x such that 2^x = 3 (mod x).
|
|
 IP Logged |
Don´t follow me, I´m lost too.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: A MODULAR PROBLEM
« Reply #1 on: Nov 25th, 2005, 6:49am » |
Quote Modify
|
The two first solutions I can find are
4700063497 and 8365386194032363.
I have the impression that you only know the answer because it was written down somewhere, as there is no simple algorithm to find them.
|
|
IP Logged |
|
|
|
pcbouhid
Uberpuzzler
Gender:
Posts: 647
|
|
Re: A MODULAR PROBLEM
« Reply #2 on: Nov 25th, 2005, 8:54am » |
Quote Modify
|
Agree with you, JC.
|
|
IP Logged |
Don´t follow me, I´m lost too.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: A MODULAR PROBLEM
« Reply #3 on: Nov 26th, 2005, 4:38am » |
Quote Modify
|
How about 1 and 2 ?
OK, arguments could be made for them not being valid, but you can also argue the converse.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A MODULAR PROBLEM
« Reply #4 on: Nov 26th, 2005, 2:06pm » |
Quote Modify
|
on Nov 26th, 2005, 4:38am, rmsgrey wrote:How about 1 and 2 ?
OK, arguments could be made for them not being valid, but you can also argue the converse. |
|
I can see arguments for the first, but not for the second..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: A MODULAR PROBLEM
« Reply #5 on: Nov 27th, 2005, 8:12am » |
Quote Modify
|
Nor can I now that I've remembered how to do simple arithmetic...
|
| « Last Edit: Nov 27th, 2005, 8:14am by rmsgrey » |
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: A MODULAR PROBLEM
« Reply #6 on: Nov 27th, 2005, 12:37pm » |
Quote Modify
|
Here's the straightforward algorithm to find the solution:
1) calculate some values of (2^N)mod N and try to find a pattern
2) as no pattern shows up, enter the list of numbers at the Online Encyclopedia of Integer Sequences:
http://www.research.att.com/~njas/sequences/
3) this returns sequence A015910, with the answer to the question as well as to some related references and websites
4) lookup 4700063497 via Google, which leads to more websites such as
http://www.primepuzzles.net/puzzles/puzz_149.htm
which explains some history around the problem, and the fact that it is still not known for certain which is the second smallest number satisfying the equation
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: A MODULAR PROBLEM
« Reply #7 on: Nov 27th, 2005, 12:53pm » |
Quote Modify
|
on Nov 27th, 2005, 12:37pm, JohanC wrote:| ...it is still not known for certain which is the second smallest number satisfying the equation |
|
Is there something wrong with your 8365386194032363? or are they just not know if it is 2nd?
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: A MODULAR PROBLEM
« Reply #8 on: Nov 27th, 2005, 2:16pm » |
Quote Modify
|
on Nov 27th, 2005, 12:53pm, Icarus wrote:
Is there something wrong with your 8365386194032363? or are they just not know if it is 2nd? |
|
Hi, Icarus,
8365386194032363 satisfies the equation, but it is unknown whether there exist other smaller solutions.
Just checking whether it satisfies is not straightforward, as 2^8365386194032363 has an enormous amount of digits.
The method is somewhat explained at
http://134.129.111.8/cgi-bin/wa.exe?A2=ind0009&L=nmbrthry&O=D&am p;P=2355
By the way, only one more solution is known. It has 65 digits:
63130707451134435989380140059866138830623361447484274774099906755
This one is elaborated at
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind9906&L=NMBRTHRY&P =1753
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
