Problems & Puzzles: Problems

Problem 40.  Crump's equation

Joe K. Crump (*) sent the following problem:

Consider the equation: 2^n = 2^(2^z+1)  mod n

Where: n = 2^(z*p)+1, prime p > 2 & z is any positive integer

1 - Prove or Disprove the equation always holds for z<=4.
2 - Prove or Disprove the equation always holds when p = 1 mod (z-1).

________
Joe is author of a very nice and interesting Add-in for Excel - freely downloadable - capable of handling the most of the usual functions of Number Theory. I'm sure that you'll enjoy it as I do.

To use it, do this:

1) Download it to your PC to: c:\windows\ApplicationData\Microsoft\Addins 
2) Open your Excel
3) Active the ZMath add-in: Tools, Add-in, Zmath, Accept
4) To see all the available functions: click the fx button, take the Zmath functions and browse for all the available functions in the right window.

Joe recommends the following way:

1 - Copy it somewhere on your harddrive, say C:\ZZMath.xll
2 - In Excel 97, 2000, or XP, choose File/Open
3 - Navigate to "C:\" or just type in "C:\zzmath.xll" and click OK.
4 - The addin will be loaded. Click 'Enable Macros' if prompted.
5 - Type =ZAdd(123,456) in a cell to verify it is working. ======================== 
The only exception is if you are using Excel XP and your Macro security is set to 'High', then the addin won't load and you won't get a warning. Go to Tools menu, Macro submenu, and click 'Security' to change it to 'Medium' if you are using Excel XP.


Solution:

Eric Brier solved completely this problem. Here is the paper (a pdf file) he sent the 23/9/22.

***

I asked to both, Crump and Brier, what was their respective interest in this equation and problem. Here are their answers:

Crump

It was just of something I ran across empirically during my computational attack on 2^n mod n = c equations [http://www.spacefire.com/numbertheory/2nmodn.htm] and figured it would be an interesting problem for your site.

If you or Eric are interested, a related problem with a lot of attention associated with it (but much harder to solve) is whether for every c > 1 there is at least one solution n to 2^n mod n = c. This would be something of interest to a lot of number theorists.

I'm preparing to setup a challenge on my web-site offering $50 (US) for a proof to the above. And $25 for a solution to 2^n mod n = 465. The least 'c' for which no solution is currently known is c=465 resisting a strong search thus far.

Brier

I was interested by this problem because congruences are related to my work in cryptography and this kind of properties looked rather strange at the first sight.

***

 



Records   |  Conjectures  |  Problems  |  Puzzles