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.


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:


It was just of something I ran across empirically during my computational attack on 2^n mod n = c equations [] 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.


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