Problems & Puzzles: Puzzles

Puzzle 389. Joe Crump and the search for solutions to 2n mod n=c

The first good new that I want to share with you is that the very interesting pages by Joe Crump are again available in his new site.

Here you will enjoy several number theory issues exposed by him in a very amusing manner. There you'll find also his useful tool Zzmath.xll, an Excel Addin.

Well, one of the sections of his site is devoted to solutions (*) to the equation:

2n mod n = c

As a matter of fact, Crump has been working over this subject several years, and his main results can be studied in detail in his database of solutions.

From this section and with his explicit permission I pose here some unsolved questions (1-2) that he has obtained as a result of his large search.

Questions:

1 - Are there infinite solutions to 2^n = c (mod n) for c>1 ?
2 - Find a solution to 2^n mod n = 465
3.  Find a larger solution to 2^n mod n = 3, than the obtained by Peter Montgomery in 1999, by factoring 2^485-3 with SNFS:
n=63130707451134435989380140059866138830623361447484274774099906755   
 

 _______
(*) Solutions to the particular case 2n mod n = 3 were asked in the Puzzle 149.
 

Contribution came from Anton Vrba:

***

Anton wrote:

While trying to find a new approach to extend the 2^n=c (mod n) sequences I observed following:

Let  q=f1*f2*f3*...fn  and define ri  as  q = ri (mod fi-1)

If  2^ ri  = c (mod  fi ),  i=1,2,..n  then 2^q = c (mod  q)

Example:  43823239 = 7 * 167 * 123031

r1 = 5,  2^5 =  4 (mod 7)   (note 4+7=11)
r2 = 9,  2^9  = 11 (mod 167),
r2 = 1169,  2^1169 = 11 (mod 123031)
2^143823239 = 11 (mod 143823239) 

I now reformulate above as follows:

Conjecture: For any positive composite integer n and b^n=c (mod n) then for all prime divisors p of  n,  it is true that p−1 divides n−r such that b^r = c (mod p)

Be reminded of the definition of Carmichael numbers

Theorem (Korselt 1899): A positive composite integer n is a Carmichael number if and only if n is square free and for all prime divisors p of n, it is true that p−1 divides n−1.

[(now trivial addition) such that b^1 = b (mod p) and  b^n=b (mod n)]

Now, possibly one could apply the techniques which are applicable to Carmichael numbers to prove that there are infinite many n, such that 2^n=3 (mod n) and develop new techniques to find further examples.

Q1:  Can the conjecture be proven?

***

Joe Crump wrote, on March 9, 07:

The value 164196324252985941533 solves the equation 2^n = 465 mod n 

I had originally attempted to find a solution via the factorization method, with the CPU help from my brother and friends Mark Miller and Curtis Krumel at Microsoft. We factored a lot of 2^x-465 without finding a solution. However, after not finding a solution with that method I switched back to a modified version of my prime-and-line algorithm and found this solution.  My brother and friends are back focusing on factoring 2^x-3 in conjunction with Max Alekseyev to solve part 3.

***

On Dec 16, 2022, Adam Stichcombe wrote:

RE: question #1.  There are infinity many solutions to some congruences, namely   2^ (2p) = 4 mod 2p    for an odd prime p.

***

 
Records   |  Conjectures  |  Problems  |  Puzzles