wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> A MODULAR PROBLEM
        
(Message started by: pcbouhid on Nov 25^th, 2005, 6:26am)

Title: A MODULAR PROBLEM
Post by pcbouhid on Nov 25^th, 2005, 6:26am

Find the smallest positive integer x such that 2^x = 3 (mod x).

Title: Re: A MODULAR PROBLEM
Post by JohanC on Nov 25^th, 2005, 6:49am

The two first solutions I can find are
[hide]4700063497[/hide] and [hide]8365386194032363[/hide].

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.

Title: Re: A MODULAR PROBLEM
Post by pcbouhid on Nov 25^th, 2005, 8:54am

[hide]Agree with you,[/hide] JC.

Title: Re: A MODULAR PROBLEM
Post by rmsgrey on Nov 26^th, 2005, 4:38am

How about [hide] 1 [/hide] and [hide] 2 [/hide]?

OK, arguments could be made for them not being valid, but you can also argue the converse.

Title: Re: A MODULAR PROBLEM
Post by towr on Nov 26^th, 2005, 2:06pm

on 11/26/05 at 04:38:19, rmsgrey wrote:

How about [hide] 1 [/hide] and [hide] 2 [/hide]?

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..

Title: Re: A MODULAR PROBLEM
Post by rmsgrey on Nov 27^th, 2005, 8:12am

Nor can I now that I've remembered how to do simple arithmetic...

Title: Re: A MODULAR PROBLEM
Post by JohanC on Nov 27^th, 2005, 12:37pm

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

Title: Re: A MODULAR PROBLEM
Post by Icarus on Nov 27^th, 2005, 12:53pm

on 11/27/05 at 12:37:55, 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?

Title: Re: A MODULAR PROBLEM
Post by JohanC on Nov 27^th, 2005, 2:16pm

on 11/27/05 at 12:53:12, 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&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

Title: Re: A MODULAR PROBLEM
Post by NickH on Nov 29^th, 2005, 12:47pm

See also this thread. (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1050227385)