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

What an interesting question!  The solution seems to be have been found.  Just some thoughts:

(1) x cannot be even.  Clearly, if x is even, then  2^x (mod x) is even.

(2) x cannot be prime.  If x is prime, then the series 2¹ , 2² ,  2³ , 2⁴, ... when converted to mod x, has a cycle that evenly divides x - 1.  Therefore, 2^x-1 (mod x) = 1 and 2^x (mod x) = 2.

(3) Therefore x must be an odd composite.

(4) Here is as far as I got in my exploration of odd composites:

x  2^x (mod x)
-- ------------
9      8
15    8
21    8
25    7 
27    26
33    8
35    18
39    8
45    17
49    30
51    8
55    43
63    8
65    32
69    8
75    68

I wonder why 8 shows up so much?  There is probably a way to rule all of these numbers out, but the pattern is not obvious to me.

Clearly, I was not close to the solution.

Posted by Steve Herman on 2008-12-19 15:25:11